java - 奇怪的并发行为

Question

我目前正在构建的这个应用程序中遇到奇怪的行为。

前言

我正在构建的这个应用程序有一个简单的目标——获取一组字符串并在多个文本文件中搜索每个字符串。该应用程序还跟踪每个字符串的唯一匹配项，即如果字符串“abcd”在文件 A 中出现 n 次，则只会计算一次。

由于此应用程序将主要处理大量文件和大量字符串，因此我决定通过创建一个实现 Runnable 的类并使用 ExecutorService 运行 Runnable 任务来在后台进行字符串搜索。我还决定研究字符串搜索的速度，所以我开始比较使用不同字符串匹配方法(即 String.contains()、String.indexOf())的时间>, Boyer-Moore 算法)。我从 http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html 抓取了 Boyer-Moore 算法的源代码。并将其包含在我的项目中。这是问题开始的地方......

问题

我注意到在使用 BoyerMoore 时，字符串搜索会返回不同的结果(每次我运行搜索时，找到的字符串数量会有所不同)类，所以我将其替换为 String.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;
    }
}

Answer 1

这应该表现得更好

• 每个文件只打开和关闭一次。
• 线程之间不共享数据，因此没有线程间开销(最终结果除外)

这会获取每个文件的匹配项并在单个线程中累积计数。

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;
}

---

这些行不是线程安全的。任意数量的线程都可以更新同一个 key ，因此结果是不安全的。

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();