Java:将 N 个二维数组附加到单个二维数组中的有效方法

Question

预先感谢您的帮助。

我有 N 个维度完全相同的二维数组。我想将它们组合成一个二维数组。下面是一个只有 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的(可能是Arrays类？)。然而，可能有许多不同的方法可以做到这一点。考虑到这一点，最有效的方法是什么？

Answer 1

数组可以解释为具有行和列的矩阵。目标是创建一个结果矩阵，其中每一行都是所有输入矩阵的相应行的串联。

对于每一行，这基本上可以分为两个步骤:

• 从所有输入数组中选择相应的行
• 将这些行合并为一个结果行

所以问题的核心是:将多个数组连接成一个数组的最有效方法是什么？ (反过来，这可以被视为问题的概括:连接两个数组的最有效方法是什么？)

对于原始数组(例如 int[] 数组)，我可以想到三种基本方法:

• 使用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;
  }
  

• 使用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;
  }
  

• 使用IntStream

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

直觉上，我会把赌注押在System.arraycopy上。它基本上没有任何开销，并且可以归结为计算机可以执行的最基本操作之一 - 即:将内存从这里复制到那里。

<小时/>

旁注:在您的特定情况下，还有另一种可能的优化选项。即，对所有行并行调用此方法。但由于该操作完全受内存限制，并且内存传输速度在很大程度上与 CPU 数量无关，因此这可能没有明显的影响。

<小时/>

这是一个比较这三种方法的示例。

这不是一个完全可靠的基准。

但它考虑了一些微基准测试最佳实践，并给出了预期性能的粗略估计:

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;
    }

}

我的(旧的、慢速的)电脑上的输出是这样的:

 ...
 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 运行，我将不胜感激。