在Java中高效实现多维数组？

据我所知（从这样的答案），java没有原生的多维连续内存数组（ 例如，与C＃不同 ）。

虽然锯齿状数组语法（数组数组）可能对大多数应用程序都有好处，但我仍然想知道如果你想要连续内存数组的原始效率（避免不必要的内存读取），最佳做法是什么

我当然可以使用映射到2D的一维数组，但我更喜欢更结构化的东西。

Answer 1

手动操作并不困难：

int[] matrix = new int[ROWS * COLS]; int x_i_j = matrix[ i*COLS + j ]; 

现在，它真的比java的多维数组快吗？

 int x_i_j = matrix[i][j]; 

对于随机访问，也许。 对于连续访问，可能不是 – matrix[i]几乎肯定在L1缓存中，如果不在寄存器缓存中。 在最佳情况下， matrix[i][j]需要一次加法和一次内存读取; 而matrix[i*COLS + j]可能需要2次加法，一次乘法，一次内存读取。 但谁在数呢？

Answer 2

这取决于您的访问模式。 使用这个简单的程序 ，将int[][]与作为矩阵处理的1D int[]数组中的2D映射进行比较，本机Java 2D矩阵是：

1. 当行在缓存上时，速度提高25％，即：按行访问：
2. 当行不在缓存中时，缓慢100％，即：通过colums访问：

即：

 // Case #1 for (y = 0; y < h; y++) for (x = 0; x < w; x++) // Access item[y][x] // Case #2 for (x = 0; x < w; x++) for (y = 0; y < h; y++) // Access item[y][x] 

1D矩阵计算如下：

 public int get(int x, int y) { return this.m[y * width + x]; } 

Answer 3

如果你真的想要一个带有连续内存数组的更多结构，请将它包装在一个对象中。

 public class My2dArray { int sizeX; private T[] items; public My2dArray(int x, int y) { sizeX = x; items = new T[x*y]; } public T elementAt(int x, int y) { return items[x+y*sizeX]; } } 

不是一个完美的解决方案，你可能已经知道了。 因此，请考虑确认您怀疑是真实的。

Java仅提供用于组织代码的某些构造，因此最终您必须达到类或接口。 由于这也需要特定的操作，因此您需要一个类。

性能影响包括为每个arrays访问创建JVM堆栈帧，并且理想的是避免这样的事情; 但是，JVM堆栈框架是JVM 如何实现它的范围。 代码组织需要适当的范围，因此我无法想象这种性能影响（不违反“一切都是对象”的精神）。

Answer 4

示例实现，没有编译器。 这基本上是当你访问多维数组时C / C ++在幕后做的事情。 当小于指定的实际尺寸时，您将不得不进一步定义访问者行为，依此类推。 开销将是最小的，可以进一步优化，但这是微优化imho。 而且，在JIT开始之后，你实际上从未真正知道引擎盖下发生了什么。

 class MultiDimentionalArray { //disclaimer: written within SO editor, might contain errors private T[] data; private int[] dimensions; //holds each dimensions' size public MultiDimensionalArray(int... dims) { dimensions = Arrays.copyOf(dims, dims.length); int size = 1; for(int dim : dims) size *= dim; data = new T[size]; } public T access(int... dims) { int idx = 1; for(int i = 0; i < dims.length) idx += dims[i] * dimensions[i]; //size * offset return data[idx]; } } 

Answer 5

假设您有一个2D数组int[][] a = new int[height][width] ，所以按照惯例你有索引a[y][x] 。 根据您表示数据的方式以及访问方式，性能的变化范围为20：

代码：

 public class ObjectArrayPerformance { public int width; public int height; public int m[]; public ObjectArrayPerformance(int w, int h) { this.width = w; this.height = h; this.m = new int[w * h]; } public int get(int x, int y) { return this.m[y * width + x]; } public void set(int x, int y, int value) { this.m[y * width + x] = value; } public static void main (String[] args) { int w = 1000, h = 2000, passes = 400; int matrix[][] = new int[h][]; for (int i = 0; i < h; ++i) { matrix[i] = new int[w]; } long start; long duration; System.out.println("duration[ms]\tmethod"); start = System.currentTimeMillis(); for (int z = 0; z < passes; z++) { for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { matrix[y][x] = matrix[y][x] + 1; } } } duration = System.currentTimeMillis() - start; System.out.println(duration+"\t2D array, loop on x then y"); start = System.currentTimeMillis(); for (int z = 0; z < passes; z++) { for (int x = 0; x < w; x++) { for (int y = 0; y < h; y++) { matrix[y][x] = matrix[y][x] + 1; } } } duration = System.currentTimeMillis() - start; System.out.println(duration+"\t2D array, loop on y then x"); // ObjectArrayPerformance mt = new ObjectArrayPerformance(w, h); start = System.currentTimeMillis(); for (int z = 0; z < passes; z++) { for (int x = 0; x < w; x++) { for (int y = 0; y < h; y++) { mt.set(x, y, mt.get(x, y) + 1); } } } duration = System.currentTimeMillis() - start; System.out.println(duration+"\tmapped 1D array, access trough getter/setter"); // ObjectArrayPerformance mt2 = new ObjectArrayPerformance(w, h); start = System.currentTimeMillis(); for (int z = 0; z < passes; z++) { for (int x = 0; x < w; x++) { for (int y = 0; y < h; y++) { mt2.m[y * w + x] = mt2.m[y * w + x] + 1; } } } duration = System.currentTimeMillis() - start; System.out.println(duration+"\tmapped 1D array, access through computed indexes, loop y then x"); ObjectArrayPerformance mt3 = new ObjectArrayPerformance(w, h); start = System.currentTimeMillis(); for (int z = 0; z < passes; z++) { for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { mt3.m[y * w + x] = mt3.m[y * w + x] + 1; } } } duration = System.currentTimeMillis() - start; System.out.println(duration+"\tmapped 1D array, access through computed indexes, loop x then y"); ObjectArrayPerformance mt4 = new ObjectArrayPerformance(w, h); start = System.currentTimeMillis(); for (int z = 0; z < passes; z++) { for (int y = 0; y < h; y++) { int yIndex = y * w; for (int x = 0; x < w; x++) { mt4.m[yIndex + x] = mt4.m[yIndex + x] + 1; } } } duration = System.currentTimeMillis() - start; System.out.println(duration+"\tmapped 1D array, access through computed indexes, loop x then y, yIndex optimized"); } } 

我们可以得出结论，线性访问性能更多地取决于您处理数组的方式（行然后是列或反向？：性能增益= x10，很多是由于CPU缓存）而不是数组本身的结构（1D与2D：性能增益） = x2）。

如果是随机访问，性能差异应该低得多，因为CPU缓存效果较差。

Answer 6

实现多维数组的最有效方法是将一维数组用作多维数组。 请参阅有关将2Darrays映射到1Darrays的答案 。

 // 2D data structure as 1D array int[] array = new int[width * height]; // access the array array[x + y * width] = /*value*/; 

我当然可以使用映射到2D的一维数组，但我更喜欢更结构化的东西。

如果要以更结构化的方式访问array ，请为其创建一个类：

 public class ArrayInt { private final int[] array; private final int width, height; public ArrayInt(int width, int height) { array = new int[width * height]; this.width = width; this.height = height; } public int getWidth() { return width; } public int getHeight() { return height; } public int get(int x, int y) { return array[x + y * width]; } public void set(int x, int y, int value) { array[x + y * width] = value; } } 

如果你想要对象数组，你可以使用generics并定义类Array ，其中T是存储在数组中的对象。

在性能方面，在大多数情况下，这将比Java中的多维数组更快。 原因可以在这个问题的答案中找到。

Answer 7

如果你不能没有C构造，那么总是有JNI。

或者，您可以开发自己的Java派生语言（以及VM和优化JIT编译器），该语言具有多维连续内存数组的语法。