performance - 在 R 中交叉制表两个大量逻辑向量的最快方法

Question

对于长度 > 1E8 的两个逻辑向量 x 和 y ，计算 2x2 交叉表的最快方法是什么？

我怀疑答案是用 C/C++ 编写它，但我想知道 R 中是否有一些东西已经很聪明地解决了这个问题，因为它并不少见。

示例代码，对于 300M 条目(如果 3E8 太大，请随意让 N = 1E8；我选择的总大小略低于 2.5GB(2.4GB)。我的目标是 0.02 的密度，只是为了让它更有趣(可以如果有帮助，请使用稀疏向量，但类型转换可能需要时间)。

set.seed(0)
N = 3E8
p = 0.02
x = sample(c(TRUE, FALSE), N, prob = c(p, 1-p), replace = TRUE)
y = sample(c(TRUE, FALSE), N, prob = c(p, 1-p), replace = TRUE)

一些明显的方法:

table

bigtabulate

简单的逻辑运算(例如 sum(x & y) )

矢量乘法 (boo)

data.table

以上部分，parallel 来自 multicore 包(或新的 parallel 包)

我已经尝试了前三个选项(请参阅我的答案)，但我觉得必须有更好更快的方法。

我发现 table 工作非常缓慢。 bigtabulate 对于一对逻辑向量来说似乎有点矫枉过正。最后，做普通的逻辑运算似乎很麻烦，它查看每个向量的次数太多(3X？7X？)，更不用说它在处理过程中填充了大量额外的内存，这是一种大量的时间浪费。

向量乘法通常是一个坏主意，但是当向量稀疏时，可以通过将其存储为这样的方式然后使用向量乘法来获得优势。

随意更改 N 和 p ，如果这将展示制表函数的任何有趣行为。 :)

更新 1. 我的第一个答案给出了三种幼稚方法的计时，这是相信 table 很慢的基础。然而，要意识到的关键是“逻辑”方法效率极低。看看它在做什么:

4 个逻辑向量运算

4 次类型转换(逻辑到整数或 FP - 对于 sum )

4 个向量求和

8 个赋值(1 个用于逻辑运算，1 个用于求和)

不仅如此，它甚至没有被编译或并行化。然而，它仍然击败了 table 的裤子。请注意， bigtabulate 和额外的类型转换( 1 * cbind... )仍然胜过 table 。

更新 2。以免有人指出 R 中的逻辑向量支持 NA ，这将成为这些交叉表的系统中的 Spanner (在大多数情况下是正确的)，我应该指出我的向量来自 is.na() 或 is.finite() . :) 我一直在调试 NA 和其他非有限值 - they've been a headache for me recently 。如果您不知道您的所有条目是否都是 NA ，您可以使用 any(is.na(yourVector)) 进行测试 - 在您采用本问答中出现的一些想法之前，这样做是明智的。

更新 3. Brandon Bertelsen 在评论中提出了一个非常合理的问题:为什么在子样本(毕竟，初始集是一个样本 ;-))可能足以创建交叉样本的情况下使用这么多数据？制表？不要在统计中漂移太远，但数据来自两个变量的 TRUE 观测值非常罕见的情况。一个是数据异常的结果，另一个是由于代码中可能存在的错误(可能是错误，因为我们只看到计算结果 - 将变量 x 视为“垃圾输入”，将 y 视为“垃圾输出”。作为结果，问题是代码导致的输出问题是否仅仅是数据异常的情况，还是存在其他一些好的数据变坏的情况？(这就是为什么我问了一个关于 stopping when a NaN , NA , or Inf is encountered 的问题。)

这也解释了为什么我的示例对于 TRUE 值的概率很低；这些实际发生的概率远低于 0.1%。

这是否暗示了不同的解决方案路径？是的:这表明我们可以使用两个索引(即每个集合中 TRUE 的位置)并计算集合交集。我避免了集合交集，因为我被 Matlab 烧了一段时间(是的，这是 R，但请耐心等待)，它会在进行交集之前先对集合的元素进行排序。 (我依稀记得复杂度更令人尴尬:比如 O(n^2) 而不是 O(n log n) 。)

Answer 1

如果您正在对巨大的逻辑向量进行大量操作，请查看 bit包裹。它通过将 bool 值存储为真正的 1 位 bool 值来节省大量内存。

这对 table 没有帮助;它实际上使情况变得更糟，因为由于其构造方式，位向量中有更多的唯一值。但它确实有助于逻辑比较。

# N <- 3e7
require(bit)
xb <- as.bit(x)
yb <- as.bit(y)
benchmark(replications = 1, order = "elapsed", 
    bit = {res <- func_logical(xb,yb)},
    logical = {res <- func_logical(x,y)}
)
#      test replications elapsed relative user.self sys.self user.child sys.child
# 1     bit            1   0.129  1.00000     0.132    0.000          0         0
# 2 logical            1   3.677 28.50388     2.684    0.928          0         0