R: Перестановки и комбинации с / без замены и для отдельных / неявных элементов / мультимножества

В этой теме я пытаюсь включить здесь все часто задаваемые вопросы и их ответы. Надеюсь, это будет полезно для кого-то.

Общий вопрос : как сгенерировать последовательности из r объектов из n объектов?

  • комбинация против перестановки.
  • с заменой vs без замены.
  • отдельные элементы против не-отдельных элементов (мультимножество).

Всего существует 2^3=8 вопросов такого типа.

[Обновить]

Джош О’Брайен предполагает, что 8 вопросов связаны с двенадцатикратным образом . Действительно, «разные» вопросы includeся в двенадцать раз, в то время как «неявные» вопросы не включены. Во всяком случае, интересно сравнить 8 вопросов здесь двенадцатым способом. См. Комментарии для дальнейших чтений.

2 Solutions collect form web for “R: Перестановки и комбинации с / без замены и для отдельных / неявных элементов / мультимножества”

EDIT : я обновил ответ на использование более эффективных пакетов

Начало использования arrangement

устройства содержат некоторые эффективные генераторы и iteratorы для перестановок и комбинаций. Было продемонстрировано, что arrangements превосходят большинство существующих пакетов подобного рода. Некоторые этапы можно найти здесь .

Вот ответы на вышеуказанные вопросы

 # 1) combinations: without replacement: distinct items combinations(5, 2) [,1] [,2] [1,] 1 2 [2,] 1 3 [3,] 1 4 [4,] 1 5 [5,] 2 3 [6,] 2 4 [7,] 2 5 [8,] 3 4 [9,] 3 5 [10,] 4 5 # 2) combinations: with replacement: distinct items combinations(5, 2, replace=TRUE) [,1] [,2] [1,] 1 1 [2,] 1 2 [3,] 1 3 [4,] 1 4 [5,] 1 5 [6,] 2 2 [7,] 2 3 [8,] 2 4 [9,] 2 5 [10,] 3 3 [11,] 3 4 [12,] 3 5 [13,] 4 4 [14,] 4 5 [15,] 5 5 # 3) combinations: without replacement: non distinct items combinations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2) [,1] [,2] [1,] "a" "a" [2,] "a" "b" [3,] "a" "c" [4,] "b" "c" # 4) combinations: with replacement: non distinct items combinations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` does not matter [,1] [,2] [1,] "a" "a" [2,] "a" "b" [3,] "a" "c" [4,] "b" "b" [5,] "b" "c" [6,] "c" "c" # 5) permutations: without replacement: distinct items permutations(5, 2) [,1] [,2] [1,] 1 2 [2,] 1 3 [3,] 1 4 [4,] 1 5 [5,] 2 1 [6,] 2 3 [7,] 2 4 [8,] 2 5 [9,] 3 1 [10,] 3 2 [11,] 3 4 [12,] 3 5 [13,] 4 1 [14,] 4 2 [15,] 4 3 [16,] 4 5 [17,] 5 1 [18,] 5 2 [19,] 5 3 [20,] 5 4 # 6) permutations: with replacement: distinct items permutations(5, 2, replace = TRUE) [,1] [,2] [1,] 1 1 [2,] 1 2 [3,] 1 3 [4,] 1 4 [5,] 1 5 [6,] 2 1 [7,] 2 2 [8,] 2 3 [9,] 2 4 [10,] 2 5 [11,] 3 1 [12,] 3 2 [13,] 3 3 [14,] 3 4 [15,] 3 5 [16,] 4 1 [17,] 4 2 [18,] 4 3 [19,] 4 4 [20,] 4 5 [21,] 5 1 [22,] 5 2 [23,] 5 3 [24,] 5 4 [25,] 5 5 # 7) permutations: without replacement: non distinct items permutations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2) [,1] [,2] [1,] "a" "a" [2,] "a" "b" [3,] "a" "c" [4,] "b" "a" [5,] "b" "c" [6,] "c" "a" [7,] "c" "b" # 8) permutations: with replacement: non distinct items permutations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` doesn't matter [,1] [,2] [1,] "a" "a" [2,] "a" "b" [3,] "a" "c" [4,] "b" "a" [5,] "b" "b" [6,] "b" "c" [7,] "c" "a" [8,] "c" "b" [9,] "c" "c" 

Сравнить с другими пакетами

Существует несколько преимуществ использования arrangements над существующими пакетами.

  1. Интегральная структура: вам не нужно использовать разные пакеты для разных методов.

  2. Это очень эффективно. См. https://randy3k.github.io/arrangements/articles/benchmark.html для некоторых тестов.

  3. Это эффективная память, она способна генерировать все 13! перестановка с 1 по 13, существующие пакеты не смогут этого сделать из-за ограничения размера матрицы. Метод getnext() iteratorов позволяет пользователям получать getnext() один за другим.

  4. Сгенерированные устройства находятся в порядке словаря, что может потребоваться для некоторых пользователей.

Прогулка через кусочек комбинаторики в R *

Ниже мы рассмотрим пакеты, оснащенные возможностями генерации комбинаций и перестановок. Если я упустил какой-либо пакет, пожалуйста, простите меня и, пожалуйста, оставьте комментарий или еще лучше, отредактируйте этот пост.

Схема анализа:

  1. Введение
  2. Комбинации
  3. Перестановки
  4. Мультимножества
  5. Резюме
  6. Память

Прежде чем мы начнем, отметим, что комбинации / перестановки с заменой отдельных элементов, отличных от единицы измерения, выбранных m за раз, эквивалентны. Это так, потому что, когда у нас есть замена, это не является конкретным. Таким образом, независимо от того, сколько раз изначально возникает определенный элемент, на выходе будет экземпляр (ы) этого элемента, повторяющийся 1 – m раз.

1. Введение

  1. gtools v 3.8.1
  2. combinat v 0.0-8
  3. multicool v 0,1-10
  4. partitions v 1.9-19
  5. RcppAlgos v 2.0.1 (я автор)
  6. arrangements v 1.1.0
  7. gRbase v gRbase

Я не включал permute , permutations или gRbase::aperm/ar_perm поскольку они на самом деле не предназначены для атаки на эти типы проблем.

| ————————————— ОБЗОР ——— ——————————- |

 |_______________| gtools | combinat | multicool | partitions | | comb rep | Yes | | | | | comb NO rep | Yes | Yes | | | | perm rep | Yes | | | | | perm NO rep | Yes | Yes | Yes | Yes | | perm multiset | | | Yes | | | comb multiset | | | | | |accepts factors| | Yes | | | | m at a time | Yes | Yes/No | | | |general vector | Yes | Yes | Yes | | | iterable | | | Yes | | |parallelizable | | | | | | big integer | | | | | |_______________| iterpc | arrangements | RcppAlgos | gRbase | | comb rep | Yes | Yes | Yes | | | comb NO rep | Yes | Yes | Yes | Yes | | perm rep | Yes | Yes | Yes | | | perm NO rep | Yes | Yes | Yes | * | | perm multiset | Yes | Yes | Yes | | | comb multiset | Yes | Yes | Yes | | |accepts factors| | Yes | Yes | | | m at a time | Yes | Yes | Yes | Yes | |general vector | Yes | Yes | Yes | Yes | | iterable | | Yes | Partially | | |parallelizable | | Yes | Yes | | | big integer | | Yes | | | 

Задачи, m at a time и general vector , относятся к способности генерировать результаты « m за раз» (когда m меньше длины вектора) и перестраивают «общий вектор» в отличие от 1:n . На практике мы обычно занимаемся поиском перестановок общего вектора, поэтому все рассмотренные ниже исследования отражают это (когда это возможно).

Все тесты проводились на трех разных настройках.

  1. Macbook Pro i7 16Gb
  2. Macbook Air i5 4Gb
  3. Lenovo работает под управлением Windows 7 i5 8Gb

Перечисленные результаты были получены из установки №1 (т.е. MBPro). Результаты для двух других систем были схожи. Кроме того, gc() периодически вызывается для обеспечения доступности всей памяти (см. ?gc ).

2. Комбинации

Сначала рассмотрим комбинации без замены, выбранные m за раз.

  1. RcppAlgos
  2. combinat (или utils )
  3. gtools
  4. arrangements
  5. gRbase

Как:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(13) testVector1 < - sort(sample(100, 17)) m <- 9 t1 <- comboGeneral(testVector1, m) ## returns matrix with m columns t3 <- combinat::combn(testVector1, m) ## returns matrix with m rows t4 <- gtools::combinations(17, m, testVector1) ## returns matrix with m columns identical(t(t3), t4) ## must transpose to compare #> [1] TRUE t5 < - combinations(testVector1, m) identical(t1, t5) #> [1] TRUE t6 < - gRbase::combnPrim(testVector1, m) identical(t(t6)[do.call(order, as.data.frame(t(t6))),], t1) #> [1] TRUE 

Ориентир:

 microbenchmark(cbRcppAlgos = comboGeneral(testVector1, m), cbGRbase = gRbase::combnPrim(testVector1, m), cbGtools = gtools::combinations(17, m, testVector1), cbCombinat = combinat::combn(testVector1, m), cbArrangements = combinations(17, m, testVector1), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.064 1.079 1.160 1.012 1.086 2.318 100 #> cbGRbase 7.335 7.509 5.728 6.807 5.390 1.608 100 #> cbGtools 426.536 408.807 240.101 310.848 187.034 63.663 100 #> cbCombinat 97.756 97.586 60.406 75.415 46.391 41.089 100 #> cbArrangements 1.000 1.000 1.000 1.000 1.000 1.000 100 

Теперь мы рассматриваем комбинации с заменой, выбранной m за раз.

  1. RcppAlgos
  2. gtools
  3. arrangements

Как:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(97) testVector2 < - sort(rnorm(10)) m <- 8 t1 <- comboGeneral(testVector2, m, repetition = TRUE) t3 <- gtools::combinations(10, m, testVector2, repeats.allowed = TRUE) identical(t1, t3) #> [1] TRUE ## arrangements t4 < - combinations(testVector2, m, replace = TRUE) identical(t1, t4) #> [1] TRUE 

Ориентир:

 microbenchmark(cbRcppAlgos = comboGeneral(testVector2, m, TRUE), cbGtools = gtools::combinations(10, m, testVector2, repeats.allowed = TRUE), cbArrangements = combinations(testVector2, m, replace = TRUE), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.000 1.000 1.000 1.000 1.000 1.00000 100 #> cbGtools 384.990 269.683 80.027 112.170 102.432 3.67517 100 #> cbArrangements 1.057 1.116 0.618 1.052 1.002 0.03638 100 

3. Перестановки

Сначала рассмотрим перестановки без замены, выбранные m за раз.

  1. RcppAlgos
  2. gtools
  3. arrangements

Как:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(101) testVector3 < - as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)) ## RcppAlgos... permuteGeneral same as comboGeneral above t1 <- permuteGeneral(testVector3, 6) ## gtools... permutations same as combinations above t3 <- gtools::permutations(10, 6, testVector3) identical(t1, t3) #> [1] TRUE ## arrangements t4 < - permutations(testVector3, 6) identical(t1, t4) #> [1] TRUE 

Ориентир:

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector3, 6), cbGtools = gtools::permutations(10, 6, testVector3), cbArrangements = permutations(testVector3, 6), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.079 1.027 1.106 1.037 1.003 5.37 100 #> cbGtools 158.720 92.261 85.160 91.856 80.872 45.39 100 #> cbArrangements 1.000 1.000 1.000 1.000 1.000 1.00 100 

Далее мы рассмотрим перестановки без замены общим вектором (возвращающим все перестановки).

  1. RcppAlgos
  2. gtools
  3. combinat
  4. multicool
  5. arrangements

Как:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(89) testVector3 < - as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)) testVector3Prime <- testVector3[1:7] ## For RcppAlgos, & gtools (see above) ## combinat t4 <- combinat::permn(testVector3Prime) ## returns a list of vectors ## convert to a matrix t4 <- do.call(rbind, t4) ## multicool.. we must first call initMC t5 <- multicool::allPerm(multicool::initMC(testVector3Prime)) ## returns a matrix with n columns all.equal(t4[do.call(order,as.data.frame(t4)),], t5[do.call(order,as.data.frame(t5)),]) #> [1] TRUE 

Ориентир:

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector3Prime, 7), cbGtools = gtools::permutations(7, 7, testVector3Prime), cbCombinat = combinat::permn(testVector3Prime), cbMulticool = multicool::allPerm(multicool::initMC(testVector3Prime)), cbArrangements = permutations(x = testVector3Prime, k = 7), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.152 1.275 0.7508 1.348 1.342 0.3159 100 #> cbGtools 965.465 817.645 340.4159 818.137 661.068 12.7042 100 #> cbCombinat 280.207 236.853 104.4777 238.228 208.467 9.6550 100 #> cbMulticool 2573.001 2109.246 851.3575 2039.531 1638.500 28.3597 100 #> cbArrangements 1.000 1.000 1.0000 1.000 1.000 1.0000 100 

Теперь рассмотрим перестановки без замены для 1:n (возвращая все перестановки).

  1. RcppAlgos
  2. gtools
  3. combinat
  4. multicool
  5. partitions
  6. arrangements

Как:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(89) t1 < - partitions::perms(7) ## returns an object of type 'partition' with n rows identical(t(as.matrix(t1)), permutations(7,7)) #> [1] TRUE 

Ориентир:

 microbenchmark(cbRcppAlgos = permuteGeneral(7, 7), cbGtools = gtools::permutations(7, 7), cbCombinat = combinat::permn(7), cbMulticool = multicool::allPerm(multicool::initMC(1:7)), cbPartitions = partitions::perms(7), cbArrangements = permutations(7, 7), unit = "relative") #> Unit: relative #> expr min lq mean median uq max #> cbRcppAlgos 1.235 1.429 1.412 1.503 1.484 1.720 #> cbGtools 1152.826 1000.736 812.620 939.565 793.373 499.029 #> cbCombinat 347.446 304.866 260.294 296.521 248.343 284.001 #> cbMulticool 3001.517 2416.716 1903.903 2237.362 1811.006 1311.219 #> cbPartitions 2.469 2.536 2.801 2.692 2.999 2.472 #> cbArrangements 1.000 1.000 1.000 1.000 1.000 1.000 #> neval #> 100 #> 100 #> 100 #> 100 #> 100 #> 100 

Наконец, мы рассмотрим перестановки с заменой.

  1. RcppAlgos
  2. iterpc
  3. gtools
  4. arrangements

Как:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(34) testVector3 < - as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)) t1 <- permuteGeneral(testVector3, 5, repetition = TRUE) t3 <- gtools::permutations(10, 5, testVector3, repeats.allowed = TRUE) t4 <- permutations(x = testVector3, k = 5, replace = TRUE) 

Этот следующий тест немного удивителен, учитывая результаты до сих пор.

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector3, 5, TRUE), cbGtools = gtools::permutations(10, 5, testVector3, repeats.allowed = TRUE), cbArrangements = permutations(x = testVector3, k = 5, replace = TRUE), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.106 0.9183 1.200 1.030 1.063 1.701 100 #> cbGtools 2.426 2.1815 2.068 1.996 2.127 1.367 100 #> cbArrangements 1.000 1.0000 1.000 1.000 1.000 1.000 100 

Это не опечатка ... gtools::permutations почти так же быстро, как и другие скомпилированные функции. Я рекомендую читателю проверить исходный код gtools::permutations поскольку он является одним из самых элегантных дисплеев программирования там ( R или иначе).

4. Мультисети

Сначала рассмотрим комбинации мультимножеств.

  1. RcppAlgos
  2. arrangements

Чтобы найти комбинации / перестановки мультимножеств, с помощью RcppAlgos используйте аргументы freqs чтобы указать, сколько раз повторяется каждый элемент вектора-источника v .

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(496) myFreqs < - sample(1:5, 10, replace = TRUE) ## This is how many times each element will be repeated myFreqs #> [1] 2 4 4 5 3 2 2 2 3 4 testVector4 < - as.integer(c(1, 2, 3, 5, 8, 13, 21, 34, 55, 89)) t1 <- comboGeneral(testVector4, 12, freqs = myFreqs) t3 <- combinations(freq = myFreqs, k = 12, x = testVector4) identical(t1, t3) #> [1] TRUE 

Ориентир:

 microbenchmark(cbRcppAlgos = comboGeneral(testVector4, 12, freqs = myFreqs), cbArrangements = combinations(freq = myFreqs, k = 12, x = testVector4), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.000 1.000 1.000 1.000 1.000 1.000 100 #> cbArrangements 1.254 1.221 1.287 1.259 1.413 1.173 100 

Для перестановок мультимножеств, выбранных m за раз, мы имеем:

  1. RcppAlgos
  2. arrangements

Как:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(8128) myFreqs < - sample(1:3, 5, replace = TRUE) testVector5 <- sort(runif(5)) myFreqs #> [1] 2 2 2 1 3 t1 < - permuteGeneral(testVector5, 7, freqs = myFreqs) t3 <- permutations(freq = myFreqs, k = 7, x = testVector5) identical(t1, t3) #> [1] TRUE 

Ориентир:

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector5, 7, freqs = myFreqs), cbArrangements = permutations(freq = myFreqs, k = 7, x = testVector5), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.461 1.327 1.282 1.177 1.176 1.101 100 #> cbArrangements 1.000 1.000 1.000 1.000 1.000 1.000 100 

Для перестановок мультимножеств, возвращающих все перестановки, имеем:

  1. RcppAlgos
  2. multicool
  3. arrangements

Как:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(8128) myFreqs2 < - c(2,1,2,1,2) testVector6 <- (1:5)^3 ## For multicool, you must have the elements explicitly repeated testVector6Prime <- rep(testVector6, times = myFreqs2) t3 <- multicool::allPerm(multicool::initMC(testVector6Prime)) ## for comparison t1 <- permuteGeneral(testVector6, freqs = myFreqs2) identical(t1[do.call(order,as.data.frame(t1)),], t3[do.call(order,as.data.frame(t3)),]) #> [1] TRUE 

Ориентир:

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector6, freqs = myFreqs2), cbMulticool = multicool::allPerm(multicool::initMC(testVector6Prime)), cbArrangements = permutations(freq = myFreqs2, x = testVector6), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.276 1.374 1.119 1.461 1.39 0.8856 100 #> cbMulticool 2434.652 2135.862 855.946 2026.256 1521.74 31.0651 100 #> cbArrangements 1.000 1.000 1.000 1.000 1.00 1.0000 100 

5. Резюме

Как gtools и combinat являются хорошо установленными пакетами для переупорядочения элементов вектора. С помощью gtools есть еще несколько опций (см. Обзор выше), и с combinat вы можете изменить factors . С multicool , один может переставить мультимножества. Хотя partitions и gRbase ограничены для целей этого вопроса, они являются силовыми структурами, снабженными высокоэффективными функциями для работы с разделами и объектами массива соответственно.

arrangements

  1. Вывод находится в порядке словаря.
  2. Позволяет пользователю указать формат с помощью аргумента layout ( r = row-major , c = column-major и l = list ).
  3. Предлагает удобные методы, такие как collect & getnext при работе с iteratorами.
  4. Позволяет генерировать более 2^31 - 1 комбинаций / перестановок через getnext . NB RcppAlgos (через lower/upper см. Ниже) и multicool (через nextPerm ) также способны это сделать.
  5. Говоря о getnext , эта функция позволяет получить определенное количество результатов, используя аргумент d .
  6. Поддерживает большие целые числа gmp для вычисления количества комбинаций / перестановок.

Заметим:

 library(arrangements) icomb < - icombinations(1000, 7) icomb$getnext(d = 5) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [1,] 1 2 3 4 5 6 7 #> [2,] 1 2 3 4 5 6 8 #> [3,] 1 2 3 4 5 6 9 #> [4,] 1 2 3 4 5 6 10 #> [5,] 1 2 3 4 5 6 11 

Эта функция очень приятная, когда вам нужно только несколько комбинаций / перестановок. С помощью традиционных методов вам нужно будет сгенерировать все комбинации / перестановки, а затем подмножество. Это сделало бы предыдущий пример невозможным, поскольку результаты более 10^17 (т. ncombinations(1000, 7, bigz = TRUE) = 194280608456793000).

Эта функция наряду с усовершенствованиями генераторов в arrangements , позволяет ей быть очень эффективной в отношении памяти.

RcppAlgos

  1. Вывод находится в порядке словаря.
  2. Есть удобные функции ограничения, которые мы не будем обсуждать здесь, поскольку они не соответствуют теме для этого вопроса. Я буду только отмечать, что проблемы, которые могут быть решены с помощью этих функций, были мотивацией для создания этого пакета.
  3. Существует аргумент upper (formally rowCap ), который аналогичен аргументу d getnext .

Заметим:

 library(RcppAlgos) comboGeneral(1000, 7, upper = 5) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [1,] 1 2 3 4 5 6 7 #> [2,] 1 2 3 4 5 6 8 #> [3,] 1 2 3 4 5 6 9 #> [4,] 1 2 3 4 5 6 10 #> [5,] 1 2 3 4 5 6 11 
  1. Кроме того, 2.0.0 с 2.0.0 , существует аргумент lower который позволяет начать генерировать при определенной комбинации / перестановке. Это прекрасно подходит для распараллеливания и позволяет быстро генерировать за 2^31 - 1 поскольку куски генерируются независимо.

Параллельный пример с более чем 6 миллиардами комбинаций:

 system.time(parallel::mclapply(seq(1,6397478649,4390857), function(x) { a < - comboGeneral(25, 15, freqs = c(rep(1:5, 5)), lower = x, upper = x + 4390856) ## do something x }, mc.cores = 7)) #> user system elapsed #> 510.623 140.970 109.496 

В случае, если вам интересно, как масштабируется каждый пакет, я оставлю вас с этим последним примером, который измеряет, насколько быстро каждый пакет может генерировать более 100 миллионов результатов (NB gtools::combinations здесь отсутствует, поскольку он будет gtools::combinations ошибку: evaluation nested too deeply... ). Кроме того, мы явно вызываем combn из пакета utils , потому что мне не удалось получить успешный запуск из combinat::combn . Различия в использовании памяти между этими двумя довольно странно, учитывая, что они незначительно отличаются (см. « ?utils::combn разделе «Авторы»).

Заметим:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(2187) testVector7 < - sort(sample(10^7, 10^3)) system.time(utils::combn(testVector7, 3)) #> user system elapsed #> 179.956 5.687 187.159 system.time(RcppAlgos::comboGeneral(testVector7, 3)) #> user system elapsed #> 1.136 0.758 1.937 system.time(arrangements::combinations(x = testVector7, k = 3)) #> user system elapsed #> 1.963 0.930 2.910 system.time(RcppAlgos::permuteGeneral(testVector7[1:500], 3)) #> user system elapsed #> 1.095 0.631 1.738 system.time(arrangements::permutations(x = testVector7[1:500], k = 3)) #> user system elapsed #> 1.399 0.584 1.993 

6. Память

При выполнении comboGeneral а также arrangements::combinations , память будет прыгать почти на 2 Gbs до вызова gc . Это кажется правильным: #rows * #nols * bytesPerCell / 2^30 bytes = choose(1000,3) * 3 * 4 / 2^30 bytes = (166167000 * 3 * 4)/2^30 = 1.857 Gbs ). Тем не менее, при выполнении combn поведение памяти было простым (например, иногда оно использовало бы все 16 ГБ памяти, а в других случаях оно было бы только на пару Gbs). Когда я тестировал это при настройке Windows, он часто падал.

Мы можем подтвердить это с помощью Rprof вместе с summaryRporf . Заметим:

 Rprof("RcppAlgos.out", memory.profiling = TRUE) t1 < - RcppAlgos::comboGeneral(testVector7, 3) Rprof(NULL) summaryRprof("RcppAlgos.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct "CombinatoricsRcpp" 1.2 100 1901.6 1.2 100 "RcppAlgos::comboGeneral" 1.2 100 1901.6 0.0 0 Rprof("arrangements.out", memory.profiling = TRUE) t3 <- arrangements::combinations(10^3, 3, testVector7) Rprof(NULL) summaryRprof("arrangements.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct ".Call" 2.08 99.05 1901.6 2.08 99.05 

С RcppAlgos и arrangements mem.total регистрирует чуть более 1900 Mb .

И вот профиль памяти на меньшем векторе, сравнивающий gtools , utils и combinat .

 testVector7Prime < - testVector7[1:300] Rprof("combinat.out", memory.profiling = TRUE) t3 <- combinat::combn(testVector7Prime, 3) Rprof(NULL) summaryRprof("combinat.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct "combinat::combn" 3.98 100.00 1226.9 3.72 93.47 Rprof("utils.out", memory.profiling = TRUE) t4 <- utils::combn(testVector7Prime, 3) Rprof(NULL) summaryRprof("utils.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct "utils::combn" 2.52 100.00 1952.7 2.50 99.21 Rprof("gtools.out", memory.profiling = TRUE) t5 <- gtools::combinations(300, 3, testVector7Prime) Rprof(NULL) summaryRprof("gtools.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct "rbind" 4.94 95.00 6741.6 4.40 84.62 

Интересно, что utils::combn и combinat::combn используют разные объемы памяти и выполняют разные промежутки времени для выполнения. Это не задерживается с меньшими векторами:

 microbenchmark(combinat::combn(2:13, 6), utils::combn(2:13, 6)) Unit: microseconds expr min lq mean median uq max neval combinat::combn(2:13, 6) 527.378 567.946 629.1268 577.163 604.3270 1816.744 100 utils::combn(2:13, 6) 663.150 712.872 750.8008 725.716 771.1345 1205.697 100 

И с помощью gtools общая используемая память немного больше 3x, чем utils . Следует отметить, что для этих 3 пакетов я получал разные результаты каждый раз, когда я их запускал (например, для combinat::combn иногда я получал 9000 Мб, а затем получаю 13000 Мб).

Тем не менее, ни один из них не может соответствовать RcppAlgos OR . Оба используют только 51 Мб при запуске в примере выше.

контрольный сценарий: https://gist.github.com/randy3k/bd5730a6d70101c7471f4ae6f453862e (вынесенный https://github.com/tidyverse/reprex )

*: Посвящение А Прогулка по комбинаторике Миклоша Боны

Давайте будем гением компьютера.