Многопоточность - соответствие экземпляров - PullRequest
Новая
       14

Многопоточность - соответствие экземпляров

1 голос
/ 22 сентября 2011

Я хочу запустить два выражения XPath одновременно на двух ревизиях базы данных, которые оба возвращают результаты из Iterator / Iterable и сопоставляют результирующие узлы с узлами в списке.

Я думаю, что лучше всего запустить оба запроса в двух потоках из executorservice и сохранить результаты из обоих потоков в BlockingQueue, тогда как другой поток собирается отсортировать результаты из BlockingQueue или фактически сохранить входящие узлы или nodeKeys в правильном положении.

Тогда тривиально получить пересечение результирующего отсортированного списка и другого отсортированного списка.

Есть еще предложения? Я также могу свободно использовать любую технологию, которая мне нравится (желательно Java). Гуава в пути к классам, но я уже думал об использовании Актеров из Акки.

Редактировать: Еще один связанный с этим вопрос может быть связан с тем, быстрее ли использовать InsertionSort в конвейерном режиме (для обработки сгенерированных результатов XPath сразу после их получения) или дождаться, пока не будет создан весь результат, и использовать QuickSort или MergeSort. Я думаю, что InsertionSort должен быть предпочтительным независимо от полученного количества элементов.

В общем, я надеюсь, что сортировка и последующее вычисление пересечения двух списков выполняется быстрее, чем O(n^2), для поиска каждого элемента в списке результатов XPath, даже если список делится на количество доступных процессоров ЦП.

Edit: В настоящее время я реализовал первую часть: 

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 результирующие ключи узла добавляются к 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, но я думаю, что по крайней мере это должно работать, как вы думаете? Есть ли у вас какие-либо предпочтительные решения или я уже допустил некоторые ошибки?

С уважением,
Johannes

1 Ответ

0 голосов
/ 27 октября 2011

Вы уверены, что вам нужно сделать это одновременно? Разве вы не можете просто построить два списка последовательно и после этого выполнить сортировку / пересечение? - Это займет лот сложности от субъекта.

Я предполагаю, что пересечение невозможно, пока оба списка не заполнены полностью, я прав? Тогда никакая очередь или синхронизация не потребуются, просто заполните два списка / набора и, после этого, обработайте оба полных списка.

Но, может быть, я не совсем понимаю вашу точку зрения ...

...