Threads之间划分一个奇数

Question

我刚刚在 Java 中学习线程，我想按字母顺序对单词列表进行排序。我的程序读取一个 txt 文件的单词并将它们放入一个字符串数组中。用户可以自己选择要使用多少个线程。我想将数组分成均匀（尽可能）线程可以自行排序的块。

所以对于我的问题：

如何在线程中尽可能均匀地拆分 array.length？我脑子一片空白，我想不出一个聪明的方法来做到这一点。

例如：如果我有一个 22 和 4 线程的 array.length，在这种情况下如何给线程； 6、6、5 和 5 大小的数组？需要适用于给定的每个数字。

我尽量解释清楚了，有什么不明白的地方请追问！谢谢！

Answer 1

您可以分两个阶段进行。第一：将长度除以线程数，没有余数得到块。第二：将剩余部分拆分为块 - 每个块 +1。某些区块不会获得 +1。

Answer 2

不需要越均匀越好。如果一个线程有 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);
    });
}

注意：如果您使用 Stream.of(array).parallel() 它实际上会为每个线程创建两个任务。这缓解了某些批次可能需要更长的时间，即使它们具有相同数量的元素。

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

让我举个例子，因为它很容易解释。 4 个线程中的 22 个元素。

22 % 4 = 2。这为您提供了比剩余线程多获得一个元素的线程数。

22 / 4 = 5。这为您提供了每个线程的最小元素数。

现在开始将您的数组分成 5 个元素，并将它们分别分配给一个线程，直到剩下 (22%4) 个线程。将剩余的 (5+1=6) 个元素分别分配给它们。

Answer 5

为了确保线程具有 "similar" 工作负载，找到均匀分布很重要。当线程数与元素数相比 "high" 时，这一点尤为重要。对于这种情况，应该确保线程负责的元素数量最多相差 1。

为此，您可以计算元素数（在您的情况下为数组长度）除以线程数的余数，并将余数一个一个地分配给任务。

_{我刚才也遇到了同样的问题。事实上，我试图以更一般的形式解决它，对于一些 ParallelRangeExecutor class，这需要计算 start- 和 end 任意范围区间的索引（不需要以索引0开头）。以下是来自这个class的"extracted"：}

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]。但这可以根据应用情况轻松调整）。

Answer 6

实现@MS Srikkanth 的观点。

{
     int threadCount = 4;
     ExecutorService executorService = Executors.newFixedThreadPool(threadCount);
     int numberOfTasks = 22;
     int chunkSize = numberOfTasks / threadCount;
     int extras = numberOfTasks % threadCount;

     int startIndex, endIndex = 0;

     for(int threadId = 0; threadId < threadCount; threadId++){
         startIndex = endIndex;
         if(threadId < (threadCount-extras)) {
             endIndex = Math.min(startIndex + chunkSize, numberOfTasks);
         }else{
             endIndex = Math.min(startIndex + chunkSize + 1, numberOfTasks);
         }


         int finalStartIndex = startIndex;
         int finalEndIndex = endIndex;
         executorService.submit(() -> {
             log.info("Running tasks from startIndex: {}, to endIndex: {}, total : {}", finalStartIndex, finalEndIndex-1, finalEndIndex-finalStartIndex);
             for (int i = finalStartIndex; i < finalEndIndex; i++) {
                  process(i);
             }
         });
     }
     executorService.shutdown();
}

Threads之间划分一个奇数

Divide an uneven number between Threads

java

arrays

algorithm

multithreading

java-threads