初始化大型整数列表最快的方法是什么？

Question

我需要用大量的整数值预先填充列表。

除了迭代，还有更快的方法吗？

当前代码：

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

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

此代码位于一个非常频繁创建的类的构造函数中，因此我希望它尽可能高效（read：性能而不是代码行）

Answer 1

我知道这个问题已经得到了回答。但是我认为缺少一个重要的答案：用值0...4093初始化LinkedList的最快方法是...根本不要这样做。尤其是当速度是个问题的时候。

基本上，您正在创建一个由4093＜code＞节点节点都必须创建（并且是自由的）。此外，必须创建（并释放）几乎每个包含的整数“几乎”因为Java使用整数缓存，但通常（您可以使用系统属性更改）在-127到127之间。

为了得到一个简单的整数列表，这需要做很多工作，如果大量使用，会给GC带来很多工作要做。

也就是说，有许多可能的方法可以更有效地做到这一点。但它们取决于您的具体使用模式。仅举几个例子：

1. 使用一个数组：＜code＞boolean〔〕inUse‘，并将获取的vlan id设置为更好的方法是使用位集而不是数组。
2. 不存储哪个vlan是空闲的，而是存储哪个vlan被占用。我认为他们往往是自由的，所以有更多的自由，因为有更多的人。（这意味着更不需要跟踪）
3. 如果您坚持使用LinkedList，请不要使用类初始化它，而是将其初始化。这取决于你需要多少。你可以保留一个游泳池。或者您的代码允许重用旧列表。（是的，您可以在使用后对它们进行排序。）

当然还有更多...

所有这些方法都需要您构建自己的“队列”接口。但也许这没有Java的丰富。这真的没有那么难。如果你真的大量使用它，你可以达到10-1000倍的性能提升系数。

使用 BitSet 的可能实现，实例化成本几乎为零，可能是：

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 );
    }

}

Answer 2

最快的方法是创建一个引用列表（使用实例块初始化-将其整齐地包装在一个语句中）：

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

然后在构造函数中，使用复制构造函数初始化队列:

Queue<Integer> queue;

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

您不会编写比JDK中更快的实现。

Answer 3

4094不是要循环的很多项目，但是如果它被非常频繁地调用，您可能会考虑使用静态变量做一些事情。

private static Integer[] theList;

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

然后使该列表成为< code >列表

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

如果你有一个可变对象的列表，使用这个方法是有危险的。这里有一个可能发生的例子。整数是不可变的，所以这实际上不适用于你的问题

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在使用静态列表而不是数组方面有一些优点，虽然性能提升很小，但性能提升仍然很大。还因为“array”实际上只作为< code>List而不是数组使用，所以应该声明为数组。

private static List<Integer> theList;

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