13

明らかに漸近的に、可能なすべての操作Seqと同じかそれ以上のパフォーマンスを発揮します。[]ただし、その構造はリストよりも複雑であるため、サイズが小さい場合は、オーバーヘッドが一定であるため、速度が低下する可能性があります。特に、いくらか知りたいのですが。

  1. <|比較してどれくらい遅い:ですか？
  2. Seqフォールドオーバー/トラバースと比較して、フォールドオーバー/トラバースはどれくらい遅いですか[]（フォールディング/トラバース機能のコストを除く）？
  3. \xs x -> xs ++ [x]遅くなるサイズ（概算）は|>？
  4. ++遅くなるサイズ（概算）は><？
  5. viewlリストのパターンマッチングと比較して、結果の呼び出しとパターンマッチングのコストはいくらですか？
  6. -elementリストと比較して、n-elementはどのくらいのメモリを占有しますか？（要素によって占有されているメモリはカウントせず、構造のみをカウントします。）Seqn

償却された複雑さについて話しているので、測定するのは難しいことは知っていますSeqが、少なくともいくつかの大まかな数値を知りたいと思います。

4

2 に答える 2

14

これはスタートになるはずです - http://www.haskell.org/haskellwiki/Performance#Data.Sequence_vs._lists

シーケンスは、同等のリストの 5/6 から 4/3 倍のスペースを使用します (GHC のようにノードごとに 1 ワードのオーバーヘッドを想定)。deque 操作のみが使用される場合、すべての内部ノードが 3 項になるため、スペース使用量は範囲の下限近くになります。分割と追加を多用すると、リストとほぼ同じスペースを使用するシーケンスになります。詳細に：

  • 長さ n のリストは n 個のコンス ノードで構成され、それぞれが 3 ワードを占めます。
  • 長さ n のシーケンスには、約 n/(k-1) ノードがあります。ここで、k は内部ノードの平均アリティ (それぞれ 2 または 3) です。各ノードのポインタ、サイズ、およびオーバーヘッドに加えて、各要素のポインタ、つまり n(3/(k-1) + 1) ワードがあります。

List は、ヘッド (cons および head) での操作に対して自明ではない定数倍高速であるため、スタックのようなアクセス パターンやストリームのようなアクセス パターンではより効率的な選択となります。Data.Sequence は、キューやランダム アクセスなど、他のすべてのアクセス パターンで高速です。

于 2013-02-10T14:46:35.880 に答える