4

現在、作成中のこのアプリケーションで奇妙な動作が発生しています。

序文

私が構築しているこのアプリケーションの目標は単純です。つまり、文字列のコレクションを取得し、複数のテキスト ファイルからそれらの各文字列を検索することです。アプリケーションは、各文字列の一意の一致も追跡します。つまり、文字列 "abcd" は、ファイル A に n 回出現する場合、1 回だけカウントされます。

このアプリケーションは主に多数のファイルと多数の文字列を処理するため、Runnable を実装するクラスを作成し、ExecutorService を使用して Runnable タスクを実行することにより、バックグラウンドで文字列検索を行うことにしました。また、文字列検索の速度を調べることにしたので、文字列一致のさまざまな方法 (つまり、Boyer-Moore アルゴリズム) を使用して時間の比較を開始しましString.contains()たString.indexOf()。http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.htmlから Boyer-Moore アルゴリズムのソース コードを取得し、プロジェクトに含めました。ここから問題が始まりました...

問題

クラスを使用すると、文字列検索がさまざまな結果で返されることに気付きました (検索を実行するたびに、見つかった文字列の数は異なります) 。BoyerMooreString.contains()

private boolean findStringInFile(String pattern, File file) {
    boolean result = false;
    BoyerMoore bm = new BoyerMoore(pattern); // This line still causes varying results.
    try {
        Scanner in = new Scanner(new FileReader(file));
        while(in.hasNextLine() && !result) {
            String line = in.nextLine();
            result = line.contains(pattern);
        }
        in.close();
    } catch (FileNotFoundException e) {
        System.out.println("ERROR: " + e.getMessage());
        System.exit(0);
    }
    return result;
}

上記のコードを使用しても、結果は一貫していませんでした。BoyerMooreオブジェクトのインスタンス化によって結果が異なるようです。もう少し深く掘り下げたところ、BoyerMooreコンストラクターの次のコードがこの矛盾を引き起こしていることがわかりました...

// position of rightmost occurrence of c in the pattern
right = new int[R];
for (int c = 0; c < R; c++)
    right[c] = -1;
for (int j = 0; j < pat.length(); j++)
    right[pat.charAt(j)] = j;

不一致の原因はわかりましたが、なぜそれが起こったのかはまだわかりません。マルチスレッドに関してはベテランではないので、可能な説明/洞察は大歓迎です!

以下は、検索タスクの完全なコードです...

private class Search implements Runnable {
    private File mSearchableFile;
    private ConcurrentHashMap<String,Integer> mTable;

    public Search(File file,ConcurrentHashMap<String,Integer> table) {
        mSearchableFile = file;
        mTable = table;
    }

    @Override
    public void run() {
        Iterator<String> nodeItr = mTable.keySet().iterator();
        while(nodeItr.hasNext()) {
            String currentString = nodeItr.next();
            if(findStringInFile(currentString , mSearchableFile)) {
                Integer count = mTable.get(currentString) + 1;
                mTable.put(currentString,count);
            }
        }
    }

    private boolean findStringInFile(String pattern, File file) {
        boolean result = false;
        // BoyerMoore bm = new BoyerMoore(pattern);
        try {
            Scanner in = new Scanner(new FileReader(file));
            while(in.hasNextLine() && !result) {
                String line = in.nextLine();
                result = line.contains(pattern);
            }
            in.close();
        } catch (FileNotFoundException e) {
            System.out.println("ERROR: " + e.getMessage());
            System.exit(0);
        }
        return result;
    }
}
4

1 に答える 1

2

これは次のようにパフォーマンスが向上するはずです

  • 各ファイルは一度だけ開いて閉じます。
  • スレッド間でデータが共有されないため、スレッド間のオーバーヘッドはありません (最終結果を除く)

これにより、各ファイルの一致が取得され、単一のスレッドでカウントが累積されます。

static class Search implements Callable<Set<String>> {
    private final File file;
    private final Set<String> toFind;
    private final long lastModified;

    public Search(File file, Set<String> toSearchFor) {
        this.file = file;
        lastModified = file.lastModified();
        toFind = new CopyOnWriteArraySet<>(toSearchFor);
    }

    @Override
    public Set<String> call() throws Exception {
        Set<String> found = new HashSet<>();
        Scanner in = new Scanner(new FileReader(file));
        while (in.hasNextLine() && !toFind.isEmpty()) {
            String line = in.nextLine();
            for (String s : toFind) {
                if (line.contains(s)) {
                    toFind.remove(s);
                    found.add(s);
                }
            }
        }
        in.close();

        if (file.lastModified() != lastModified) 
            throw new AssertionError(file + " was modified");
        return found;
    }
}

public static Map<String, AtomicInteger> performSearches(
        ExecutorService service, File[] files, Set<String> toFind)
        throws ExecutionException, InterruptedException {
    List<Future<Set<String>>> futures = new ArrayList<>();
    for (File file : files) {
        futures.add(service.submit(new Search(file, toFind)));
    }
    Map<String, AtomicInteger> counts = new LinkedHashMap<>();
    for (String s : toFind)
        counts.put(s, new AtomicInteger());
    for (Future<Set<String>> future : futures) {
        for (String s : future.get())
            counts.get(s).incrementAndGet();
    }
    return counts;
}

これらの行はスレッドセーフではありません。任意の数のスレッドが同じキーを更新できるため、結果は安全ではありません。

Integer count = mTable.get(currentString) + 1;
// another thread could be running here.
mTable.put(currentString,count);

簡単な回避策は、AtomicInteger を使用することです (コードも簡素化されます)。

private final ConcurrentHashMap<String, AtomicInteger> mTable;

for(Map.Entry<String, AtomicInteger> entry: mTable.entrySet()) 
    if(findStringInFile(entry.getKey(), mSearchableFile)) 
        entry.getValue().incrementAndGet();
于 2013-01-03T16:01:57.143 に答える