haskell - Haskell での二分探索を使用したより高速な「elem」

Question

のリストがありText、それらはソートされています。elem線形検索ではなく二分検索として実装することで、はるかに高速なバージョンの を作成できるように思えます。そのようなバージョンはすでに存在しますか?

Answer 1

Haskell のリストは、リンクされたリストとして実装されます。つまり、任意のi-th 要素へのアクセスは にありO(i)ます。通常の使用法では、 for リストのバイナリ検索バージョンはelem、標準バージョンよりも時間がかかります (以下の @DanielFischer の発言を参照)。

Data.SetやData.Mapなどの別のコンテナーを使用したい場合があります。これらはバランスの取れたバイナリ ツリーとして実装され、O(log n)アクセス時間を提供します (nはマップ/セット内の要素の数)。

Answer 2

二分探索にはランダム アクセスが必要です。Haskell リストはランダム アクセスを提供しないため (途中の要素へのアクセスには直線的な時間がかかります)、二分探索は役に立ちません。

データがArrayランダム アクセスを提供する にある場合、二分探索が実行可能です。

Answer 3

テキストのリストがあり、それらはソートされています。

データ構造を変更すると、アルゴリズムが明確になります (ブルックスの言葉を言い換えると)。

これは特に Haskell に当てはまります。Haskell では、通常、データ構造が可変配列の観点からではありません (つまり、ポインターのハッキングに頼ることはありません)。

たとえばヒープやツリーを使用してテキストを保存する場合、 O(log(n)) elemを簡単に実装できます。それらがソートされているという事実を利用して、より高速な挿入を提供できます。