劃分線程之間的不平衡數

我剛剛在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

劃分線程之間的不平衡數

回答

相關問題