6

私が現在取り組んでいるプログラムでは、少し時間がかかっている部分が 1 つあります。基本的に、文字列のリストと 1 つのターゲット フレーズがあります。例として、対象フレーズが「完成品の在庫」であるとします。ここで、ストップ ワード (of) をフィルターで除外した後、"inventory"、"finished"、"goods" の 3 つの単語のいずれかを含むすべての文字列をリストから抽出したいと考えています。今、私は次のようにアイデアを実装しました：

String[] targetWords; // contains "inventory", "finished", and "goods"
ArrayList<String> extractedStrings = new ArrayList<String>();

for (int i = 0; i < listOfWords.size(); i++) {
    String[] words = listOfWords.get(i).split(" ");
    outerloop:
    for (int j = 0; j < words.length; j++) {
        for (int k = 0; k < targetWords.length; k++) {
            if (words[j].equalsIgnoreCase(targetWords[k])) {
                extractedStrings.add(listOfWords.get(i));
                break outerloop;
            }
        }
    }
}

リストには 10 万語を超える単語が含まれており、これにより、各ターゲット フレーズのタスクを完了するのに約 0.4 ～ 0.8 秒かかります。問題は、処理するこれらのターゲット フレーズがたくさんあるということです。したがって、このタスクを完了するためのより効率的な方法を誰かが知っているかどうか疑問に思っていましたか? 事前に助けてくれてありがとう！

4

5 に答える 5

6

10 万語のリストを (1 回) HashSet に追加できます。リストを反復処理するのではなくwordSet.contains()、HashSet を使用すると一定時間のパフォーマンスが得られるため、リストのサイズの影響を受けません。

于 2013-08-09T00:33:32.403 に答える
1

フレーズ全体が必要なのか、listOfWords からの単語だけが必要なのか、少し混乱しています。ターゲット単語の1つが文字列に含まれている場合、listOfWordsから文字列を取得しようとしている場合、これはうまくいくはずです。 

    String[] targetWords= new String[]{"inventory", "finished", "goods"};
    List<String> listOfWords = new ArrayList<String>();

    // build lookup map
    Map<String, ArrayList<String>> lookupMap = new HashMap<String, ArrayList<String>>();
    for(String words : listOfWords) {
        for(String word : words.split(" ")) {
            if(lookupMap.get(word) == null) lookupMap.put(word, new ArrayList<String>());
            lookupMap.get(word).add(words);
        }
    }

    // find phrases
    Set<String> extractedStrings = new HashSet<String>();
    for(String target : targetWords) {
        if(lookupMap.containsKey(target)) extractedStrings.addAll(lookupMap.get(target));
    }
于 2013-08-09T01:20:50.813 に答える
1

targetWordstargetWords のすべての単語を同時にチェックするのではなく、の各要素を通過しています。さらに、各反復で単語のリストを実際には必要としないのに分割しているため、オーバーヘッドが生じます。

targetWords1 つの (コンパイルされた)正規表現に結合することをお勧めします。

(?xi)  # turn on comments, use case insensitive matching
\b     # word boundary, i.e. start/end of string, whitespace
(      # begin of group containing 'inventory' or 'finished' or 'goods'
 inventory|finished|goods  # bar separates alternatives
)      # end of group
\b     # word boundary

正規表現文字列のバックスペースを二重引用符で囲むことを忘れないでください。

import java.util.regex.*;
...
Pattern targetPattern = Pattern.compile("(?xi)\\b(inventory|finished|goods)\\b");
for (String singleString : listOfWords) {
  if (targetPattern.matcher(singleString).find()) {
    extractedStrings.add(singleString);
  }
}

通常、正規表現エンジンはパフォーマンスのために最適化されていますが、正規表現の速度に満足できない場合は、独自の高速複数文字列検索を展開する必要があります。Aho-Corasick 文字列マッチング アルゴリズムは、テキスト内の複数の固定文字列を検索するために最適化されていますが、もちろん、このアルゴリズムを実装することは、単純にパターンを作成することに比べてかなりの労力を要します。

于 2013-08-09T20:51:11.897 に答える
0

ExecutorService各単語の検索を並列 化するために実装しようと思います。http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ExecutorService.html

たとえば、固定スレッド プール サイズの場合:

Executors.newFixedThreadPool(20);
于 2013-08-09T00:25:21.300 に答える