划分线程之间的不平衡数

我刚刚在Java中学习线程，我想按字母顺序排列一个单词列表。我的程序读取一个txt文件的文字并把它们放在一个字符串数组中。用户可以选择他们想要使用的线程数。我想将数组拆分成尽可能多的块，以便线程可以自行排序。划分线程之间的不平衡数

所以我的问题：

我怎样才能跨越线程尽可能地均匀分割array.length？我的想法是空白，我想不出一个聪明的方式来做到这一点。

例如：如果我有一个22和4线程的array.length，在这种情况下如何给线程; 6,6,5和5个尺寸的阵列片？需要适用于每个给定的数字。

我试图解释它，我可以做到最好，请问是否有什么不清楚！谢谢！

来源

2016-04-18 Magnarok

事实上，你这样做是为了在线程之间分割工作，这在很大程度上是不相关的 - 你似乎在问如何将一个数组分割成N个大致相同大小的块。 –

它不需要尽可能均匀。如果一个线程有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（）它实际上为每个线程创建两个任务。这减轻了一些批次可能花费更长时间，即使它们具有相同数量的元素。

来源

2016-04-18 08:35:21

您是否尝试过有10个任务和8个线程？ – Marco13

@ Marco13最长的线程将最有可能有两个任务，这将决定完成它们需要多长时间。我注意到了你的观点+1注意：计算机很少与你一次使用的CPU数量成线性关系。如果您有5x2个任务线程，那么它们可能会比2x2 + 6x1更快，因为工作负载是平均的。 –

也许我在这里误解了一些东西，但是对于10个任务和8个线程，这似乎将'-4'（！）元素分配给最后一个线程（我没有做数学，只是试过了 - 它当然只是一个小错误，但对我来说似乎不对）。除此之外，还有很多细微之处：无关的系统工作量，实核与虚拟核心的数量，正在运行的其他线程，在那里完成的计算的类型*（IO与算术）以及一般的输入数字（例如，给4个线程提供100000个元素与7个元素 - 在第一种情况下，+/- 100可能无关紧要） – Marco13

您可以分两个阶段完成。第一：用线程数除长度而不用余数来得到块。第二：分割块之间的剩余部分 - 每个块1 +1。某些块不会获得+1。

来源

2016-04-18 08:34:55 omickron

鉴于n元素和k线程，你应该指定1 + n/k元素第一n % k线程，n/k元素，其余线程。

你的情况，你有n = 22和k = 4，所以... n/k = 5（四舍五入）和n%k = 2，所以首先2线程分配有5+1元素，其余2线程都分配给他们5。

来源

2016-04-18 08:37:07 CptBartender

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

22％4 = 2.这会给你一个元素比剩下的线程多的线程数。

22/4 = 5.这给你每个线程的最小元素数量。

现在开始将你的数组分成5个元素，并将它们分配给一个线程，直到剩下（22％4）个线程为止。将其余的（5 + 1 = 6）元素分配给它们。

来源

2016-04-18 08:37:55 Madhusudhan

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

为了达到这个目的，你可以计算除以元素数量（在你的情况下数组长度）除以线程数量的余数，并在任务中逐个分配这个余数。

_{前段时间我有同样的问题。实际上，我试图以稍微更一般的形式解决它，对于某些类需要计算开始和结束任意范围的间隔的指数（其不需要以索引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]，但这可以根据应用情况轻松调整）。

来源

2016-04-18 09:18:50 Marco13

划分线程之间的不平衡数

回答

相关问题