Divide an uneven number between Threads

Question

I am just learning Threads in Java and I want to sort a list of words alphabetical. My program read the words of a txt-file and put them in a String-array. The user can choose how many threads they want to use themselves. I want to split the array in even (as possible) chunks that the threads can sort by themselves.

So to my question:

How can I split the array.length as even as possible across the threads? My mind is blanking and I can't think of a smart way to do this.

e.g: If I have a array.length of 22 and 4 threads, how can give the threads in this case; 6, 6, 5 and 5 sized pieces of the array? Needs to be applicable to every number given.

I tried to explain it the best I could, please ask if something was unclear! Thank you!

Answer 1

Let me just take your example as it will be easy to explain. 22 elements amongst 4 threads.

22 % 4 = 2. This gives you the number of threads that will get one element more than the remaining threads.

22 / 4 = 5. This gives you the minimum number of elements per thread.

Now start dividing your array into 5 elements and assign them to a thread each till you are left with (22%4) 2 threads. Assign them the remaining (5+1=6) elements each.

Answer 2

It doesn't need to be as evenly as possible. If one thread has 6, this will determine the length of time it takes in which case it doesn't matter how many are up to 6.

You can do

int chunkSize = (tasks + threads - 1) / threads; // divide by threads rounded up.
for (int t = 0; t < threads; t++) {
    int start = t * chunksSize;
    int end = Math.min(start + chunkSize, tasks);
    executor.submit(() -> {
         // inside the thread
         for (int i = start; i < end; i++) {
             process(i);
    });
}

Note: if you use Stream.of(array).parallel() it actually create two tasks per thread. This mitigates that some batches might take longer even though they have the same number of elements.