多线程——匹配实例

Question

我想在数据库的两个修订版上同时运行两个 XPath 表达式，它们都从迭代器/可迭代器返回结果，并将结果节点与列表中的节点相匹配。

我认为最好的办法是在 executorservice 的两个线程中运行两个查询，并将两个线程的结果保存在 BlockingQueue 中，而另一个线程将对 BlockingQueue 中的结果进行排序code> 或者实际上将传入的节点或nodeKeys保存在正确的位置。

然后获得结果排序列表和另一个排序列表的交集就很简单了。

还有其他建议吗？我还可以自由地使用我喜欢的任何技术（最好是 Java）。 Guava 在类路径中，但我已经考虑过使用 Akka 中的 Actor。

编辑：另一个相关问题是，以管道方式使用 InsertionSort（在收到生成的 XPath 结果时对其进行处理）更快，还是等到整个结果生成并使用 QuickSort 或 MergeSort 更快。我认为无论结果元素的数量如何，插入排序应该是更可取的。

一般来说，我希望排序然后计算两个列表的交集比搜索 XPath 结果列表中的每个项目的 O(n^2) 更快，即使列表除以数字可用的 CPU 处理器数。

编辑： 我目前已经实现了第一部分：

final ExecutorService executor = Executors.newFixedThreadPool(2);
final AbsTemporalAxis axis =
    new NextRevisionAxis.Builder(mSession).setRevision(mRevision)
        .setIncludeSelf(EIncludeSelf.YES).build();
for (final IReadTransaction rtx : axis) {
    final ListenableFuture<Void> future =
        Futures.makeListenable(executor.submit(new XPathEvaluation(rtx, mQuery)));
    future.addListener(new Runnable() {
        @Override
        public void run() {
            try {
                mSemaphore.acquire();
            } catch (final InterruptedException e) {
                LOGWRAPPER.error(e.getMessage(), e);
            }
        }
    }, executor);
}
executor.shutdown();

final ExecutorService sameThreadExecutor = MoreExecutors.sameThreadExecutor();
sameThreadExecutor.submit(new XPathResult());
sameThreadExecutor.shutdown();
return null;

信号量初始化为 2，并在 XPathEvaluation 中将生成的 nodeKey 添加到 LinkedBlockingQueue 中。

然后我将对用注释表示的 XPathResults 进行排序，该注释尚未实现：

private final class XPathResult implements Callable<Void> {
    @Override
    public Void call() throws AbsTTException, InterruptedException {
        while (true) {
            final long key = mQueue.take();
            if (key == -1L) {
                break;
            }
            if (mSemaphore.availablePermits() == 0) {
                mQueue.put(-1L);
            }

            // Do InsertionSort.
        }

        return null;
    }
}

没有任何 JavaDoc，但我认为至少它应该可以工作，您认为呢？您有更好的解决方案吗？还是我到目前为止犯了一些错误？

亲切的问候，
约翰内斯

Answer 1

您确定需要同时执行此操作吗？您不能连续构建两个列表，然后执行排序/相交吗？ - 这将需要主题变得很多复杂性。

我认为在两个列表都完全填满之前无法进行相交，对吗？然后，不需要队列或同步，只需填充两个列表/集合，完成后处理两个完整列表。

但也许我不太明白你的意思......