Разделите неровное число между Threads

Question

Я просто изучаю темы на Java, и я хочу отсортировать список слов по алфавиту. Моя программа считывает слова txt-файла и помещает их в массив String. Пользователь может выбрать, сколько потоков они хотят использовать сами. Я хочу разделить массив на четные (насколько это возможно) куски, которые потоки могут сортировать сами по себе.

Так мой вопрос:

Как я могу расколоть array.length как можно ровнее по резьбе? Мой разум гаснет, и я не могу придумать разумный способ сделать это.

e.g: Если у меня есть array.length из 22 и 4 потоков, как можно передать потоки в этом случае; 6, 6, 5 и 5 размеров массива? Нужно быть применимым к каждому указанному числу.

Я попытался объяснить это как можно лучше, пожалуйста, спросите, если что-то неясно! Спасибо!

Answer 1

Это не должно быть как можно более равномерным. Если одна нить имеет 6, это будет определять продолжительность времени, необходимого в этом случае не имеет значения, сколько до 6.

Вы можете сделать

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); 
    }); 
} 

Примечание: если вы используете поток .of (array) .parallel() фактически создает две задачи для потока. Это смягчает то, что некоторые партии могут занимать больше времени, даже если они имеют одинаковое количество элементов.

Answer 2

Вы можете сделать это в два этапа. Во-первых: разделите длину с количеством потоков без остатка, чтобы получить куски. Второе: разделите остаток между кусками - +1 за каждый кусок. Некоторый кусок не получит +1.

Answer 3

Учитывая n элементов и k нити, вы должны назначить 1 + n/k элементов первых n % k нитей и n/k элементов остальных нитей.

В вашем случае, у вас есть n = 22 и k = 4, так что ... n/k = 5 (округление вниз) и n%k = 2, поэтому первые 2 потоки имеют 5+1 элементы, возложенные на них, а остальные 2 нити имеют 5 возложенные на них.

Answer 4

Позвольте мне просто привести ваш пример, поскольку его будет легко объяснить. 22 элемента среди 4 потоков.

22% 4 = 2. Это дает вам количество потоков, которые получат один элемент больше, чем остальные потоки.

22/4 = 5. Это дает минимальное количество элементов в потоке.

Теперь начните разделять массив на 5 элементов и назначьте их потоку каждый, пока вы не останетесь с (22% 4) 2 потоками. Назначьте их оставшимся (5 + 1 = 6) элементам каждый.

Answer 5

Чтобы убедиться, что потоки имеют «аналогичную» рабочую нагрузку, важно найти равномерное распределение. Это особенно важно, когда количество потоков «высокое» по сравнению с количеством элементов. В этом случае следует убедиться, что количество элементов, за которые отвечает поток, отличается не более чем на 1.

Для этого вы можете вычислить оставшуюся часть деления количества элементов (длина массива в вашем случае) на количество потоков и распределить этот остаток один за другим среди задач.

_{У меня была такая же проблема некоторое время назад. Фактически, я попытался разрешить его в несколько более общей форме для некоторого класса ParallelRangeExecutor, для чего потребовалось вычисление начала - и end индексов интервалов произвольного диапазона (который не нужно начинать с индекс 0). Это «извлекается» из этого класса следующие:}

import java.util.Arrays; 

public class EvenTaskDistribution 
{ 
    public static void main(String[] args) 
    { 
     test(22, 4); 
     test(21, 4); 
     test(100, 3); 
     test( 3, 4); 
    } 

    private static void test(int numElements, int parallelism) 
    { 
     int taskSizes[] = computeTaskSizes(parallelism, 0, numElements); 
     System.out.printf("Distributing %4d elements among %4d threads: %s\n", 
      numElements, parallelism, Arrays.toString(taskSizes)); 
    } 

    public static int[] computeTaskSizes(
     int parallelism, int globalMin, int globalMax) 
    { 
     if (parallelism <= 0) 
     { 
      throw new IllegalArgumentException(
       "Parallelism must be positive, but is " + parallelism); 
     } 
     if (globalMin > globalMax) 
     { 
      throw new IllegalArgumentException(
       "The global minimum may not be larger than the global " + 
       "maximum. Global minimum is "+globalMin+", " + 
       "global maximum is "+globalMax); 
     } 
     int range = globalMax - globalMin; 
     if (range == 0) 
     { 
      return new int[0]; 
     } 
     int numTasks = Math.min(range, parallelism); 
     int localRange = (range - 1)/numTasks + 1; 
     int spare = localRange * numTasks - range; 
     int currentIndex = globalMin; 
     int taskSizes[] = new int[numTasks]; 
     for (int i = 0; i < numTasks; i++) 
     { 
      final int min = currentIndex; 
      final int max = min + localRange - (i < spare ? 1 : 0); 
      taskSizes[i] = max - min; 
      currentIndex = max; 
     } 
     return taskSizes; 
    } 
} 

Выход

Distributing 22 elements among 4 threads: [5, 5, 6, 6] 
Distributing 21 elements among 4 threads: [5, 5, 5, 6] 
Distributing 100 elements among 3 threads: [33, 33, 34] 
Distributing 3 elements among 4 threads: [1, 1, 1] 

(последний показывает один из случаев угловыми, что один, возможно, придется учитывать Например, один мог. ожидайте здесь [1,1,1,0], но это можно легко настроить в зависимости от случая приложения).