CODEWITHSUNDEEP
javamultithreadingparallel-processing
Badger
Badger

Reputation: 301

Iterating over single List in parallel without duplicates in Java

I have an ArrayList filled with 'someObject'. I need to iterate over this list, with 4 different threads (using Futures & Callables). The threads will keep the top 5 valued objects it comes across. I first tried creating a parallel stream, but that didn't work out so well. Is there some obvious thing I'm not thinking of, so each thread can iterate over the objects, without possibly grabbing the same object twice?

Upvotes: 1

Views: 245

Answers (2)

Creos
Creos

Reputation: 2525

You don't need AtomicInteger or any other synchronization for that matter.

You should simply logically partition your list (whose size is known upfront) based on the number of processing threads (whose number is also known upfront) and let each of them operate on its own section of [from, to) of the list.

This avoid the need for any synchronization at all (even if it's just an optimized one such as AtomicInteger) which is what you should always strive for (as long as it's safe).

Pseudo code

class Worker<T> implements Runnable {
    final List<T> toProcess;

    protected Worker(List<T> list, int fromInc, int toExcl){
       // note this does not allow passing an empty list or specifying an empty work section but you can relax that if you wish
       // this also implicitly checks the list for null
       Preconditions.checkArgument(fromInc >= 0 && fromInc < list.size());
       Preconditions.checkArgument(toExcl > 0 && fromInc <= list.size());
       // note: this does not create a copy, but only a view so it's very cheap
       toProcess = list.subList(fromInc, toExcl);
    }

    @Override
    public final void run() {
       for(final T t : toProcess) {
           process(t);
       }
    }

    protected abstract process(T t);
}

As with the AtomicInteger solution (really any solution which does not involve copying the list), this solution also assumes that you will not be modifying the list once you have handed it off to each thread and processing has commenced. Modifying the list while processing is in progress will result in undefined behavior.

Upvotes: 1

Zim-Zam O&#39;Pootertoot
Zim-Zam O&#39;Pootertoot

Reputation: 18148

You can use an AtomicInteger to iterate over the list:

class MyRunnable implements Runnable {
    final List<SomeObject> list;
    final AtomicInteger counter; // initialize to 0

    public void run() {
        while(true) {
            int index = counter.getAndIncrement();
            if(index < list.size()) {
                do something with list.get(index);
            } else {
                return;
            }
        }
    }
}

So long as each MyRunnable has the same AtomicInteger reference they won't duplicate indices

Upvotes: 1

Related Questions