wolfram-mathematica - 计算与谓词匹配的元素的最快方法

Question

今天早些时候我问是否有 idiomatic way to count elements matching predicate Mathematica 中的函数，因为我关心性能。

我对给定谓词的初始方法 pred如下:

PredCount1[lst_, pred_] := Length@Select[lst, pred];

我收到了改用的建议

PredCount2[lst_, pred_] := Count[lst, x_/;pred@x];

我开始分析这些函数，使用不同的 lst尺寸和pred函数，并添加了两个定义:

PredCount3[lst_, pred_] := Count[Thread@pred@lst, True];
PredCount4[lst_, pred_] := Total[If[pred@#, 1, 0] & /@ lst];

我的数据样本范围在 1 到 1000 万个元素之间，我的测试函数是 EvenQ , #<5&和PrimeQ 。下图显示了所花费的时间。

EvenQ

PredCount2 最慢，3 和 4 不相上下。

比较谓词:#<5&

我选择了这个函数，因为它接近我实际问题所需的功能。不要担心这是一个愚蠢的测试函数，它实际上证明了第四个函数有一些优点，我实际上最终在我的解决方案中使用了它。

与 EvenQ 相同，但 3 明显比 4 慢。

PrimeQ

这太奇怪了。一切都翻转了。我并不怀疑缓存是罪魁祸首，因为最差的值是最后计算的函数的值。

那么，计算列表中与给定谓词函数匹配的元素数量的正确(最快)方法是什么？

Answer 1

您正在看到自动编译的结果。

首先，对于 Listable 函数(例如 EvenQ 和 PrimeQ)，不需要使用 Thread:

EvenQ[{1, 2, 3}]

{False, True, False}

这也解释了为什么 PredCount3 在这些函数上表现良好。 (它们针对列表上的线程进行了内部优化。)

现在让我们看看时间安排。

dat = RandomInteger[1*^6, 1*^6];

test = # < 5 &;

First@Timing[#[dat, test]] & /@ {PredCount1, PredCount2, PredCount3, PredCount4}

{0.343, 0.437, 0.25, 0.047}

如果我们更改系统选项以防止 Map 内自动编译并再次运行测试:

SetSystemOptions["CompileOptions" -> {"MapCompileLength" -> Infinity}]

First@Timing[#[dat, test]] & /@ {PredCount1, PredCount2, PredCount3, PredCount4}

{0.343, 0.452, 0.234, 0.765}

您可以清楚地看到，如果不编译，PredCount4 会慢得多。简而言之，如果您的测试函数可以由 Mathematica 编译，那么这是一个不错的选择。

Here are some other examples of fast counting using numeric functions.