Java：N 2dアレイを単一の2次元アレイに追加する効率的な方法

Question

ご協力いただきありがとうございます。

私は正確に同じ次元を持つN 2d配列を持っています。私はこれらを1つの2D配列に結合したいと考えています。以下は、2つの2次元配列のみの例です。

array1 = [[1 2] 
      [3 4] 
      [5 6]] 

array2 = [[7 8] 
      [9 1] 
      [2 3]] 

result = [[1 2 7 8] 
      [3 4 9 1] 
      [5 6 2 3]] 

これを行う最も効率的な方法は何ですか？これらのアレイは、場合によっては20x10000のオーダーで非常に大きくなる可能性があります。素朴なアプローチはforループを使用することですが、これは非常に効率的ではありません。特にこの操作をかなり頻繁にやりたいからです。私はまた、いくつかのJavaのビルドメソッド（配列クラス可能性がありますか？）を使用することができると思われる。しかし、それを行う方法はさまざまです。それを念頭において、これを行う最も効率的な方法は何ですか？

Answer 1

アレイは、行と列のマトリックスとして解釈することができます。目標は、各行がすべての入力行列の対応する行の連結である結果行列を作成することです。各行について

が、これは基本的に2つの段階に分けることができる：単一の結果行にこれらの行を結合し、すべての入力アレイ

から

• 選択各行

だから問題の核心は、複数の配列を1つの配列に連結する最も効率的な方法は何でしょうか？ （そして、今度は、はとなります。2つのアレイを連結する最も効率的な方法は何ですか？プリミティブ配列（例えば、int[]アレイ）について）

、私はこのための3つの基本的な方法を考えることができる：IntBuffer

private static int[] combineWithBuffer(int[]... arrays) 
{ 
    // Assuming the same length for all arrays! 
    int length = arrays[0].length; 
    int result[] = new int[arrays.length * length]; 
    IntBuffer buffer = IntBuffer.wrap(result); 
    for (int i = 0; i < arrays.length; i++) 
    { 
     buffer.put(arrays[i]); 
    } 
    return result; 
} 

を使用System.arraycopy

private static int[] combineWithArraycopy(int[]... arrays) 
{ 
    // Assuming the same length for all arrays! 
    int length = arrays[0].length; 
    int result[] = new int[arrays.length * length]; 
    for (int i = 0; i < arrays.length; i++) 
    { 
     System.arraycopy(arrays[i], 0, result, i * length, length); 
    } 
    return result; 
} 

を使用

• 使用IntStream

  private static int[] combineWithStreams(int[] ... arrays) 
  { 
      return Stream.of(arrays).flatMapToInt(IntStream::of).toArray(); 
  } 
  

直感的に、私はSystem.arraycopyに私のベットを置くと思います。基本的にオーバーヘッドはなく、コンピュータが実行できる最も基本的な操作の1つになる - つまり：ここからそこへコピーメモリ。

---

サイドノート：特定のケースでは、最適化のための別のオプションがあります。つまり、すべての行に対してこのメ​​ソッドを呼び出すには、を並列ににします。しかし、操作はメモリにのみ依存し、メモリ転送速度はCPUの数にほとんど依存しないため、これは顕著な効果はありません。

---

ここでは、3つのアプローチを比較する例を示します。

これは完全に信頼できるベンチマークではありません。

しかし、それは考慮にいくつかのmicrobenchmarkingベストプラクティスを取り、もう1つは期待できるパフォーマンスの概算を与える：

import java.nio.IntBuffer; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
import java.util.Locale; 
import java.util.concurrent.Callable; 
import java.util.concurrent.ExecutorService; 
import java.util.concurrent.Executors; 
import java.util.concurrent.LinkedBlockingQueue; 
import java.util.concurrent.ThreadPoolExecutor; 
import java.util.concurrent.TimeUnit; 
import java.util.function.Function; 
import java.util.stream.IntStream; 
import java.util.stream.Stream; 

public class ArraycopyStreamPerformance 
{ 
    public static void main(String[] args) 
    { 
     basicTest(); 

     int runs = 100; 
     int minNum = 2; 
     int maxNum = 8; 
     int minRows = 2; 
     int maxRows = 20; 
     int minCols = 100; 
     int maxCols = 10000; 
     for (int num = minNum; num <= maxNum; num *= 2) 
     { 
      for (int rows = minRows; rows <= maxRows; rows += 2) 
      { 
       for (int cols = minCols; cols <= maxCols; cols *= 10) 
       { 
        runTest(num, rows, cols, runs); 
       } 
      } 
     } 
    } 

    private static void runTest(int num, int rows, int cols, int runs) 
    { 
     int arrays[][][] = new int[num][rows][cols]; 

     long before = 0; 
     long after = 0; 

     int blackHole = 0; 

     // arraycopy 
     before = System.nanoTime(); 
     for (int i = 0; i < runs; i++) 
     { 
      int resultA[][] = combineRows(
       ArraycopyStreamPerformance::combineWithArraycopy, arrays); 
      blackHole += resultA[0][0]; 
     } 
     after = System.nanoTime(); 

     System.out.printf(Locale.ENGLISH, 
      "%2d arrays, %3d rows, %6d cols, arraycopy   : %8.3fms\n", 
      num, rows, cols, (after - before)/1e6); 


     // arraycopy parallel 
     before = System.nanoTime(); 
     for (int i = 0; i < runs; i++) 
     { 
      int resultA[][] = combineRowsParallel(
       ArraycopyStreamPerformance::combineWithArraycopy, arrays); 
      blackHole += resultA[0][0]; 
     } 
     after = System.nanoTime(); 

     System.out.printf(Locale.ENGLISH, 
      "%2d arrays, %3d rows, %6d cols, arraycopy parallel: %8.3fms\n", 
      num, rows, cols, (after - before)/1e6); 


     // buffer 
     before = System.nanoTime(); 
     for (int i = 0; i < runs; i++) 
     { 
      int resultB[][] = combineRows(
       ArraycopyStreamPerformance::combineWithBuffer, arrays); 
      blackHole += resultB[0][0]; 
     } 
     after = System.nanoTime(); 

     System.out.printf(Locale.ENGLISH, 
      "%2d arrays, %3d rows, %6d cols, buffer   : %8.3fms\n", 
      num, rows, cols, (after - before)/1e6); 


     // buffer parallel 
     before = System.nanoTime(); 
     for (int i = 0; i < runs; i++) 
     { 
      int resultB[][] = combineRowsParallel(
       ArraycopyStreamPerformance::combineWithBuffer, arrays); 
      blackHole += resultB[0][0]; 
     } 
     after = System.nanoTime(); 

     System.out.printf(Locale.ENGLISH, 
      "%2d arrays, %3d rows, %6d cols, buffer parallel: %8.3fms\n", 
      num, rows, cols, (after - before)/1e6); 


     // streams 
     before = System.nanoTime(); 
     for (int i = 0; i < runs; i++) 
     { 
      int resultC[][] = combineRows(
       ArraycopyStreamPerformance::combineWithStreams, arrays); 
      blackHole += resultC[0][0]; 
     } 
     after = System.nanoTime(); 

     System.out.printf(Locale.ENGLISH, 
      "%2d arrays, %3d rows, %6d cols, stream   : %8.3fms (" + 
      blackHole + ")\n", num, rows, cols, (after - before)/1e6); 
    } 



    private static void basicTest() 
    { 
     int array1[][] = 
     { 
      { 1, 2 }, 
      { 3, 4 }, 
      { 5, 6 } 
     }; 

     int array2[][] = 
     { 
      { 7, 8 }, 
      { 9, 1 }, 
      { 2, 3 } 
     }; 

     int result[][] = 
     { 
      { 1, 2, 7, 8 }, 
      { 3, 4, 9, 1 }, 
      { 5, 6, 2, 3 } 
     }; 
     System.out.println(Arrays.deepToString(result)); 

     int resultA[][] = combineRows(
      ArraycopyStreamPerformance::combineWithArraycopy, array1, array2); 
     System.out.println(Arrays.deepToString(resultA)); 
     int resultB[][] = combineRows(
      ArraycopyStreamPerformance::combineWithBuffer, array1, array2); 
     System.out.println(Arrays.deepToString(resultB)); 
     int resultC[][] = combineRows(
      ArraycopyStreamPerformance::combineWithStreams, array1, array2); 
     System.out.println(Arrays.deepToString(resultC)); 
    } 




    private static int[][] selectRows(int row, int[][]... arrays) 
    { 
     int result[][] = new int[arrays.length][]; 
     for (int j = 0; j < arrays.length; j++) 
     { 
      result[j] = arrays[j][row]; 
     } 
     return result; 
    } 

    private static int[][] combineRows(
     Function<int[][], int[]> mergeFunction, int[][]... arrays) 
    { 
     int rows = arrays[0].length; 
     int result[][] = new int[rows][]; 
     for (int i = 0; i < rows; i++) 
     { 
      result[i] = mergeFunction.apply(selectRows(i, arrays)); 
     } 
     return result; 
    } 

    private static int[] combineWithArraycopy(int[]... arrays) 
    { 
     // Assuming the same length for all arrays! 
     int length = arrays[0].length; 
     int result[] = new int[arrays.length * length]; 
     for (int i = 0; i < arrays.length; i++) 
     { 
      System.arraycopy(arrays[i], 0, result, i * length, length); 
     } 
     return result; 
    } 

    private static int[] combineWithBuffer(int[]... arrays) 
    { 
     // Assuming the same length for all arrays! 
     int length = arrays[0].length; 
     int result[] = new int[arrays.length * length]; 
     IntBuffer buffer = IntBuffer.wrap(result); 
     for (int i = 0; i < arrays.length; i++) 
     { 
      buffer.put(arrays[i]); 
     } 
     return result; 
    } 

    private static int[] combineWithStreams(int[] ... arrays) 
    { 
     return Stream.of(arrays).flatMapToInt(IntStream::of).toArray(); 
    } 



    private static final ExecutorService EXECUTOR_SERVICE = 
     createFixedTimeoutExecutorService(
      Runtime.getRuntime().availableProcessors(), 5, TimeUnit.SECONDS); 

    public static ExecutorService createFixedTimeoutExecutorService(
     int poolSize, long keepAliveTime, TimeUnit timeUnit) 
    { 
     ThreadPoolExecutor e = 
      new ThreadPoolExecutor(poolSize, poolSize, 
       keepAliveTime, timeUnit, new LinkedBlockingQueue<Runnable>()); 
     e.allowCoreThreadTimeOut(true); 
     return e; 
    } 

    private static int[][] combineRowsParallel(
     Function<int[][], int[]> mergeFunction, int[][]... arrays) 
    { 
     int rows = arrays[0].length; 
     int result[][] = new int[rows][]; 
     List<Callable<Object>> tasks = new ArrayList<Callable<Object>>(); 
     for (int i = 0; i < rows; i++) 
     { 
      int index = i; 
      tasks.add(Executors.callable(() -> 
      { 
       result[index] = mergeFunction.apply(selectRows(index, arrays)); 
      })); 
     } 
     try 
     { 
      EXECUTOR_SERVICE.invokeAll(tasks); 
     } 
     catch (InterruptedException e) 
     { 
      Thread.currentThread().interrupt(); 
     } 
     return result; 
    } 

} 

私の（古い、遅い）PC上の出力は、この線に沿っています：

... 
8 arrays, 20 rows, 10000 cols, arraycopy   : 354.977ms 
8 arrays, 20 rows, 10000 cols, arraycopy parallel: 327.749ms 
8 arrays, 20 rows, 10000 cols, buffer   : 328.717ms 
8 arrays, 20 rows, 10000 cols, buffer parallel: 312.522ms 
8 arrays, 20 rows, 10000 cols, stream   : 2044.017ms (0) 

並列化は努力の価値、そして一般的になり何のスピードアップをもたらしていないことを示す、arraycopyとIntBufferベースのアプローチは、ほぼ同じ性能を持っています。

YMMV。誰かがJMHを実行するために忍耐を持っているなら、私はそれを感謝します。

Answer 2

私の意見では、この種の配列を持つforループを使用するほうが、ストリームやリストを使うほうが良いでしょう。

しかし、それはちょうど私の意見です...

私は（作成のオーバーヘッドをスレッドに起因する小さなアレイ用のやり過ぎである）マルチスレッドと思います。マルチスレッド化は、20 * 10000のサイズの配列でさえ、過剰なものになる可能性があります。ただし、複数回実行する必要がある場合は、executorServiceを使用できます。しかし、それはあなたのニーズによって異なり...

は、ここに例を示します

public static void main(String[] args) { 
    test(100, 20, 3); 
    test(7, 3, 4); 
    test(3,7,4); 
} 

private static void test(int outerSize, int innerSize, int numberOfArrays) { 
    int[][][] arrays = new int[numberOfArrays][outerSize][innerSize]; 
    int[][] resultArray; 
    int counter = 0; 
    System.out.println("Testing " + numberOfArrays + " arrays, " + outerSize + " by " + innerSize); 
    for (int arrayIndex = 0; arrayIndex < numberOfArrays; arrayIndex++) 
     for (int outerIndex = 0; outerIndex < outerSize; outerIndex++) { 
      for (int innerIndex = 0; innerIndex < innerSize; innerIndex++) { 
       arrays[arrayIndex][outerIndex][innerIndex] = counter++; 
      } 
     } 
    // Change number of threads here; 
    resultArray = new ArrayCombiner(5, arrays).combine(); 
    System.out.println(Arrays.deepToString(resultArray)); 
} 

static class ArrayCombiner { 
    private final int[][][] sources; 
    private final int[][] resultArray; 
    private final int innerSourceLength, outerSourceLength, numberOfThreads; 

    public ArrayCombiner(int numberOfThreads, int[][]... sources) { 
     this.sources = sources; 
     this.numberOfThreads = numberOfThreads; 
     resultArray = new int[outerSourceLength = sources[0].length][(innerSourceLength = sources[0][0].length) 
       * sources.length]; 
    } 

    public int[][] combine() { 
     if (numberOfThreads <= 1) { 
      combinePortion(0, outerSourceLength); 
     } else { 
      Thread[] threads = new Thread[numberOfThreads]; 
      for (int i = 0; i < numberOfThreads; i++) { 
       (threads[(int) i] = new Thread(runnableToCombinePortion(i))).start(); 
      } 
      for (int i = 0; i < numberOfThreads; i++) { 
       try { 
        threads[i].join(); 
       } catch (InterruptedException e) { 
        e.printStackTrace(); 
       } 
      } 
     } 
     return resultArray; 
    } 

    private Runnable runnableToCombinePortion(int threadIndex) { 
     int outerFrom = (int) ((float) threadIndex/numberOfThreads * outerSourceLength), 
       outerTo = (int) ((float) (1 + threadIndex)/numberOfThreads * outerSourceLength); 
     return() -> { 
      combinePortion(outerFrom, outerTo); 
     }; 
    } 

    private void combinePortion(int outerFrom, int outerTo) { 
     for (int outerIndex = outerFrom; outerIndex < outerTo; outerIndex++) { 
      for (int sourceIndex = 0; sourceIndex < sources.length; sourceIndex++) { 
       System.arraycopy(sources[sourceIndex][outerIndex], 0, resultArray[outerIndex], 
         sourceIndex * innerSourceLength, innerSourceLength); 
      } 
     } 
    } 
} 

Answer 3

はこれを試してみてください。

static int[][] append(int[][]... matrices) { 
    int size = matrices.length; 
    int rows = matrices[0].length; 
    int cols = matrices[0][0].length; 
    int[][] result = new int[rows][cols * size]; 
    for (int i = 0; i < rows; ++i) 
     for (int j = 0, k = 0; j < size; ++j, k += cols) 
      System.arraycopy(matrices[j][i], 0, result[i], k, cols); 
    return result; 
} 

そして

int[][] a = {{1, 2}, {3, 4}, {5, 6}}; 
int[][] b = {{7, 8}, {9, 1}, {2, 3}}; 
int[][] result = append(a, b); 
for (int[] e : result) 
    System.out.println(Arrays.toString(e)); 

結果：

[1, 2, 7, 8] 
[3, 4, 9, 1] 
[5, 6, 2, 3]