2

今天早些时候，我问是否有一种惯用的方法来计算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 PrimeQ 谓词

这很奇怪。一切都颠倒了。我不怀疑缓存是这里的罪魁祸首，因为最差的值是最后计算的函数。

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

4

2 回答 2

1

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

首先，对于Listable诸如EvenQandPrimeQ之类的功能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编译，这是一个不错的选择。

以下是使用数字函数进行快速计数的其他一些示例。

于 2012-04-27T21:19:58.933 回答
1

列表中整数的性质会对可实现的时序产生重大影响。如果整数的范围受到限制，使用Tally可以提高性能。

(* Count items in the list matching predicate, pred *)

PredCountID[lst_, pred_] := 
Select[Tally@lst, pred@First@# &]\[Transpose] // Last // Total

(* Define the values over which to check timings  *)
ranges = {100, 1000, 10000, 100000, 1000000};
sizes = {100, 1000, 10000, 100000, 1000000, 10000000,100000000};

对于 PrimeQ，此函数给出以下时间：

数学图形

Timing表明即使在 10^8 大小的列表中，如果素数来自整数集合 {0,...,100000} 并且低于分辨率在一个很小的范围内，例如 1 到 100。

因为谓词只需要应用于一组Tally值，这种方法对确切的谓词函数相对不敏感。

于 2012-04-28T12:57:25.543 回答