3

私は文字列の大きなコレクションを持っています。「Foo」で始まる文字列または「Bar」で終わる文字列を見つけられるようにしたいと考えています。最速の結果を得るには、どのコレクション タイプが最適でしょうか? (私は Java を使用しています)

HashSet は完全一致では非常に高速ですが、部分一致ではそうではないと思いますか? では、リストをループするだけでなく、何を使用できますか? LinkedList または同様のタイプを調べる必要がありますか? この種のクエリ用に最適化されたコレクション型はありますか?

4

3 に答える 3

3

しばらく経ちましたが、今これを実装する必要があり、いくつかのテストを行いました。

私はすでにHashSet<String>ソースとして持っているので、他のすべてのデータ構造の生成は検索時間に含まれています。100 の異なるソースが使用され、そのたびにデータ構造を再生成する必要があります。毎回数個の単一文字列を照合するだけで済みます。これらのテストは Android で実行されました。

方法:

  1. シンプルなループスルーと各文字列 HashSetの呼び出しendsWith()

  2. 各文字列に対して単純なループをHashSet実行し、プリコンパイル Patternされた一致 (正規表現) を実行します。

  3. 文字列全体で単一の結合と単一の一致に変換HashSetします。String\n

  4. から SortedTree反転して生成します。次に、@Mario Rossi で説明されているように一致させます。StringsHashSetsubset()

結果：

Duration for method 1: 173ms (data setup:0ms search:173ms)
Duration for method 2: 6909ms (data setup:0ms search:6909ms)
Duration for method 3: 3026ms (data setup:2377ms search:649ms)
Duration for method 4: 2111ms (data setup:2101ms search:10ms)

結論：

SortedSet/SortedTreeは検索が非常に高速です。すべてをループするよりもはるかに高速ですStrings。ただし、構造の作成には多くの時間がかかります。正規表現ははるかに遅くなりますが、Android/Java では、String数百から 1 つの大きなものを生成することがボトルネックになります。Strings

いくつかの一致のみを行う必要がある場合は、コレクションをループすることをお勧めします。より多くの一致を作成する場合は、SortedTree!を使用すると非常に便利です。

于 2014-03-09T00:31:36.257 に答える
3

この問題に最適なコレクション タイプは ですSortedSet。実際には、次の 2 つが必要です。

  1. 規則的な順序で単語。
  2. 文字を反転させた単語。

これらSortedSetの が作成されたら、メソッドを使用subSetして探しているものを見つけることができます。例えば：

  1. で始まる単語"Foo":

     forwardSortedSet.subSet("Foo","Fop");

  2. で終わる言葉"Bar":

     backwardSortedSet.subSet("raB","raC");

最後の検索文字に 1 を「追加」する理由は、範囲全体を取得するためです。「終わり」の単語は から除外されているsubSetので問題ありません。

編集:SortedSet標準 Java ライブラリで 実装する 2 つの具体的なクラスのうち、を使用しますTreeSet。もう 1 つの ( ConcurrentSkipListSet) は並行プログラム向けであるため、この状況には最適化されていません。

于 2013-09-02T01:59:50.340 に答える
2

If the list of words is stable (not many words are added or deleted), a very good second alternative is to create 2 lists:

  1. One with the words in normal order.
  2. The second with the characters in each word reversed.

For speed purposes, make them ArrayLists. Never LinkedLists or other variants which perform extremely bad on random access (the core of binary search; see below).

After the lists are created, they can be sorted with method Collections.sort (only once each) and then searched with Collections.binarySearch. For example:

    Collections.sort(forwardList);
    Collections.sort(backwardList);

And then to search for words starting in "Foo":

    int i= Collections.binarySearch(forwardList,"Foo") ;
    while( i < forwardList.size() && forwardList.get(i).startsWith("Foo") ) {
        // Process String forwardList.get(i)
        i++;
    }

And words ending in "Bar":

    int i= Collections.binarySearch(backwardList,"raB") ;
    while( i < backwardList.size() &&  backwardList.get(i).startsWith("raB") ) {
        // Process String backwardList.get(i)
        i++;
    }
于 2013-09-02T02:12:20.693 に答える