This discussion is archived
2 Replies Latest reply: May 31, 2013 1:05 PM by 966867 RSS

Looking for right pattern for executing competing algorithms

1012159 Newbie
Currently Being Moderated
Hi all. I'm new to concurrency and am looking for some guidance on the 'best' way to accomplish something.

Background: Extremely abstract example here. There is some task(s) to accomplish. The tasks can vary greatly from one another in complexity. There are a number of algorithms available which could all be used to solve these tasks. However, no one algorithm dominates the others for all cases. It is also very challenging to profile the tasks and algorithms to effectively match them to the optimal algorithm. Performance varies such that task/algorithm combinations could take seconds, minutes, or hours to complete.

Given n algorithms in our portfolio (lets say 4 for example), when a task is presented, we wish to run all 4 algorithms concurrently. As soon as one algorithm completes the task, we will terminate the others and use the results from the first finisher. (So, it's a cut-throat winner-take-all race)


So far in reading the concurrent java examples out there, I've yet to see anything that would/could match this scenario.

Any guidance?
  • 1. Re: Looking for right pattern for executing competing algorithms
    jtahlborn Expert
    Currently Being Moderated
    The ExecutorCompletionService has pretty much this exact example in the javadoc.
  • 2. Re: Looking for right pattern for executing competing algorithms
    966867 Newbie
    Currently Being Moderated
    Few years ago I implemented a competition sorting algorithm: The idea was to use different sorting algorithms to sort the same array concurrently. All algorithms accessed concurrently a single array-instance at the same time. If one of sorting algorithms was finished then other algorithms were canceled.

    I adapted few sorting algorithms like in place quick sort, insertion sort thus they could work on the same array without disturbing each other. To lock many variables at ones I used a scheduler which avoided deadlocks. Suddenly final sorting algorithm was very slow because the most of time was consumed by data-access and synchronization.

    Here you can find the scheduler implementation:
    https://sourceforge.net/p/happy-guys/wiki/MultiLock-MultiSynchronization/

    Best Regards
    Andrej

    Edited by: zarr on 31.05.2013 22:05

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points