java - ArrayListで検索

Question

私はこれを持っています。

private ArrayList<String> words;

これは辞書なので、単語はすでに並べ替えられています。古い研究によると、二分探索は非常に高速である必要があることを私は知っています。Javaはすでに必要なものを実装していると思います。

では、ソートされたArrayList内に特定の文字列が存在するかどうかを見つける最も効率的な方法は何ですか？または、別のタイプを使用する必要がありますか？

ありがとうございました。

Answer 1

または、別のタイプを使用する必要がありますか？

HashSet<String>代わりに使用してみてください。そのcontainsメソッドには、ハッシュの衝突が多すぎないことを前提としたO（1）ルックアップがあります。ドキュメントから：

このクラスは、ハッシュ関数が要素をバケット間で適切に分散することを前提として、基本操作（追加、削除、包含、およびサイズ設定）に対して一定時間のパフォーマンスを提供します。

ソートされたバイナリ検索ArrayListはO（log n）のみです。これはまだ非常に高速ですが、を使用するほど高速ではありませんHashSet。

Answer 2

二分探索は、ソートされた配列の中で最速になります。ハッシュセットを使用している場合は、存在のテストを一定時間で実行できます。

Answer 3

特定の文字列を検索しようとする回数によって異なります。HashMap<String, String>マップが大きくなるにつれてこれは高速のままであるため、を試してみることをお勧めします。

Answer 4

バイナリ検索を行う場合は、データを次のように再編成することをお勧めします。Binary Search Tree

ArrayListsは、シーケンシャル操作やランダムアクセスによく使用されます。検索を行う予定で、最速のルックアップが必要な場合は、最初からデータを整理するのが最善です。これには、より高速な挿入/削除や、可能な限り最速の時間で実行したいと考えている他のすべての操作を容易にするという利点もあります。

あなたが始めるためにグーグルと他の場所にたくさんのガイドがあります。