1

Javaで、増え続ける文字列リストで単語または部分文字列を検索する最速の方法は何ですか?

たとえば、10 個の単語のリストがあり、ユーザーが入力した単語を 5 分ごとに検索し、そのリストが 1 分ごとに 1 単語ずつ増えていく場合、これらの単語を格納するのに最適なデータ構造は何でしょうか。 ?

私たちが実際に行っているのはこれです...「キーワード」を取得すると、プログラムはそのキーワードに基づいて応答するフレーズを検索する必要がありますが、フレーズのリストは常に増加しています。キーワードを読み取り、すべてのフレーズを解析してからフレーズを選択するには、非常に時間がかかります。現在のアルゴリズムは現在 n^3 であり、これは不適切です。

Java のデータ構造、またはこれをより効率的にするのに役立つソート/検索アルゴリズムはありますか?

4

2 に答える 2

1

巨大で困難な検索タスクには、常にマージソートを使用します。リストが毎分増えているという事実は、アルゴリズムにとって問題にはならないはずです。必要な単語を見つけるために、これを別のチェッカーと組み合わせることができます。実際、最初のリストを並べ替えたら、検索を開始したときにのみデータを確認するのではなく、リスト内の各要素を受け取ったときに挿入する方が理にかなっている場合があります。

リストをこのように並べ替えておくと、成長率が信じられないほど高くないと仮定すると、パフォーマンスが大幅に向上します。

于 2012-10-29T22:30:17.343 に答える
1

HashMap にリンクされたキーワードとフレーズを格納するだけでは不十分な場合は、フレーズの逆インデックスを使用することをお勧めします。その場合、Apache Luceneはおそらくこれを実装するための選択肢です。

于 2012-10-29T22:32:27.550 に答える