スレッド間で不均等数を分割する

Question

私はJavaでスレッドを学習しており、アルファベット順の単語のリストをソートしたいと思います。私のプログラムはtxtファイルの単語を読み込み、文字列配列に入れます。ユーザーは自分自身で使用するスレッドの数を選択できます。私はスレッドがそれ自身でソートできる偶数（可能な）チャンクで配列を分割したい。

だから私の質問に：

私もスレッド間で可能な限りArray.lengthとを分割することができますどのように？私の心は空っぽで、私はこれを行うための賢い方法を考えることができません。

例：22と4のスレッドのarray.lengthを持っている場合、どのようにスレッドをこのケースで与えることができますか。配列の6,6,5,5サイズの小片？与えられたすべての数字に適用する必要があります。

私はできる限り最高の説明をしようとしましたが、何か不明な点があればお尋ねください！ありがとうございました！

Answer 1

可能な限り均等にする必要はありません。 1つのスレッドが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); 
    }); 
} 

注を行うことができ、6

にアップしているどのように多くの問題ではありません。その場合には、それにかかる時間の長さを決定します：あなたはストリームを使用する場合.of（array）.parallel（）実際にはスレッドごとに2つのタスクを作成します。これにより、要素の数が同じであっても、一部のバッチが長くかかることが軽減されます。 n要素とkスレッドを考える

Answer 2

2つのフェーズで実行できます。 最初にスレッドの長さを残りの部分なしで分割してチャンクを取得します。 2番目：チャンクごとに残りの部分を分割します（チャンクごとに+1）。一部のチャンクは+1を取得しません。

Answer 3

、あなたは残りのスレッドに最初n % kスレッドへ1 + 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これにより、残りのスレッドより1つ多くの要素を取得するスレッドの数が得られます。

22/4 = 5.スレッドごとの要素の最小数を指定します。

配列を5つの要素に分割し、2つのスレッド（22％4）が残っているまでスレッドに割り当てます。それらに残りの（5 + 1 = 6）要素をそれぞれ割り当てます。

Answer 5

スレッドに「類似の」ワークロードがあることを確認するためには、均等な分布を見つけることが重要です。これは、要素の数に比べてスレッドの数が「多い」場合に特に重要です。この場合、スレッドが担当する要素の数が1以下であることを確認する必要があります。

これを達成するには、要素の数（あなたの場合は配列の長さ）をスレッドの数で割って残りの部分をタスク間で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はできます。ここでは[1,1,1,0]が必要ですが、これはアプリケーションの場合に応じて簡単に調整できます）。