Multithreading - instances de correspondance

Question

Je souhaite exécuter simultanément deux expressions XPath sur deux révisions d'une base de données qui renvoient les résultats d'un Iterator/Iterable et correspondent aux nœuds résultants avec des nœuds dans une liste.

Je pense que la meilleure chose est d'exécuter les deux requêtes dans deux threads d'un ExecutorService et enregistrer les résultats des deux fils dans un BlockingQueue, alors qu'un autre thread va trier les résultats de l'BlockingQueue ou enregistre effectivement les nœuds ou nodeKeys entrants dans la bonne position.

Ensuite, il est trivial d'obtenir l'intersection de la liste triée résultante et d'une autre liste triée.

D'autres suggestions? Je suis également libre d'utiliser n'importe quelle technologie que j'aime (de préférence Java). La goyave est dans le classpath, mais j'ai déjà pensé à utiliser des acteurs d'Akka. Edit: Une autre question connexe serait de savoir s'il était plus rapide d'utiliser InsertionSort de manière pipeline (pour traiter les résultats XPath générés dès leur réception) ou d'attendre que le résultat entier soit généré et d'utiliser QuickSort ou MergeSort . Je pense que InsertionSort devrait être préférable quel que soit le nombre d'éléments qui en résulte. En général j'espère que le tri et le calcul de l'intersection de deux listes est plus rapide que O(n^2) pour la recherche de chaque élément dans la liste de résultats XPath, même si la liste est divisée par le nombre de processeurs CPU disponibles.

Edit: Je suis actuellement implémentés la première partie:

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; 

Le sémaphores est initialisée à 2 et XPathEvaluation les nodeKeys résultants sont ajoutés à un LinkedBlockingQueue.

Alors je vais trier les XPathResults dénotés avec le commentaire, qui ne sont pas encore mis en œuvre:

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

Sans JavaDoc, mais je pense au moins il devrait fonctionner, que pensez-vous? Avez-vous des solutions préférables ou ai-je déjà fait quelques erreurs?

salutations les,
Johannes

Answer 1

Etes-vous sûr que vous devez faire en même temps? Ne pouvez-vous pas construire les deux listes consécutivement et ensuite effectuer votre tri/intersection? - Cela prendrait un lot de la complexité du sujet.

Je suppose que l'intersection ne peut pas être faite tant que les deux listes ne sont pas complètement remplies, ai-je raison? Ensuite, aucune file d'attente ou synchronisation ne serait nécessaire, il suffit de remplir deux listes/ensembles et, une fois terminé, de traiter les deux listes complètes.

Mais peut-être que je ne comprends pas vraiment ...