Jak efektywnie sortować znaki w ciągu w R?

Jak mogę skutecznie sortować znaki każdego łańcucha w wektorze? Na przykład, biorąc pod uwagę wektor ciągów:

set.seed(1)
strings <- c(do.call(paste0, replicate(4, sample(LETTERS, 10000, TRUE), FALSE)),
do.call(paste0, replicate(3, sample(LETTERS, 10000, TRUE), FALSE)),
do.call(paste0, replicate(2, sample(LETTERS, 10000, TRUE), FALSE)))

Napisałem funkcję, która podzieli każdy ciąg na wektor, posortuje wektor, a następnie zwinie dane wyjściowe:

sort_cat <- function(strings){
  tmp <- strsplit(strings, split="")
  tmp <- lapply(tmp, sort)
  tmp <- lapply(tmp, paste0, collapse = "")
  tmp <- unlist(tmp)
  return(tmp)
}
sorted_strings <- sort_cat(strings)

Jednak wektor ciągów, do którego muszę to zastosować, jest bardzo długi, a ta funkcja jest zbyt wolna. Czy ktoś ma jakieś sugestie dotyczące poprawy wydajności?

Możesz skrócić czas, minimalizując na pewno liczbę pętli, a następnie zrób to, używając parallelpakietu ... moim podejściem byłoby podzielenie ciągów raz, a następnie w sortowaniu i wklejaniu pętli:

sort_cat <- function(strings){
    tmp <- strsplit(strings, split="")
    tmp <- lapply(tmp, sort)
    tmp <- lapply(tmp, paste0, collapse = "")
    tmp <- unlist(tmp)
    return(tmp)
}

sort_cat2 <- function(strings){
    unlist(mcMap(function(i){
        stri_join(sort(i), collapse = "")
    }, stri_split_regex(strings, "|", omit_empty = TRUE, simplify = F), mc.cores = 8L))
}

> microbenchmark::microbenchmark(
+     old = sort_cat(strings[1:500000]),
+     new = sort_cat2(strings[1:500000]),
+     times = 1
+ )
Unit: seconds
 expr        min         lq       mean     median         uq        max neval
  old 9.62673395 9.62673395 9.62673395 9.62673395 9.62673395 9.62673395     1
  new 5.10547437 5.10547437 5.10547437 5.10547437 5.10547437 5.10547437     1

Goli się jak 4 sekundy, ale wciąż nie jest tak szybko ...

Edytować

Dobra, udało mi się to osiągnąć, używając applystrategii tutaj:

1) wyodrębniaj litery zamiast dzielonych granic 2) utwórz matrycę z wynikami 3) iteruj po wierszach 4) Sortuj 5) Dołącz

Unikasz wielu pętli i niepublicznych… IGNORE:? Zastrzeżeniem jest, jeśli ciągi o różnych długościach, musisz usunąć wszelkie puste lub NA w applytakich jaki[!is.na(i) && nchar(i) > 0]

sort_cat3 <- function(strings){
    apply(stri_extract_all_regex(strings, "\\p{L}", simplify = TRUE), 1, function(i){
        stri_join(stri_sort(i), collapse = "")
    })
}

> microbenchmark::microbenchmark(
+     old = sort_cat(strings[1:500000]),
+     mapping = sort_cat2(strings[1:500000]),
+     applying = sort_cat3(strings[1:500000]),
+     times = 1
+ )
Unit: seconds
     expr         min          lq        mean      median          uq         max neval
      old 10.35101934 10.35101934 10.35101934 10.35101934 10.35101934 10.35101934     1
  mapping  5.12771799  5.12771799  5.12771799  5.12771799  5.12771799  5.12771799     1
 applying  3.97775326  3.97775326  3.97775326  3.97775326  3.97775326  3.97775326     1

Zajmuje nam od 10,3 sekundy do 3,98

Ponowne wdrożenie za pomocą stringidaje około 4x przyspieszenie. Zredagowałem również, sort_cataby użyć fixed = TRUEw strsplit, co sprawia, że ​​jest trochę szybszy. I dzięki Carlowi za sugestię pojedynczej pętli, która przyspiesza nas jeszcze trochę.

sort_cat <- function(strings){
  tmp <- strsplit(strings, split="", fixed = TRUE)
  tmp <- lapply(tmp, sort)
  tmp <- lapply(tmp, paste0, collapse = "")
  tmp <- unlist(tmp)
  return(tmp)
}

library(stringi)
sort_stringi = function(s) {
  s = stri_split_boundaries(s, type = "character")
  s = lapply(s, stri_sort)
  s = lapply(s, stri_join, collapse = "")
  unlist(s)
}

sort_stringi_loop = function(s) {
  s = stri_split_boundaries(s, type = "character")
  for (i in seq_along(s)) {
    s[[i]] = stri_join(stri_sort(s[[i]]), collapse = "")
  }
  unlist(s)
}

bench::mark(
  sort_cat(strings),
  sort_stringi(strings),
  sort_stringi_loop(strings)
)
# # A tibble: 3 x 13
#   expression                    min median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result memory
#   <bch:expr>                 <bch:> <bch:>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list> <list>
# 1 sort_cat(strings)          23.01s 23.01s    0.0435    31.2MB     2.17     1    50     23.01s <chr ~ <Rpro~
# 2 sort_stringi(strings)       6.16s  6.16s    0.162     30.5MB     2.11     1    13      6.16s <chr ~ <Rpro~
# 3 sort_stringi_loop(strings)  5.75s  5.75s    0.174     15.3MB     1.74     1    10      5.75s <chr ~ <Rpro~
# # ... with 2 more variables: time <list>, gc <list>

Metodę tę można również stosować równolegle. Profilowanie kodu, aby zobaczyć, które operacje faktycznie trwają najdłużej, byłoby dobrym następnym krokiem, jeśli chcesz iść jeszcze szybciej.

Ta wersja jest nieco szybsza

sort_cat2=function(strings){
A=matrix(unlist(strsplit(strings,split="")),ncol=3,byrow=TRUE)
B=t(apply(A,1,sort))
paste0(B[,1],B[,2],B[,3])
}

Ale myślę, że można to zoptymalizować