怠惰な関数型言語では、リンクリストはジェネレータ風のセマンティクスを持ち、最適化コンパイラの下では、実際にはストレージに使用されていないときにオーバーヘッドを完全に削除できます。リンクされたリストは、熱心な関数型言語で実用的なパフォーマンス上の利点がありますか？
しかし、熱心な機能言語では、それらの使用はそれほど重くはないように見えますが、最適化するのは難しいようです。 Schemeのような言語では、プライマリシーケンス表現としてフラットな配列よりも優れたパフォーマンス理由がありますか？
私は、単一リンクリストを使用すると明らかに時間が複雑になることに気付いています。私は、プライマリシーケンス表現として熱心な単独リンクリストを使用することによる実際のパフォーマンス結果、コンパイラの最適化を検討しています。
TL; DR：パフォーマンス上の利点はありません！
最初のLispはデータ構造としてcons（リンクリストセル）を持ち、すべてに使用しました。 Common LispとSchemeの両方には今日のベクタがありますが、機能的なスタイルではうまく一致しません。リンクされたリストには、1つの再帰的なステップがあり、アキュムレータの前にゼロ個以上の要素を追加できます。最後に、繰り返しの間に共有されたリストがあります。この操作では、複数の再帰が行われ、すべてのテールを共有する複数のバージョンが作成されます。私は共有がリンクされたリストの最も重要な側面だと言います。ミニマックスアルゴリズムを作成して状態をリンクリストに格納すると、状態の変更されていない部分をコピーすることなく状態を変更できます。 C++ビャーネ・ストロヴストルップの
Creatorは、データ構造を有するのペナルティはスクランブルとリンクリストのように二重の大きさは容易にあなたが順番に挿入し、データ構造の半分の要素を移動する必要がある場合でも上回っていることin a talkに言及しています。これらは二重にリンクされたリストと突然変異の挿入であることを覚えておいてください。しかし、ほとんどの時間はポインタを直線的に追跡し、すべてのCPUキャッシュミスを取得し、正しい場所を見つけ出し、したがってソートされたO（n）ベクトルをリストする方が良いでしょう。
リストにたくさん挿入するプログラムがある場合は、おそらくツリーがより良い選択肢になります。consでCLとSchemeで行うことができます。実際に、Chris Okasakiのすべての機能的なデータ構造はconsで実装できます。 Haskellのほとんどの "可変"構造は、それと同様に実装されています。
Schemeでパフォーマンス上の問題が発生し、プロファイリング後にリンクリスト操作を配列1で置き換える必要があることが判明した場合は、その方法で何も立っていることはありません。結局のところ、すべてのアルゴリズムの選択肢には長所と短所があります。ハードコンピューティングはどの言語でも難しいです。
C++の配列/ベクトルは、デフォルトでは_unboxed_（メモリパックされている）なので、高速すぎることに注意してください。これにより、キャッシュミスのない_elements_に実際にアクセスできます。しかし、動的言語（限定されたOO動的型付けを含む）およびHaskell et al。一般的には、_O_（_ _ _）検索で要素をルックアップする必要がある場合には、ポインタの_配列として配列を持つことしかできません。配列は依然としてリンクリストより高速ですが、C++のような大きな要因ではありません。 – leftaroundabout
@leftaround私は同意しますが、今度はハスケルにボックス化されていないベクトルがあります。これらは低レベルの安全ではないプリミティブを使用して定義する必要がありましたが、ボックス化できないタイプの場合にのみ定義しなければなりませんでしたが、パフォーマンスはC++に近いほうがよいでしょう。 – chi
@leftaroundaboutいいえ、速度は主にメモリの依存関係を取り除くことによって得られます。ポインタのベクトルは、リンクされた値のリストよりもはるかに高速です。メモリの参照を解除すると潜在的に潜在的ですが、それほど厄介なスループットはありません。 – Veedrac
1）シンプリシティ2）トリビアルO（1）プリフェンド3）共有 – Bergi
@Bergiシンプリシティは実際には「パフォーマンス」の利点ではありませんが、それは理由です。私はあなたの共有ポイントを理解しているとは分かりません。不変性を仮定すると、フラットアレイを簡単に共有することができます。 – Textfield
しかし、配列の一部を共有することはできません。リストはテールを共有できます。 – Bergi