Radix реализация сортировки в R

Question

Как реализовать Radix sort в базе R (например) для следующего вектора:

vec <- c(25, 478, 34, 9021, 6, 9947, 504, 22) 

В общем, Radix сортировки выполняет следующие действия:

• Сортировать основанный на unit позиции: 9021 22 34 504 25 6 9947 478
• Сортировка на основе ten позиций: 504 6 9021 22 25 34 9947 478
• Сортировка на основе hundred позиций: 6 9021 22 25 34 478 504 9947
• Сортировка на основе thousand позиций: 6 22 25 34 478 504 9021 9947

и так далее. Конечно, vec - всего лишь пример, и решение может иметь дело с данными любой длины, содержащей числа любой длины.

Выход будет vec отсортировано по возрастанию (по убыванию). То есть,

6 22 25 34 478 504 9021 9947 

Answer 1

Вот мое собственное решение:

f_radixSort <- function(x){ 
    mx <- nchar(max(x)) 
    for (i in 1:mx) 
     x <- x[order(x%%(10^i))] 
    return(x) 
} 

И образец вызова вместе с печатью пошаговой сортировки.

f_radixSort(vec) 

# units 
# [1] 9021 22 34 504 25 6 9947 478 

# tens 
# [1] 504 6 9021 22 25 34 9947 478 

# hundreds 
# [1] 6 9021 22 25 34 478 504 9947 

# thousands 
# [1] 6 22 25 34 478 504 9021 9947 

# ten thousands 
# [1] 6 22 25 34 478 504 9021 9947 

И короткий СРАВНИТЕЛЬНЫЙ (я не включал сортировку с использованием data.table как я не знаю, что это чей принцип и, кроме того, я спросил об ответе на базовом R):

library(microbenchmark) 
vec <- c(25, 478, 34, 9021, 6, 9947, 504, 22) 

all(radix(vec)==f_radixSort(vec)) 
# [1] TRUE 

microbenchmark(radix(vec), f_radixSort(vec)) 

# Unit: microseconds 
      # expr  min  lq  mean median  uq  max neval 
     # radix(vec) 857.239 915.230 980.39907 943.4745 1005.071 2081.051 100 
# f_radixSort(vec) 39.061 42.216 52.28206 51.0810 54.686 111.775 100 

# ======================================================== 
set.seed(200) 
vec<-sample(10000,5000) 

all(radix(vec)==f_radixSort(vec)) 
# [1] TRUE 

microbenchmark(radix(vec), f_radixSort(vec)) 

# Unit: milliseconds 
      # expr  min  lq  mean median  uq  max neval 
     # radix(vec) 6.724506 7.003191 8.135387 7.877256 8.195904 52.786763 100 
# f_radixSort(vec) 2.132132 2.167436 2.302167 2.200337 2.268544 4.009464 100 

Answer 2

Я знаю, что data.table реализует Radix сортировки из коробки, так что вы можете использовать этот пакет и, например, сортировать данные, просто установив ключ:

library(data.table) 

vec <- c(25, 478, 34, 9021, 6, 9947, 504, 22) 

f1<-function(vec){ 
    DT<-data.table(vec) 
setkey(DT, vec) 
DT 
} 

f1(vec) 

    vec 
1: 6 
2: 22 
3: 25 
4: 34 
5: 478 
6: 504 
7: 9021 
8: 9947 

I предположим, что вы могли бы реализовать алгоритм самостоятельно, но это, вероятно, будет медленным в R. функция будет выглядеть примерно так:

library(stringr) 
library(dplyr) 
library(tidyr) 

radix<-function(numbers){ 
    digits<-nchar(max(numbers)) 
    numbers<-str_pad(numbers, digits, pad = "0") 
    rad<-data.frame(matrix(0, ncol = digits, nrow = length(numbers))) 

    for(i in 1:digits){ 
    rad[,i] <- str_sub(numbers, i,i) 
    } 

    for(z in rev(1:ncol(rad))){ 
    a <- which(rad[,z] == 0) 
    b <- which(rad[,z] == 1) 
    c <- which(rad[,z] == 2) 
    d <- which(rad[,z] == 3) 
    e <- which(rad[,z] == 4) 
    f <- which(rad[,z] == 5) 
    g <- which(rad[,z] == 6) 
    h <- which(rad[,z] == 7) 
    i <- which(rad[,z] == 8) 
    j <- which(rad[,z] == 9) 

    k<-c(a,b,c,d,e,f,g,h,i,j) 
    rad<-rad[k,] 
    } 

    rad<-rad %>% unite_(col = "num", from = colnames(rad), sep = "") 
    return(as.numeric(rad$num)) 
} 

It может быть очищен/скорость, но это делает базисное то, как я понимаю:

radix(vec) 
[1] 6 22 25 34 478 504 9021 9947 

Для сравнения скорости:

microbenchmark(f1(vec), radix(vec)) 

Unit: microseconds 
     expr min  lq mean median  uq  max neval 
    f1(vec) 290.6 314.8 335 327 349.1 524.1 100 
radix(vec) 1062.8 1121.7 1458 1163 1250.5 24407.9 100 

Larger Сравнение скорости:

set.seed(200) 
more<-sample(10000,5000) 
microbenchmark(f1(more), radix(more)) 

     expr  min  lq mean median  uq  max neval 
    f1(more) 539.3 565.5 623 622.2 664.8 769.7 100 
radix(more) 10457.8 10668.0 11683 11133.7 12298.3 25010.6 100