What's the fastest way to initialize a large list of integers?

Question

I need to pre-populate a List with a large number of integer values.

Is there are faster way to do this other than iteration?

Current Code:

class VlanManager {
    Queue<Integer> queue = Lists.newLinkedList();

    public VlanManager(){
    for (int i = 1; i < 4094; i++) {
        queue.add(i);
    }
}

This code is in the constructor of a class that is created pretty frequently so I'd like this to be as efficient (read:performance not lines of code) as possible

Answer 1

4094 isnt to many items to loop but if it is getting called very frequently you might look at doing something with a static variable.

private static Integer[] theList;

static {
    theList = new Integer[4094];
    for (int i = 1; i < 4094; i++) {
        theList[i-1] = i;
    }
}

then make that list a List

Queue<Integer> intQue = new LinkedList(Arrays.asList(theList));

---

There is a danger of using this method if you have a list of mutable objects. Heres an example of what can happen. Integers are immutable so this doesnt actually apply to your question as it stands

class MyMutableObject {
    public int theValue;
}

class Test {

    private static MyMutableObject[] theList;

    static {
        theList = new MyMutableObject[4094];
        for (int i = 1; i <= 4094; i++) {
            theList[i-1] = new MyMutableObject();
            theList[i-1].theValue = i;
        }
    }

    public static void main(String [] args) {
        Queue<MyMutableObject> que = new LinkedList(Arrays.asList(theList));
        System.out.println(que.peek().theValue); // 1
        // your actually modifing the same object as the one in your static list
        que.peek().theValue = -100; 
        Queue<MyMutableObject> que2 = new LinkedList(Arrays.asList(theList));
        System.out.println(que2.peek().theValue); // -100
    }
}

---

@Bohemian Has some good points on using a static List instead of an array, while the performance gains are very small they are none the less performance gains. Also because the 'array' is actually only ever being used as a List not an array it should be declared as such.

private static List<Integer> theList;

static {
    theList = new ArrayList(4094);
    for (Integer i = 0; i < 4094; i++) {
        theList.add(i+1);
    }
}

Answer 2

The fastest way would be to create a reference list (initialized using an instance block - neatly wrapping it all up in one statement):

private static final List<Integer> LIST = new ArrayList<Integer>(4094) {{
    for (int i = 1; i < 4094; i++)
       LIST.add(i);
}};

Then in your constructor, initialize the queue using the copy constructor:

Queue<Integer> queue;

public VlanManager(){
    queue = new LinkedList<Integer>(LIST);
}

You will not write a faster implementation than what's in the JDK.

Answer 3

I realize this question has already been answered. But I think one important answer is missing: The fastest way to initialize a LinkedList with the values 0..4093 is .. DON'T DO IT AT ALL. Especially if speed is an issue.

What you basically are doing is creating a structure consisting of 4093 Node elements each consiting of two pointers to prev/next element and one pointer to an Integer object. Each of this Nodes must be created (and free). In addition nearly each contained Integer must be created (and freed). 'Nearly' because Java uses a cache for Integer but normally (you can change this with system properties) in the range of -127..127.

This is a lot to do in order to get a simple list of integer and if used intensively gives the GC a lot to do afterwards.

That being said there are numerous possible ways of doing this in a more efficient way. But they depend on what your concrete usage pattern is. Just to name a few:

1. Use an Array: boolean [] inUse' and set the taken vlan-id totrue` if it's taken
2. Even better use a BitSet instead of the array
3. Don't store which vlan is free, but which vlan is taken. I think they tend to be free and so there are much more free as there are taken ones. (this means much less to keep track of).
4. If you insist on using a LinkedList don't initialize it with your class but have it already initialized. This depends on how much of them you would need. You could keep a pool of them. Or perhaps your codes allows reusage of old lists. (yes, you could sort them after usage.)

Surely there are more...

All of this methods require you to build your own 'Queue' interface. But perhaps this has not to be as rich as Java's. And it really isn't that difficult. If you really use this intensively you could reach perfomance improvement factor 10x-1000x++.

A possible implementation using BitSet with an instantiation cost of nearly nothing could be:

import java.util.BitSet;

import org.testng.annotations.Test;


public class BitSetQueue {

    // Represents the values 0..size-1
    private final BitSet bitset;
    private final int size;
    private int current = 0;
    private int taken = 0;

    public BitSetQueue( int size ){

        this.bitset = new BitSet( size );
        this.size = size;
        this.current = size-1;
    }

    public int poll(){

        // prevent endless loop
        if( taken == size ) return -1;

        // seek for next free value.
        // can be changed according to policy
        while( true ){

            current = (current+1)%size;

            if( ! bitset.get( current ) ){
                bitset.set( current );
                taken++;
                return current;
            }
        }
    }

    public boolean free( int num ){

        if( bitset.get( num ) ){
            bitset.clear( num );
            taken--;
            return true;
        }
        return false;
    }


    @Test
    public static void usage(){

        BitSetQueue q = new BitSetQueue( 4094 );

        for( int i = 0; i < 4094; i++ ){
            assertEquals( q.poll(), i );
        }
        assertEquals( q.poll(), -1 ); // No more available

        assertTrue( q.free( 20 ) );
        assertTrue( q.free( 51 ) );

        assertEquals( q.poll(), 20 );
        assertEquals( q.poll(), 51 );
    }

}