Storing & lookup double array

Question

Hi,

I have a fairly expensive array calculation (SpectralResponse) which I like to keep to a minimum. I figured the best way is to store them and bring it back up when same array is needed again in the future. The decision is made using BasicParameters.

So right now, I use a LinkedList of object for the arrays of SpectralResponse, and another LinkedList for the BasicParameter. And the BasicParameters has a isParamsEqualTo(BasicParameters) method to compare the parameter set.

LinkedList<SpectralResponse> responses
LinkedList<BasicParameters> fitParams
LinkedList<Integer> responseNumbers

So to look up, I just go through the list of BasicParameters, check for match, if matched, return the SpectralResponse. If no match, then calculate the SpectralResponse.

Here's is the for loop I used to lookup.

size: LinkedList size, limited to a reasonable value
responseNumber: just another variable to distinguish the SpectralResponse.

    for ( i = size-1; i > 0 ; i--) {
        if (responseNumbers.get(i) == responseNum)
        {
            tempFit = fitParams.get(i);
            if (tempFit.isParamsEqualTo(fit))
            {
                return responses.get(i);
            }
        }
    }

But somehow, doing it this way no only take out lots of memory, it's actually slower than just calculating SpectralResponse straight. Much slower.

So it is my implementation that's wrong, or I was mistaken that precalculating and lookup is faster?

Answer 1

Hi,

You are accessing a LinkedList by index, this is the worst possible way to access it ;)

You should use ArrayList instead, or use iterators for all your lists.

Possibly you should merge the three objects into one, and keep them in a map with responseNum as key.

Hope this helps!

Answer 2

You probably should use an array type (an actual array, like Vector, ArrayList), not Linked lists. Linked lists is best for stack or queue operation, not indexing (since you have to traverse it from one end). Vector is a auto resizing array, wich has less overhead in accessing inexes.

Answer 3

The get(i) methods of LinkedList require that to fetch each item it has to go further and further along the list. Consider using an ArrayList, the iterator() method, or just an array.

Answer 4

The second line, 'if (responseNumbers.get(i) == responseNum)' will also be inefficient as the responseNumbers.get(i) is an Integer, and has to be unboxed to an int (Java 5 onwards does this automatically; your code would not compile on Java 1.4 or earlier if responseNum is declared as an an int). See this for more information on boxing.

To remove this unboxing overhead, use an IntList from the apache primitives library. This library contains collections that store the underlying objects (ints in your case) as a primitive array (e.g. int[]) instead of an Object array. This means no boxing is required as the IntList's methods return primitive types, not Integers.