7

統計物理学のモデルの分配関数を計算するために Haskell を試しています。これには、構成の非常に大きなリストをトラバースし、さまざまなオブザーバブルを合計することが含まれます。これは、可能な限り効率的に行いたいと考えています。

私のコードの現在のバージョンはここにあります: https://gist.github.com/2420539

構成を列挙するためにリストとベクトルのどちらかを選択しようとすると、いくつかの奇妙なことが起こります。特に、リストを切り詰めるには、V.toList . V.take (3^n) . V.fromList(where Vis Data.Vector) を使用する方が を使用するよりも高速ですがtake、これは少し直感に反するように感じます。どちらの場合も、リストは遅延評価されます。

リスト自体はiterate;を使用して作成されます。代わりにVectors を可能な限り使用し、 を使用してリストを作成するとV.iterateN、再び遅くなります ...

私の質問は、どれが最も速いかを予測する方法 (スプライシングV.toListとコード内のランダムな場所以外) はありますか? V.fromList(ところで、ghc -O2現在の安定版を使用してすべてをコンパイルします。)

4

1 に答える 1

12

ベクトルは正格で、O(1)個のサブセットがあります (例: take )。また、最適化された挿入と削除もあります。そのため、データ構造をオンザフライで切り替えることで、パフォーマンスが向上することがあります。ただし、これは通常、間違ったアプローチです。すべてのデータをいずれかの形式で保持する方が適切です。(そして、UArrays も使用しています - 問題をさらに混乱させます)。

一般的なルール：

  • データが大きく、一括でのみ変換される場合は、ベクトルのような高密度で効率的な構造を使用するのが理にかなっています。

  • データが小さく、めったに直線的にトラバースされない場合、リストは理にかなっています。

リストとベクトルの操作は複雑さが異なることに注意してください。したがって、iterate . replicateリストはO(n)ですが、怠惰ですが、ベクトルの同じ操作は必ずしも効率的であるとは限りません (配列を生成するには、ベクトルの組み込みメソッドを優先する必要があります)。

一般に、ベクトルは常に数値演算に適しているはずです。リストで行うさまざまな機能を使用する必要がある場合があります。

ベクトルのみに固執します。UArray を避け、ジェネレータ以外のリストを避けます。

于 2012-04-19T12:24:45.610 に答える