私は Haskell を学習しており、Haskell リストと (あなたの言語を挿入) の配列のパフォーマンスの違いに関する記事をいくつか読みました。
学習者である私は、当然ながら、パフォーマンスの違いについて考えることもなくリストだけを使用しています。最近調査を開始し、Haskell で利用できるデータ構造ライブラリが多数あることを発見しました。
データ構造に関するコンピューター サイエンスの理論をあまり深く理解せずに、リスト、配列、ベクトル、シーケンスの違いを説明していただけますか?
また、あるデータ構造を別のデータ構造の代わりに使用する一般的なパターンはありますか?
私が見逃していて役に立つかもしれない他の形式のデータ構造はありますか?
ベストアンサー1
リストロック
Haskellで連続データを扱うのに最も使いやすいデータ構造はリストである。
data [a] = a:[a] | []
リストはϴ (1) consとパターンマッチングを提供します。標準ライブラリ、そしてプレリュードには、コードに散らばるべき便利なリスト関数が満載です（foldr、、）。リストは永続的map、つまり純粋に関数的であり、非常に便利です。Haskellのリストは、共帰的であるため（他の言語ではこれをストリームと呼びます）、実際には「リスト」ではありません。そのため、次のようなものfilter
ones :: [Integer]
ones = 1:ones
twos = map (+1) ones
tenTwos = take 10 twos
素晴らしいです。無限のデータ構造は素晴らしいです。
Haskell のリストは、命令型言語のイテレータとよく似たインターフェースを提供します (遅延のため)。そのため、リストが広く使用されているのは当然です。
一方で
リストの最初の問題は、リストへのインデックス作成に(!!)ϴ (k) 時間がかかることです。これは面倒です。また、追加は遅くなる可能性があります++が、Haskell の遅延評価モデルにより、追加が発生した場合でも完全に償却されたものとして扱うことができます。
リストの 2 番目の問題は、データの局所性が低いことです。実際のプロセッサでは、メモリ内のオブジェクトが互いに隣接して配置されていない場合、定数が大きくなります。そのため、C++ では、std::vector私が知っている純粋なリンク リスト データ構造よりも高速な「snoc」(オブジェクトを末尾に配置する) が実現されていますが、これは永続的なデータ構造ではないため、Haskell のリストほど使いやすくはありません。
リストの 3 番目の問題は、スペース効率が悪いことです。余分なポインターが大量に存在することで、ストレージが (一定の係数で) 増加します。
シーケンスは機能的である
Data.Sequence内部的にはフィンガーツリーに基づいています（知りたくないでしょうが）。つまり、いくつかの優れた特性を持っています。
純粋に機能的。
Data.Sequence完全に永続的なデータ構造です。ツリーの先頭と末尾へのアクセスが非常に高速です。ϴ (1) (償却) は、最初または最後の要素を取得するため、またはツリーを追加するためです。リストが最も高速なのは、
Data.Sequenceせいぜい定数分遅いだけです。シーケンスの途中へのϴ (log n) アクセス。これには、新しいシーケンスを作成するための値の挿入が含まれます。
高品質のAPI
一方、Data.Sequenceデータの局所性の問題にはあまり効果がなく、有限コレクションに対してのみ機能します（リストよりも遅延が少ない）
配列は気の弱い人には向いていない
配列は CS で最も重要なデータ構造の 1 つですが、遅延純粋関数の世界とはあまり適合しません。配列は、コレクションの中央への ϴ (1) アクセスと、非常に優れたデータ局所性/定数係数を提供します。しかし、Haskell にはあまり適合しないため、使用するのは面倒です。現在の標準ライブラリには、実際にはさまざまな配列型があります。これらには、完全に永続的な配列、IO モナドの可変配列、ST モナドの可変配列、および上記の非ボックス化バージョンが含まれます。詳細については、Haskell wikiを参照してください。
ベクトルは「より良い」配列である
このData.Vectorパッケージは、配列の優れた機能をすべて、より高レベルでクリーンな API で提供します。何をしているのか本当にわかっているのでなければ、配列のようなパフォーマンスが必要な場合は、これらを使用する必要があります。もちろん、いくつかの注意事項は適用されます。変更可能な配列のようなデータ構造は、純粋な遅延言語ではうまく機能しません。それでも、O (1) のパフォーマンスが必要な場合があり、Data.Vector使いやすいパッケージでそれを実現します。
他の選択肢もあります
最後に効率的に挿入できるリストだけが必要な場合は、差分リスト を使用できます。リストがパフォーマンスを台無しにする最も良い例は、[Char]プレリュードが としてエイリアスしているから発生する傾向がありますString。リストは便利ですが、C 文字列よりも 20 倍ほど遅くなる傾向があるため、または非常に高速な を自由Charに使用してください。今考えていない他のシーケンス指向のライブラリもあることは確かです。Data.TextData.ByteString
結論
Haskell でシーケンシャル コレクションが必要な場合、90% 以上はリストが適切なデータ構造です。リストはイテレータのようなもので、リストを使用する関数は、付属の関数を使用して、他のデータ構造で簡単に使用できます。toListより良い世界では、プレリュードは使用するコンテナー タイプに関して完全にパラメトリックになりますが、現在は[]標準ライブラリが散らかっています。したがって、リストを (ほぼ) どこでも使用することは間違いなく問題ありません。ほとんど
のリスト関数の完全なパラメトリック バージョンを取得できます (そして、それらを使用することは有益です)
Prelude.map ---> Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc ---> Data.Foldable.foldr/foldl/etc
Prelude.sequence ---> Data.Traversable.sequence
etc
実際、Data.Traversableリストのようなものであれば何でもほぼ普遍的な API を定義します。
それでも、完全にパラメトリックなコードだけを書くのが上手な人もいるかもしれませんが、ほとんどの人はそうではなく、至る所でリストを使用しています。学習中であれば、ぜひそうすることをお勧めします。
Data.Vectorコメントに基づいて、 vs をいつ使用するかについて説明していなかったことに気付きましたData.Sequence。配列とベクターは、非常に高速なインデックス作成とスライス操作を提供しますが、基本的には一時的 (命令型) なデータ構造です。 や のような純粋関数型データ構造ではData.Sequence、古い値を変更したかのように、古い値から新しい[]値を効率的に生成できます。
newList oldList = 7 : drop 5 oldList
古いリストは変更されず、コピーする必要もありません。そのため、リストoldListが非常に長い場合でも、この「変更」は非常に高速になります。同様に、
newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence
3000 個の要素の代わりに forを使用して新しいシーケンスを生成しますnewValue。この場合も、古いシーケンスは破棄されず、新しいシーケンスが作成されるだけです。ただし、これは非常に効率的に実行され、O (log (min (k, kn) を要します。ここで、n はシーケンスの長さ、k は変更するインデックスです。
Vectorsこれをとで簡単に行うことはできません。これらは変更Arraysできますが、これは実際の命令型の変更であるため、通常の Haskell コードでは実行できません。つまり、や などの変更を行うパッケージ内の操作では、ベクトル全体をコピーする必要があるため、時間がかかります。唯一の例外は、モナド (または)内で可変バージョン ( )を使用して、命令型言語の場合と同じようにすべての変更を行うことができることです。完了したら、ベクトルを「フリーズ」して、純粋なコードで使用する不変構造に変換します。VectorsnocconsO(n)Vector.MutableSTIO
Data.Sequenceリストが適切でない場合は、デフォルトで を使用する必要があると思います。Data.Vector使用パターンに多くの変更が含まれない場合、または ST/IO モナド内で非常に高いパフォーマンスが必要な場合にのみ使用してください。
モナドに関するこの話でST混乱しているのであれば、純粋で速くて美しいものにこだわるべき理由がさらに増えますData.Sequence。