Geek Answers Handbook

Efficient implementation of multidimensional arrays in Java?

As far as I understand (from answers like this ), java does not have built-in multidimensional contiguous arrays of memory ( unlike C #, for example ).

While the syntax of an uneven array (arrays of arrays) can be useful for most applications, I would still like to know what is the best practice if you want to get the raw efficiency of a continuous memory array (avoiding unnecessary memory reads)

I could, of course, use a one-dimensional array that maps to 2D, but I prefer something more structured.

+5
source share
7 answers

this is not difficult to do manually:

int[] matrix = new int[ROWS * COLS];

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

now, is it really faster than a java multi dimension array?

int x_i_j = matrix[i][j];

for random access maybe. for continuous access, probably not - matrix[i]almost certainly in the L1 cache, if not in the register cache. at best, matrix[i][j]one addition and one read in memory is required; while it matrix[i*COLS + j]may cost 2 additions, one multiply, one read. but who counts?

+5
source

It depends on your access pattern. Using this simple program , comparing int[][]with a two-dimensional mapping over a 1D array int[], viewed as a matrix, the built-in Java Java matrix is:

  • 25% , , : :
  • 100% , , : :

// 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];
}
+4

, .

public class My2dArray<T> {

  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 , . , .

JVM , , ; , JVM , JVM . , , ( " " ).

+3

, . , C/++ . , .. , imho. , , , JIT .

class MultiDimentionalArray<T> {
//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];
    }
}
+1

. . 2D- 1D-.

// 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>, T - , .

, , Java. .

0

, 2D- int[][] a = new int[height][width], a[y][x]. , , 20 :

2D array access comparison

:

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, - ), (1D vs 2D: = x2).

, , .

0

C-, JNI.

Java- ( VM JIT-), .

-1

More articles:


All Articles