Reputation: 123
I am looking to divide up an array to process in parallel, but am struggling to split up the array when the size does not divide nicely by the number of threads (since it rounds down). I think I am missing something obvious, but how could I handle this? I can't just round up, since then it would go past the index.
final int NUM_THREADS = Integer.parseInt(args[1]);
int size = g.nodes.length / NUM_THREADS;
for( int i = 0; i < NUM_THREADS; i++ ) {
Runnable task = new GraphSortRunnable(i*size, (i+1)*size, g.nodes);
// code continues
}
Upvotes: 0
Views: 1408
Reputation: 159215
Solution
Now, if your goal is 2 chunks, then 13 / 2 = 6.5, but 13 / 6 = 2 + 1/2, so still not good. You have to round up, which is called ceiling
.
So, two ways to round up when doing int
calculations.
Convert to double
and use Math.ceiling()
: chunkSize = (int)Math.ceiling((double)arraySize / (double)threadCount)
.
Rely of the fact that int / int
is always rounded down (truncated), so ceiling(a/b) = truncate((a + b - 1) / b)
, or in your case: chunkSize = (arraySize + threadCount - 1) / threadCount
.
Example
If you had 10 values and 4 threads, the above code would result in chunk size of 3, so your threads would likely get 3,3,3,1.
If you want 3,3,2,2, it gets more complicated. Basically, repeat the chunk size calculation after each chunk is calculated.
CODE
And finally to prove my point, here's the code:
public static void main(String[] args) {
System.out.println(splitEvenly(10, 2));
System.out.println(splitEvenly(10, 3));
System.out.println(splitEvenly(10, 4));
System.out.println(splitEvenly(500, 13));
System.out.println(splitEvenly(5, 10));
}
public static List<Integer> splitEvenly(int valueCount, int threadCount) {
List<Integer> chunks = new ArrayList<>();
int valuesLeft = valueCount;
for (int threadsLeft = threadCount; threadsLeft > 0; threadsLeft--) {
int chunk = (valuesLeft + threadsLeft - 1) / threadsLeft;
chunks.add(chunk);
valuesLeft -= chunk;
}
return chunks;
}
Output:
[5, 5]
[4, 3, 3]
[3, 3, 2, 2]
[39, 39, 39, 39, 39, 39, 38, 38, 38, 38, 38, 38, 38]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
Upvotes: 2
Reputation: 4305
You can use Java8 stream API. It is simpler than custom splitting:
public class Main {
public static void main(String[] args) throws Exception {
Object[] gnode = new Object[10];
Arrays.stream(gnode).parallel().forEach(Main::processOneNode);
}
public static void processOneNode(Object node){
System.out.println(Thread.currentThread().getName());
}
}
You can customize it. See Custom thread pool in Java 8 parallel stream
ForkJoinPool forkJoinPool = new ForkJoinPool(20);
forkJoinPool.submit(() -> Arrays.stream(gnode).parallel().forEach(Main::processOneNode)).get();
Upvotes: 2