Parallel processing of pairs of items from the list in Java8

Question

In Java8, having a List<Item> list I process it sequentially as below:

ConcurrentMap<String, Integer> map = new ConcurrentHashMap<String, Integer>();
for (int i1 = 0; i1 < list.size() - 1; i1++) {
    Item item1 = list.get(i1);
    for (int i2 = i1 + 1; i2 < list.size(); i2++) {
        Item item2 = list.get(i2);
        doSomething(item1, item2);
    }
}

So I process all ordered pairs of items from the list (index of item1 < index of item2). Now, I would like to run doSomething(item1, item2) function in parallel for each ordered pair. What would be the best strategy to achieve that? Interested in the fastest possible code. Java8 streams are welcome.

doSomething for instance does: map.put(item1.key + " " + item2.key, item1.val + item2.val);.

The number of ordered pairs is n * (n - 1) / 2 where n is the size of the list. I also consider to split the amount of job evenly to reach the load-balance (at the moment assume each pair's execution time is the same). So it is not required to call doSomething(item1, item2) function in parallel for each ordered pair, but possibly for a set of prepared pairs.

I rolled back the edit#4 which significantly changed the question meaning making existing answers inappropriate. If you have different question, please ask it instead of editing the old one. — Tagir Valeev
– Tagir Valeev, Commented Aug 13, 2015 at 2:05

Louis Wasserman · Accepted Answer · 2015-08-04 01:31:27Z

5

IntStream.range(0, list.size()).parallel()
   .forEach(i1 -> 
       IntStream.range(i1 + 1, list.size()).parallel()
           .forEach(i2 -> doSomething(list.get(i1), list.get(i2))));

This doesn't have to be nearly as complicated as any of the other answers.

answered Aug 4, 2015 at 1:31

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Tagir Valeev Over a year ago

@BrandonMcHomery, parallel stream does not create a separate thread for each pair. It works smarter.

Louis Wasserman Over a year ago

No, you should not, parallel streams will divide the work intelligently into a correctly sized thread pool. You don't need to worry about that for streams.

Nir Alfasi Over a year ago

@LouisWasserman can you explain your last comment a bit further? according to this my understanding is that .parallel() uses the ForkJoinPool

Louis Wasserman Over a year ago

@alfasin, sure, so what? It uses the common pool, which Java intelligently sizes.

Nir Alfasi Over a year ago

I wasn't criticising... I thought that you meant that it creates the pool, and wanted to learn if there is such a feature for ForkJoinPool (creating more instances of it)

Tagir Valeev · Accepted Answer · 2015-08-11 04:12:56Z

1

I've added the special feature to my StreamEx library (since version 0.3.6) just to solve this issue: EntryStream.ofPairs method:

EntryStream.ofPairs(list).parallel()
    .forKeyValue((item1, item2) -> doSomething(item1, item2));

If you don't mind using third-party library, you may try this. Internally it's different from the accepted solution. It splits the set of n*(n-1)/2 possible pairs as evenly as possible, so parallelism could be more effective in this case.

answered Aug 11, 2015 at 4:12

Tagir Valeev

101k19 gold badges233 silver badges346 bronze badges

Comments

Nir Alfasi · Accepted Answer · 2015-08-25 18:54:38Z

1

If you don't need to control the number of running threads (i.e. the list is relatively small) you can run them in parallel like this:

for (int i1 = 0; i1 < list.size() - 1; i1++) {
    Item item1 = list.get(i1);
    for (int i2 = i1 + 1; i2 < list.size(); i2++) {
        Item item2 = list.get(i2);
        new Thread(){
            @Override
            public void run() {
                doSomething(item1, item2);
            }
        }.start();
    }
}

If the list is long the code above will spin one thread for each pair of items which could effect performance really badly. In such a case I would use a ExecutorService and create a newFixedThreadPool to limit the number of threads that could be span up simultaneously:

ExecutorService executor = Executors.newFixedThreadPool(5);

for (int i1 = 0; i1 < list.size() - 1; i1++) {
    Item item1 = list.get(i1);
    for (int i2 = i1 + 1; i2 < list.size(); i2++) {
        Item item2 = list.get(i2);

        executor.execute(new Runnable(){
            @Override
            public void run() {
                doSomething(item1, item2);
            }
        });

    }
}

edited Aug 25, 2015 at 18:54

answered Aug 3, 2015 at 21:14

Nir Alfasi

53.6k11 gold badges94 silver badges138 bronze badges

2 Comments

Louis Wasserman Over a year ago

Creating a new thread for every pair of items is likely to have terrible performance.

Nir Alfasi Over a year ago

@LouisWasserman depends on the size of the list. If it's only a few items that shouldn't be too bad. That said, if the list is long, it would be a good idea to use a fixed-size threadpool. I'll add it to the answer - thanks!

Collectives™ on Stack Overflow

Parallel processing of pairs of items from the list in Java8

3 Answers 3

5 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related