浏览 R* 中的组合数学片段
下面,我们检查具有生成组合和排列功能的包。如果我遗漏了任何包裹,请原谅我,并请发表评论,或者更好的是,编辑这篇文章。
分析概要:
- 介绍
- Setup
- 组合
- 排列
- 多组
- Summary
- Memory
在开始之前,我们注意到组合/排列with替换所选的不同项目和非不同项目m一次是等价的。之所以如此,是因为我们什么时候有替换,它是不具体的。因此,无论特定元素最初出现多少次,输出都会有该元素的实例重复 1 到m times.
一、简介
套餐:
gtools
combinat
multicool
partitions
RcppAlgos
arrangements
utils
我没有包括permute
or permutations
因为它们并不是真正要解决这些类型的问题。我也没有包括更新的gRbase
因为某些情况下我的电脑崩溃了。
|——————————————OVERVIEW————————————-|
|_________________| 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 | Yes |
| comb multiset | | | | |
| accepts factors | | Yes | | |
| m at a time | Yes | Yes/No | | |
| general vector | Yes | Yes | Yes | |
| iterable | | | Yes | |
| parallelizable | | | | |
| multi-threaded | | | | |
| big integer | | | | |
|_________________| arrangements | RcppAlgos | utils |
| comb rep | Yes | Yes | |
| comb NO rep | Yes | Yes | Yes |
| perm rep | Yes | Yes | |
| perm NO rep | Yes | Yes | |
| perm multiset | Yes | Yes | |
| comb multiset | Yes | Yes | |
| accepts factors | Yes | Yes | Yes |
| m at a time | Yes | Yes | Yes |
| general vector | Yes | Yes | Yes |
| iterable | Yes | Yes | |
| parallelizable | Yes | Yes | |
| big integer | Yes | Yes | |
| multi-threaded | | Yes | |
任务,m at a time
and general vector
,指的是产生结果的能力“m一次”并重新排列“通用向量”,而不是1:n
。在实践中,我们通常关心的是寻找通用向量的重排,因此下面的所有检查将尽可能反映这一点。
2. Setup
所有基准测试均在 3 种不同的设置上运行。
- 2022 年 Macbook Air 苹果 M2 24 GB
- 2020 年 Macbook Pro i7 16 GB
- 2022 年 Windows Surface i5 16 GB
library(microbenchmark)
## print up to 4 digits to keep microbenchmark output tidy
options(digits = 4)
options(width = 90)
numThreads <- min(as.integer(RcppAlgos::stdThreadMax() / 2), 6)
numThreads
#> [1] 4
pkgs <- c("gtools", "combinat", "multicool", "partitions",
"RcppAlgos", "arrangements", "utils", "microbenchmark")
sapply(pkgs, packageVersion, simplify = FALSE)
#> $gtools
#> [1] '3.9.3'
#>
#> $combinat
#> [1] '0.0.8'
#>
#> $multicool
#> [1] '0.1.12'
#>
#> $partitions
#> [1] '1.10.7'
#>
#> $RcppAlgos
#> [1] '2.6.0'
#>
#> $arrangements
#> [1] '1.1.9'
#>
#> $utils
#> [1] '4.2.1'
#>
#> $microbenchmark
#> [1] '1.4.7'
列出的结果是从设置 #1(即 Macbook Air M2)获得的。 Macbook Pro 上的结果类似,但在 Windows 设置中,多线程效果较差。在某些情况下,在 Windows 设置中,串行执行速度更快。我们将使用该模式调用所有函数package::function
so no library
需要打电话。
3. 组合
首先,我们检查没有选择替换的组合m一次。
RcppAlgos
combinat
gtools
arrangements
utils
How to:
set.seed(13)
tVec1 <- sort(sample(100, 20))
m <- 10
t1 <- RcppAlgos::comboGeneral(tVec1, m) ## returns matrix with m columns
t3 <- combinat::combn(tVec1, m) ## returns matrix with m rows
t4 <- gtools::combinations(20, m, tVec1) ## returns matrix with m columns
identical(t(t3), t4) ## must transpose to compare
#> [1] TRUE
t5 <- arrangements::combinations(tVec1, m)
identical(t1, t5)
#> [1] TRUE
t6 <- utils::combn(tVec1, m) ## returns matrix with m rows
identical(t(t6), t4) ## must transpose to compare
#> [1] TRUE
基准:
microbenchmark(
cbRcppAlgosPar = RcppAlgos::comboGeneral(tVec1, m,
nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::comboGeneral(tVec1, m),
cbGtools = gtools::combinations(20, m, tVec1),
cbCombinat = combinat::combn(tVec1, m),
cbUtils = utils::combn(tVec1, m),
cbArrangements = arrangements::combinations(tVec1, m),
unit = "relative"
)
#> Warning in microbenchmark(cbRcppAlgosPar = RcppAlgos::comboGeneral(tVec1, : less accurate
#> nanosecond times to avoid potential integer overflows
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 100
#> cbRcppAlgosSer 2.712 2.599 1.280 2.497 2.477 0.2666 100
#> cbGtools 739.325 686.803 271.623 679.894 661.560 11.7178 100
#> cbCombinat 173.836 166.265 76.735 176.052 191.945 4.9075 100
#> cbUtils 179.895 170.345 71.639 169.661 178.385 3.8900 100
#> cbArrangements 2.717 2.995 1.975 2.835 2.935 0.8195 100
现在,我们检查选择的替换组合m一次。
RcppAlgos
gtools
arrangements
How to:
set.seed(97)
tVec2 <- sort(rnorm(12))
m <- 9
t1 <- RcppAlgos::comboGeneral(tVec2, m, repetition = TRUE)
t3 <- gtools::combinations(12, m, tVec2, repeats.allowed = TRUE)
identical(t1, t3)
#> [1] TRUE
t4 <- arrangements::combinations(tVec2, m, replace = TRUE)
identical(t1, t4)
#> [1] TRUE
基准:
microbenchmark(
cbRcppAlgosPar = RcppAlgos::comboGeneral(tVec2, m, TRUE,
nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::comboGeneral(tVec2, m, TRUE),
cbGtools = gtools::combinations(12, m, tVec2, repeats.allowed = TRUE),
cbArrangements = arrangements::combinations(tVec2, m, replace = TRUE),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.0000 1.000 1.0000 1.0000 100
#> cbRcppAlgosSer 1.987 2.382 0.9173 2.347 1.2776 0.9733 100
#> cbGtools 670.126 517.561 103.8726 523.135 177.0940 12.0440 100
#> cbArrangements 2.300 2.582 0.8294 2.542 0.9212 1.0089 100
4. 排列
首先,我们检查没有选择替换的排列m一次。
RcppAlgos
gtools
arrangements
How to:
tVec3 <- as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
t1 <- RcppAlgos::permuteGeneral(tVec3, 6)
t3 <- gtools::permutations(10, 6, tVec3)
identical(t1, t3)
#> [1] TRUE
t4 <- arrangements::permutations(tVec3, 6)
identical(t1, t4)
#> [1] TRUE
基准:
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(tVec3, 6,
nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec3, 6),
cbGtools = gtools::permutations(10, 6, tVec3),
cbArrangements = arrangements::permutations(tVec3, 6),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 100
#> cbRcppAlgosSer 1.204 1.553 1.522 1.523 1.509 0.5722 100
#> cbGtools 357.078 308.978 288.396 301.611 292.862 64.8564 100
#> cbArrangements 2.356 2.361 2.183 2.292 2.224 0.4605 100
接下来,我们检查排列,而不用通用向量替换(返回所有排列)。
RcppAlgos
gtools
combinat
multicool
arrangements
How to:
tVec3Prime <- tVec3[1:9]
## For RcppAlgos, arrangements, & gtools (see above)
t4 <- combinat::permn(tVec3Prime) ## returns a list of vectors
## convert to a matrix
t4 <- do.call(rbind, t4)
t5 <- multicool::allPerm(multicool::initMC(tVec3Prime)) ## 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(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(tVec3Prime,
nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec3Prime),
cbGtools = gtools::permutations(9, 9, tVec3Prime),
cbCombinat = combinat::permn(tVec3Prime),
cbMulticool = multicool::allPerm(multicool::initMC(tVec3Prime)),
cbArrangements = arrangements::permutations(tVec3Prime),
times = 25,
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0 25
#> cbRcppAlgosSer 1.555 2.187 2.616 2.190 2.274 10.3 25
#> cbGtools 1913.125 1850.589 1893.918 1877.707 1915.601 2124.5 25
#> cbCombinat 508.360 512.182 562.042 532.123 595.722 715.3 25
#> cbMulticool 103.061 103.694 128.480 118.169 127.118 208.3 25
#> cbArrangements 3.216 3.583 13.566 3.544 3.561 139.2 25
现在,我们检查排列而不用替换1:n
(返回所有排列)。
RcppAlgos
gtools
combinat
multicool
partitions
arrangements
How to:
t1 <- partitions::perms(9) ## returns an object of type 'partition' with n rows
identical(t(as.matrix(t1)), RcppAlgos::permuteGeneral(9))
#> [1] TRUE
基准:
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(9, nThreads = numThreads),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(9),
cbGtools = gtools::permutations(9, 9),
cbCombinat = combinat::permn(9),
cbMulticool = multicool::allPerm(multicool::initMC(1:9)),
cbPartitions = partitions::perms(9),
cbArrangements = arrangements::permutations(9),
times = 25,
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 25
#> cbRcppAlgosSer 1.583 2.218 2.587 2.261 2.591 1.814 25
#> cbGtools 2010.303 1855.443 1266.853 1898.458 1903.055 217.422 25
#> cbCombinat 511.196 515.197 392.252 533.737 652.125 86.305 25
#> cbMulticool 108.152 103.188 80.469 108.227 120.804 23.504 25
#> cbPartitions 6.139 6.018 7.167 5.993 6.403 9.446 25
#> cbArrangements 4.089 3.797 3.135 3.791 3.760 1.858 25
最后,我们检查替换排列。
RcppAlgos
gtools
arrangements
How to:
t1 <- RcppAlgos::permuteGeneral(tVec3, 5, repetition = TRUE)
t3 <- gtools::permutations(10, 5, tVec3, repeats.allowed = TRUE)
t4 <- arrangements::permutations(x = tVec3, k = 5, replace = TRUE)
identical(t1, t3)
#> [1] TRUE
identical(t1, t4)
#> [1] TRUE
考虑到到目前为止的结果,下一个基准有点令人惊讶。
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(
tVec3, 5, TRUE, nThreads = numThreads
),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec3, 5, TRUE),
cbGtools = gtools::permutations(10, 5, tVec3, repeats.allowed = TRUE),
cbArrangements = arrangements::permutations(tVec3, 5, replace = TRUE),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 100
#> cbRcppAlgosSer 1.307 1.669 1.465 1.561 1.513 1.015 100
#> cbGtools 6.364 6.188 5.448 5.762 5.434 1.625 100
#> cbArrangements 2.584 2.442 1.824 2.265 2.135 0.117 100
这不是一个错字……gtools::permutations
几乎与其他编译函数一样快。我鼓励读者去查看源代码gtools::permutations
因为它是最优雅的编程展示之一(R
或其他)。
5. 多组训练
首先,我们检查多重集的组合。
RcppAlgos
arrangements
要查找多重集的组合/排列,使用RcppAlgos
使用freqs
参数指定源向量每个元素的次数,v
,重复。
set.seed(496)
myFreqs <- sample(1:5, 12, replace = TRUE)
## This is how many times each element will be repeated
tVec4 <- as.integer(c(1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233))
t1 <- RcppAlgos::comboGeneral(tVec4, 12, freqs = myFreqs)
t3 <- arrangements::combinations(tVec4, 12, freq = myFreqs)
identical(t1, t3)
#> [1] TRUE
基准:
microbenchmark(
cbRcppAlgosPar = RcppAlgos::comboGeneral(
tVec4, 12, freqs = myFreqs, nThreads = numThreads
),
cbRcppAlgosSer = RcppAlgos::comboGeneral(tVec4, 12, freqs = myFreqs),
cbArrangements = arrangements::combinations(tVec4, 12, freq = myFreqs),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 100
#> cbRcppAlgosSer 3.197 3.012 2.003 2.831 2.681 0.1658 100
#> cbArrangements 9.391 7.830 4.901 7.252 6.731 0.3140 100
对于所选多重集的排列m一次,我们有:
RcppAlgos
arrangements
How to:
set.seed(123)
tVec5 <- sort(runif(5))
t1 <- RcppAlgos::permuteGeneral(tVec5, 8, freqs = rep(4, 5))
t3 <- arrangements::permutations(tVec5, 8, freq = rep(4, 5))
identical(t1, t3)
#> [1] TRUE
基准:
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(
tVec5, 8, freqs = rep(4, 5), nThreads = numThreads
),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec5, 8, freqs = rep(4, 5)),
cbArrangements = arrangements::permutations(tVec5, 8, freq = rep(4, 5)),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 100
#> cbRcppAlgosSer 3.336 3.326 2.990 3.330 3.517 2.106 100
#> cbArrangements 3.751 3.746 3.346 3.757 3.840 2.305 100
对于返回所有排列的多重集排列,我们有:
RcppAlgos
multicool
partitions
arrangements
How to:
tVec6 <- (1:5)^3
## For multicool, you must have the elements explicitly repeated
tVec6Prime <- rep(tVec6, times = rep(2, 5))
## for comparison
t1 <- RcppAlgos::permuteGeneral(tVec6, freqs = rep(2, 5))
t2 <- partitions::multiset(tVec6Prime)
t3 <- multicool::allPerm(multicool::initMC(tVec6Prime))
t4 <- arrangements::permutations(tVec6, freq = rep(2, 5))
## the package partitions, returns class of integer
## whereas RcppAlgos preserves class of tVec6 (i.e. numeric)
all.equal(t1, t(as.matrix(t2)))
#> [1] TRUE
identical(t1[do.call(order,as.data.frame(t1)),],
t3[do.call(order,as.data.frame(t3)),])
#> [1] TRUE
identical(t1, t4)
#> [1] TRUE
基准:
microbenchmark(
cbRcppAlgosPar = RcppAlgos::permuteGeneral(
tVec6, freqs = rep(2, 5), nThreads = numThreads
),
cbRcppAlgosSer = RcppAlgos::permuteGeneral(tVec6, freqs = rep(2, 5)),
cbMulticool = multicool::allPerm(multicool::initMC(tVec6Prime)),
cbPartitions = partitions::multiset(tVec6Prime),
cbArrangements = arrangements::permutations(tVec6, freq = rep(2, 5)),
unit = "relative"
)
#> Unit: relative
#> expr min lq mean median uq max neval
#> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 100
#> cbRcppAlgosSer 2.485 2.141 2.289 2.584 2.511 1.0250 100
#> cbMulticool 80.195 66.237 45.540 64.971 66.057 3.5655 100
#> cbPartitions 5.731 4.786 3.925 4.719 4.953 0.4558 100
#> cbArrangements 2.999 2.907 3.270 2.966 2.906 3.1214 100
六、总结
Both gtools
and combinat
是用于重新排列向量元素的成熟包。和gtools
还有更多选项(请参阅上面的概述)以及combinat
,你可以重新排列factors
. With multicool
,一个人能够重新排列多重集。虽然partitions
就这个问题而言,它是有限的,但它是一个强大的功能,包含处理整数分区的高效函数。
arrangements
- 输出按字典顺序排列。
- 允许用户通过指定格式
layout
参数(“行:行优先”、“列:列优先”和“列表:列表”)。
- 提供便捷的方法,例如
collect
& getnext
使用迭代器时。
- 允许生成超过
2^31 - 1
组合/排列通过getnext
. N.B. RcppAlgos
(via nextItem
) and multicool
(via nextPerm
)也有能力做到这一点。
- GMP 支持允许探索载体的组合/排列并产生多种结果。
Observe:
icomb <- arrangements::icombinations(1000, 7)
icomb$getnext()
#> [1] 1 2 3 4 5 6 7
icomb$getnext(d = 5)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,] 1 2 3 4 5 6 8
#> [2,] 1 2 3 4 5 6 9
#> [3,] 1 2 3 4 5 6 10
#> [4,] 1 2 3 4 5 6 11
#> [5,] 1 2 3 4 5 6 12
当您只需要一些组合/排列时,此功能非常好。使用传统方法,您必须生成所有组合/排列,然后生成子集。这将使前面的示例变得不可能,因为有多个10^17
结果(即ncombinations(1000, 7, bigz = TRUE)
= 194280608456793000)。
此功能以及对生成器的改进arrangements
,使其在内存方面非常高效。
RcppAlgos
- 输出按字典顺序排列。
- 有一些方便的约束特征,我们不会在这里讨论,因为它们与这个问题无关。我只会指出,利用这些功能可以解决的问题类型是创建这个包的动机(分区、子集和等)。
- GMP 支持允许探索载体的组合/排列并产生多种结果。
- 使用并行产生结果
Parallel
or nThreads
论据。
- 如同
combn
,有一个FUN
将函数应用于每个结果的参数(另请参阅FUN.VALUE
).
- Provides flexible and merory efficient iterators that allow for bidirectional iteration as well as random access.
-
nextItem
|nextNIter
|nextRemaining
: 检索next词典结果
-
prevItem
|prevNIter
|prevRemaining
: 检索previous词典结果
-
front
|back
|[[
:随机访问方法
- 允许轻松生成超过
2^31 - 1
任何起点的结果。
Observe:
iter <- RcppAlgos::comboIter(1000, 7)
# first combinations
iter@nextIter()
#> [1] 1 2 3 4 5 6 7
# next 5 combinations
iter@nextNIter(5)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,] 1 2 3 4 5 6 8
#> [2,] 1 2 3 4 5 6 9
#> [3,] 1 2 3 4 5 6 10
#> [4,] 1 2 3 4 5 6 11
#> [5,] 1 2 3 4 5 6 12
# from the current state, the previous combination
iter@prevIter()
#> [1] 1 2 3 4 5 6 11
# the last combination
iter@back()
#> [1] 994 995 996 997 998 999 1000
# the 5th combination
iter[[5]]
#> [1] 1 2 3 4 5 6 11
# you can even pass a vector of indices
iter[[c(1, 3, 5)]]
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,] 1 2 3 4 5 6 7
#> [2,] 1 2 3 4 5 6 9
#> [3,] 1 2 3 4 5 6 11
# start iterating from any index
iter[[gmp::pow.bigz(2, 31)]]
#> [1] 1 2 3 17 138 928 954
# get useful info about the current state
iter@summary()
#> $description
#> [1] "Combinations of 1000 choose 7"
#>
#> $currentIndex
#> Big Integer ('bigz') :
#> [1] 2147483648
#>
#> $totalResults
#> Big Integer ('bigz') :
#> [1] 194280608456793000
#>
#> $totalRemaining
#> Big Integer ('bigz') :
#> [1] 194280606309309352
## get next ieteration
iter@nextIter()
#> [1] 1 2 3 17 138 928 955
如果您想知道每个包的扩展方式,我将为您提供最后一个示例,用于衡量速度RcppAlgos
和arrangements
包可以生成超过 1 亿个结果。笔记,gtools::combinations
此处省略,因为它会抛出错误:evaluation nested too deeply...
。我们也省略了combn
因为它需要相当长的时间来执行。奇怪的是,两者之间的内存使用差异utils::combn
and combinat::combn
考虑到它们只是略有不同,这是相当奇怪的(参见?utils::combn
在“作者”部分下)。
Observe:
set.seed(2187)
tVec7 <- sort(sample(10^7, 10^3))
## 166,167,000 Combinations
system.time(RcppAlgos::comboGeneral(tVec7, 3))
#> user system elapsed
#> 0.386 0.105 0.490
system.time(arrangements::combinations(x = tVec7, k = 3))
#> user system elapsed
#> 0.439 0.105 0.545
## 124,251,000 Permuations
system.time(RcppAlgos::permuteGeneral(tVec7[1:500], 3))
#> user system elapsed
#> 0.141 0.076 0.218
system.time(arrangements::permutations(x = tVec7[1:500], k = 3))
#> user system elapsed
#> 0.386 0.077 0.463
7. 记忆
执行时comboGeneral
也arrangements::combinations
,调用前内存会跳近2Gbsgc
。这似乎是正确的#rows * #nols * bytesPerCell / 2^30 bytes = choose(1000,3) * 3 * 4 / 2^30 bytes = (166167000 * 3 * 4)/2^30 = 1.857 Gbs
)。但是,执行时combn
,内存行为不稳定(例如,有时它会使用全部 16 Gb 内存,而其他时候它只会激增几 Gb)。当我在 Windows 设置上对此进行测试时,它经常会崩溃。
我们可以使用以下方法确认这一点Rprof
随着summaryRporf
。观察:
Rprof("RcppAlgos.out", memory.profiling = TRUE)
t1 <- RcppAlgos::comboGeneral(tVec7, 3)
Rprof(NULL)
head(summaryRprof("RcppAlgos.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "RcppAlgos::comboGeneral" 0.42 100 1902 0.42 100
Rprof("arrangements.out", memory.profiling = TRUE)
t3 <- arrangements::combinations(tVec7, 3)
Rprof(NULL)
head(summaryRprof("arrangements.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "arrangements::combinations" 0.5 100 1902 0.5 100
With RcppAlgos
& arrangements
, mem.total
注册刚刚结束1900 Mb
.
这是较小向量上的内存配置文件。
tVec7Prime <- tVec7[1:300]
Rprof("combinat.out", memory.profiling = TRUE)
t3 <- combinat::combn(tVec7Prime, 3)
Rprof(NULL)
head(summaryRprof("combinat.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "combinat::combn" 2.1 100 1055 1.98 94.29
Rprof("utils.out", memory.profiling = TRUE)
t4 <- utils::combn(tVec7Prime, 3)
Rprof(NULL)
head(summaryRprof("utils.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "utils::combn" 1.6 100 2059 1.6 100
Rprof("gtools.out", memory.profiling = TRUE)
t5 <- gtools::combinations(300, 3, tVec7Prime)
Rprof(NULL)
head(summaryRprof("gtools.out", memory = "both")$by.total, n = 1)
#> total.time total.pct mem.total self.time self.pct
#> "rbind" 1.62 100 6659 1.46 90.12
有趣的是,utils::combn
and 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) 313.4 326.7 329.4 328.1 330.4 370.6 100
#> utils::combn(2:13, 6) 378.3 393.1 397.0 395.2 399.2 451.2 100
与gtools
使用的总内存略多于 3 倍utils
。应该注意的是,对于这 3 个包,我每次运行它们时都会得到不同的结果(例如combinat::combn
有时我会得到 9000 Mb,然后我会得到 13000 Mb)。
仍然无人可比RcppAlgos
OR arrangements
。在上面的示例中运行时,两者仅使用 51 Mb。
基准测试脚本:https://github.com/jwood000/RcppAlgos/blob/main/scripts/SO_Comb_Perm_in_R.R https://github.com/jwood000/RcppAlgos/blob/main/scripts/SO_Comb_Perm_in_R.R
*: An homage to A Walk through Combinatorics by Miklós Bóna