質問

Haskellを学んでいて、Haskellのリストと（あなたの言語を挿入してください）配列のパフォーマンスの違いに関するいくつかの記事を読みました。

学習者である私は、当然ながら性能の違いについて考えることなく、ただリストを使っています。 最近調べ始めたら、Haskellで利用できるデータ構造ライブラリがたくさんあることがわかりました。

リスト、配列、ベクトル、シーケンスの違いについて、コンピュータサイエンスのデータ構造の理論にあまり深く立ち入ることなく、どなたか説明していただけませんか？

また、あるデータ構造の代わりに別のデータ構造を使用するような、よくあるパターンはありますか？

その他、私が見逃している、役に立つかもしれないデータ構造の形式はありますか？

どのように解決するのですか？

リストロック

Haskellでシーケンシャルなデータに対して最も親しみやすいデータ構造は、リストです。

 data [a] = a:[a] | []

リストは ϴ (1) cons とパターンマッチングを提供します。 標準ライブラリやプレリュードには便利なリスト関数がたくさんあるので、あなたのコードを散らかさないようにしましょう ( foldr , map , filter ). リストは 永続的 純粋に機能的で、とてもいいことだと思います。 Haskellのリストはコインダイレクション（他の言語ではこれをストリームと呼びます）なので、本当の意味でのリストではありません。

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

は素晴らしく機能する。 無限のデータ構造はロックです。

Haskellのリストは、（怠惰のため）命令型言語のイテレータによく似たインタフェースを提供する。 だから、広く使われているのは理にかなっている。

一方

リストの最初の問題は、リストへのインデックス付けに (!!) はϴ時間を要し、これは迷惑な話です。また、追加も遅くなることがあります ++ しかし、Haskellの遅延評価モデルは、これらが発生した場合、完全に償却されたものとして扱うことができることを意味します。

リストの2つ目の問題は、データローカリティが低いことです。 実際のプロセッサでは、メモリ上のオブジェクトが互いに隣接して配置されていない場合に、高い定数が発生します。 ですから、C++では std::vector しかし、これは永続的なデータ構造ではないので、Haskellのリストほど親しみやすいものではありません。

リストの3つ目の問題は、スペース効率が悪いことです。 余分なポインタの束は、ストレージを（一定の割合で）押し上げるのです。

配列は機能的である

Data.Sequence は、内部的には 指の木 (知りたくもないでしょうが)つまり、これらはいくつかの素晴らしい特性を持っているのです。

1. 純粋に機能的であること。 Data.Sequence は完全に永続的なデータ構造です。
2. ツリーの先頭と末尾にダントツで高速にアクセスできる。 ϴ(1) (償却)で最初か最後の要素を取得したり、ツリーを追加することができます。 リストが最も得意とするところです。 Data.Sequence はせいぜい一定数遅くなる程度です。
3. ϴ(log n)シーケンスの途中までアクセスできる。 これには、新しいシーケンスを作るための値の挿入も含まれる
4. 高品質なAPI

一方 Data.Sequence はデータの局所性の問題にはあまり効果がなく、有限のコレクションに対してのみ機能します（リストよりも遅延が少ないです）。

配列は気の弱い人には向かない

配列はCSで最も重要なデータ構造の1つですが、怠惰な純粋関数型の世界とはあまり相性がよくありません。 配列はコレクションの真ん中にϴアクセスでき、例外的に優れたデータローカリティと定数係数を提供します。 しかし、Haskellにはあまりなじまないので、使うのは面倒です。 実は、現在の標準ライブラリには、数多くの異なる配列型が存在します。 完全な永続化配列、IOモナド用のミュータブル配列、STモナド用のミュータブル配列、そしてこれらの非ボックス化されたバージョンなどです。 詳しくは ハッシュケルウィキ

ベクターはより良い配列です。

は Data.Vector パッケージは、より高度ですっきりした API で、配列のすべての機能を提供します。自分が何をしているのか本当にわかっているのでなければ、配列のようなパフォーマンスが必要な場合はこれらを使うべきでしょう。 もちろん、いくつかの注意点はまだ適用されます。変更可能な配列のようなデータ構造は、純粋な遅延言語ではうまくいきません。 それでも、時にはO(1)のパフォーマンスが必要で、かつ Data.Vector は、使いやすいパッケージで提供します。

他のオプションがあります

効率的に末尾に挿入できる機能を持ったリストが欲しいだけなら 差分リスト . リストがパフォーマンスを悪化させる最も良い例は、次のようなものです。 [Char] というエイリアスを作成し、プレリュードが String . Char リストは便利ですが，C言語の文字列よりも20倍ほど動作が遅くなる傾向があります． Data.Text または非常に高速な Data.ByteString . 他にもシーケンス指向のライブラリがあると思うのですが、今は考えていません。

まとめ

Haskellでシーケンシャルなコレクションを必要とする場合の90%以上は、リストが適切なデータ構造です。 リストはイテレータのようなもので、リストを消費する関数は、リスト以外のデータ構造でも toList という関数が付属しています。 より良い世界では、プレリュードはどのコンテナタイプを使用するかについて完全にパラメータ化されていますが、現在では [] は標準ライブラリに散らばっています。 だから、（ほとんど）あらゆるところでリストを使うのは、間違いなくOKなのです。

ほとんどのリスト関数の完全パラメトリックバージョンが手に入ります（そして、それを使うことは尊いことです）。

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 対 Data.Sequence . 配列とベクトルは非常に高速なインデックス付けとスライス操作を提供しますが、基本的には一過性の（命令的な）データ構造です。 純粋な関数型データ構造である Data.Sequence と [] を効率よく生産することができます。 新しい を、あたかも古い値を修正したかのように、古い値から生成します。

  newList oldList = 7 : drop 5 oldList

は古いリストを変更しませんし、それをコピーする必要もありません。 ですから、たとえ oldList がとてつもなく長い場合、この "modification" は非常に高速になります。 同様に

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

は新しいシーケンスを生成し newValue を3000要素に置き換えます。 繰り返しますが、これは古いシーケンスを破壊するのではなく、新しいシーケンスを作成するだけです。 しかし、この処理は非常に効率的で、O(log(min(k,k-n)), n は配列の長さ、kは変更するインデックスです。

を使用すると、このようなことは簡単にできません。 Vectors と Arrays . これらは モディファイド しかし、これは本当の命令的な変更であり、通常のHaskellのコードではできない。 つまり Vector のような変更を行うパッケージは snoc と cons はベクター全体をコピーしなければならないので O(n) の時間が必要です。 唯一の例外は、ミュータブルバージョン( Vector.Mutable ) の内部で ST モナド（または IO で、命令型言語と同じように、すべての修正を行います。 それが終わったら、quot;freeze" で、vector を純粋なコードで使用するための不変の構造に変身させるのです。

私の感覚では、デフォルトで Data.Sequence リストが適切でない場合 使用方法 Data.Vector は、使用パターンが多くの変更を伴わない場合、またはST/IOモナド内で極めて高いパフォーマンスが必要な場合にのみ使用します。

もし、これだけ ST モナドを使えば、より速く、より美しい、純粋な Data.Sequence .