Using 2D arrays to make more efficient sequential storage

This code is part of a growing "primitive" tools collection here on github

Use Case

Consider:

IntArray ia = new IntArray();
ia.set(300, 5);
System.out.printf("Values at 10, 300, and 3000 are: %d %d and %d\n",
        ia.get(10), ia.get(300), ia.get(3000));

This gives:

Values at 10, 300, and 3000 are: 0 5 and 0

Primary concerns are:

• correctness for all use cases

• efficiency in memory

• performance

Additionally, I am interested in use-cases or usability factors that are of concern, or should be added.

Background

Arrays are a very convenient system for storing data based on a simple index. Their constraints though (in Java), are that:

• They are limited in size (to 231 - 1 members)

• once initialized, they cannot be expanded, only replaced. Replacing an array requires having both the old, and new array in memory at once, and all the data needs to be copied from the old to new location.

• they require consecutive spans of memory to be stored in.

Many of these constraints can be avoided or reduced if you store array data in a 2-dimensional structure. Each 'row' is a portion of the overall span. If each row has the same, fixed size, then the translation from the logical linear system, the matrix system, is:

• row -> index / rowsize

• col -> index % rowsize

Similarly, the translation from a row/column position to the logical index, is:

• index -> row * rowsize + col

If you choose a fixed row size that is also a power of 2, then you can accomplish the same with bitwise operations. A row size of 256 elements, is implemented as:

• row -> index >>> 8

• col -> index & 255

similarly:

• index -> (row




The following is a collection of static methods designed to help manage a system where you create a matrix to represent a logical single-dimensional array as a matrix instead. In addition, an implementation of a primitive int` array that allows some structured and dynamic access to the data in the array.

ArrayOps

Tools for

Naming

Okay this one is so easy that I just have to point it out.

private int hwm = -1; // high water mark

What have we said about shortening variable names like that only to add a comment about what the abbreviation means afterward?

private int highWaterMark = -1;

Right. That is what we have said.

But what is a high water mark really? I don't see your class having anything to do with measuring the height of water in a river.

Suggestion: Either name it highestAccessedIndex or add javadoc to it, explaining what you mean by "high water mark".

Copy

IntArray a = new IntArray();
Random random = new Random();
for (int i = 0; i < 1000; i++) {
    a.set(random.nextInt(1000), random.nextInt(1000));
}
a.set(420, 42);
a.set(41, 73);
a.set(41, 73);
// How do I copy this thing!?

Please provide a copy-constructor!

To be or not to be equal ?

Consider this code:

IntArray a = new IntArray();
IntArray b = new IntArray();

a.set(42, 10);
b.set(42, 10);
System.out.println(a.equals(b)); // Prints true
System.out.println(a.get(4000)); // Prints 0
System.out.println(a.equals(b)); // Prints false

It is a bit weird that calling a get method modifies the result of a.equals(b).

This is definitely not something I would expect. Additionally, the JavaDoc for get does not inform about this.

I think that the "high water mark" should not be considered in equals.

Luckily, you are not breaking the hashCode and equals contract here. Your hashCode method does not consider hwm. Did the hwm accidentally sneak into the equals method?

Usability

This is probably the worst news.

Your class seem to be really useful. However... as you are using java.util.streams there are certain platforms where this class is unusable so far. Such as GWT and Android

GWT support for Java 8 will be added in GWT 2.8, but Java 8 and Android does not go well together. Although there is a retrolambda gradle plugin, that does not support the Java 8 Stream API.

If you want to support more than Java 8, that is up to you.

How do I...?

The class is called IntArray (although it is resizable), but there are some features I'm not sure how to use that are available on other arrays / list classes..

• Add a value at the end of the array, such as array.add(42)

• Check if the array contains a value, array.contains(42)

• Remove a value from the array, array.remove(42)

• Add all values from an int[], array.addAll(new int[]{ 1, 2, 3, 4 })

• Check the size of the array, array.size()

Also, what is the index position of your array good for? There is no way to check which indexes has a value and which does not have a value. The concept reminds me of SparseIntArray in Android which is similar to Map, but with the limitation that your class does not provide a way to remove values, and does not allow negative key indexes.

Speed comparison

Using a particular benchmarking library, I found that your class performs well when compared to IntArray from LibGDX

Although your two classes provides quite different ways of doing things, the IntArray from LibGDX provides all the add, contains, remove methods, etc. but does not behave well when using sparse indexes.

public class SpeedTest {

    private static final int SIZE = 1000000;

    @Test
    public void test() {
        UBench bench = new UBench("Speed");
        bench.addIntTask("Rolfl", () -> rolfl(), i -> i == SIZE);
        bench.addIntTask("Libgdx", () -> gdx(), i -> i == SIZE);
        bench.report("Result", bench.press(1000));
    }

    private int gdx() {
        IntArray array = new IntArray();
        for (int i = 0; i < SIZE; i++) {
            array.add(i);
        }
        return SIZE;
    }

    private int rolfl() {
        net.tuis.primutils.IntArray array = new net.tuis.primutils.IntArray();
        for (int i = 0; i < SIZE; i++) {
            array.set(i, i);
        }
        return SIZE;
    }

}

Results:

Task Speed -> Rolfl: (Unit: MILLISECONDS)
  Count    :     1000      Average  :   3.4577
  Fastest  :   2.9710      Slowest  :  19.9286
  95Pctile :   4.6342      99Pctile :   5.6237
  TimeBlock : 4.153 3.642 3.421 3.742 3.237 3.238 3.262 3.279 3.308 3.297
  Histogram :   992     7     1

Task Speed -> Libgdx: (Unit: MILLISECONDS)
  Count    :     1000      Average  :   5.0694
  Fastest  :   4.0500      Slowest  :  14.9409
  95Pctile :   7.6653      99Pctile :   8.9765
  TimeBlock : 6.373 5.877 4.951 5.576 4.662 4.634 4.642 4.632 4.648 4.699
  Histogram :   968    32

StackExchange Code Review Q#82954, answer score: 7