CODEWITHSUNDEEP
javaarraysperformancelistmemory
Jon
Jon

Reputation: 25

Array of objects vs list+array of indices

Say you have 10 indexed references within an object (#0 thru 9). However, 2 of them are unused in a particular instance of our class (say, #3 and #8). Here's my question: Memory and performance-wise, what would be the best option: an array of references of length 10, with null values at indices 3 and 8, or an list of size 8 coupled with an int array pointing to the indices of references in that list?

Solution 1 would look something like this:

class SomeObject{
    OtherObject[] references = new OtherObject[10];
    {
        for(int i = 0; i<10; i++){
            if(i != 3 && i != 8)
                references[0] = new OtherObject();
            //otherwise just keep the null value
        }
    }

    //then to use (here getting the toString() value)
    String getStringOfObjectAtIndex(int index){
        //in real code we'd first check that index is within 0-9
        if(references[index] != null)
            return references[index].toString();
        else
            return "";//no reference for that index
    }
}

Whilst solution 2 would be more like so:

class SomeObject{
    ArrayList<OtherObject> references = new ArrayList<>(0);
    int[] pointers = new int[10];
    {
        for(int i = 0; i<10; i++){
            if(i != 3 && i != 8){
                pointers[i] = references.size();
                references.add(new OtherObject());
            }else{
                pointers[i] = -1;//no reference available
            }
        }
    }

    //then to use (here getting the toString() value)
    String getStringOfObjectAtIndex(int index){
        //in real code we'd first check that index is within 0-9
        if(pointers[index] != -1)
            return references.get(pointers[index]).toString();
        else
            return "";//no reference for that index
    }
}

tl;dr: is a null reference inside an array larger than an int?

Upvotes: 0

Views: 58

Answers (1)

JB Nizet
JB Nizet

Reputation: 692191

In the first case, assuming a reference costs 64 bits, you need 128 bits to store the two null references, and the code is easy to understand and maintain.

In the second case, you need an additional array of 10 ints (that means 10 * 32 bits, plus at least 16 bytes for the array itself), and the code is convoluted. Not to mention that the ArrayList itself has additional overhead compared to the array, and will anyway contain an array that is larger than 8 to hold the elements.

Anyway, this looks a lot like premature optimization, which is the root of all evil. Use the simplest, most obvious, most readable and maintainable solution. It has a good chance to be fast enough, and even has chance to be the fastest and the lowest on memory.

An alternate strategy might be useful if you have a very large, and very sparse array. But in that case, using a Map<Integer, OtherObject> would be simpler.

Upvotes: 1

Related Questions