4

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

前言

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

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

问题

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