2

今日の初めに、私はパフォーマンスに関心があったので、Mathematica で述語関数に一致する要素をカウントする慣用的な方法があるかどうかを尋ねました。

特定の述語に対する私の最初のアプローチpredは次のとおりです。

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

代わりに使用する提案を得ました

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

これらの関数のプロファイリングをさまざまなlstサイズとpred関数で開始し、さらに 2 つの定義を追加しました。

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

データ サンプルは 100 万から 1000 万要素の範囲で、テスト関数はとEvenQでした。次のグラフは、所要時間を示しています。#<5&PrimeQ

イーブンQ EvenQ 述語

PredCount2 が最も遅く、3 と 4 で十分です。

比較述語: #<5&

実際の問題で必要なものに近いため、この関数を選択しました。これがばかげたテスト関数であることを心配しないでください。実際には、4 番目の関数に何らかのメリットがあることが証明されており、実際にソリューションで使用することになりました。

5 つ未満の述語

と同じEvenQですが、3 は 4 より明らかに遅いです。

プライムQ PrimeQ述語

これは奇妙です。すべてがひっくり返る。最悪の値は最後に計算された関数に対するものであるため、ここでの原因としてキャッシングを疑っていません。

では、特定の述語関数に一致するリスト内の要素の数を数える正しい (最速の) 方法は何ですか?

4

2 に答える 2

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 の場合、この関数は次のタイミングを提供します。

Mathematica グラフィックス

サイズが 10^8 のリストであっても、素数が {0,...,100000} の整数のセットからのものである場合、10 分の 1 秒未満で素数をカウントできることを示してTimingいます。 1 ～ 100 などの小さな範囲内。

述語は一連の値にのみ適用する必要があるためTally、このアプローチは正確な述語関数に比較的影響されません。

于 2012-04-28T12:57:25.543 に答える
1

自動コンパイルの結果が表示されています。

まず、andのListableような関数の使用は不要です。EvenQPrimeQThread

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 に答える