2014-07-19 118 views
0

我需要預先填充大量整數值的列表。初始化大整數列表的最快方法是什麼?

是否有更快的方式來做到這一點,而不是迭代?

目前代碼:

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

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

此代碼是在創建相當頻繁類的構造函數,所以我想這是因爲有效的(閱讀:性能不是行代碼)儘可能

+0

我不認爲有任何其他方式 –

+1

你可以嘗試創建一個即時陣列和使用asList,但我d在您需要的實際環境下進行配置。我會編程生成數組代碼,除非你真的喜歡打字。 –

+9

4094?別擔心,你會沒事的...... –

回答

4

4094對許多項目來說並不是循環的,但如果它被非常頻繁地調用,你可能會考慮用靜態變量來做一些事情。

private static Integer[] theList; 

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

然後使該列表中的List

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對使用數組的靜態列表,而不是一些好點,而性能提升是非常小的,他們性能收益就不會那麼好。另外,因爲'數組'實際上只被用作List而不是數組,所以它應該被聲明爲這樣。

private static List<Integer> theList; 

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

這就是我正要做的事情。 – ChiefTwoPencils

+0

這比我肯定的要好!但是我需要一個可變對象,所以我認爲這不適合我的用例。 –

+0

@DaveTucker所以你不使用整數? –

3

最快的方法是創建一個參考列表(使用實例塊初始化 - 整齊地包裹這一切在一個聲明中):

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中更快的實現。

+0

這裏一個很好的優點是避免每次創建對象時將所有4094值的'int'更改爲'Integer'。 –

+0

這與@ug_給出的答案基本相同,只是將簡單靜態塊更改爲雙大括號。我沒有真正的印象。 – Boann

+0

@Boann居然沒有。這兩個答案有一些相似之處,但最大的區別在於隊列初始化(問題的主題):另一個答案需要一個數組,創建(並初始化)一個List,然後使用該List來初始化隊列。我的答案跳過了中間對象並直接進入JDK的(快速)列表拷貝構造函數。另一個重要的區別是我的引用列表包含Integer對象,它們不需要轉換,但另一個回答是初始化他的引用列表,其中的inf基元必須每次都包裝爲整數。 – Bohemian

1

我意識到這個問題已經被回答了。但我認爲缺少一個重要的答案:初始化值爲0..4093的LinkedList的最快方法是...... 請勿全部在處執行此操作。特別是如果速度是一個問題。

你基本上正在做的是創建一個由4093 Node元素組成的結構,每個元素包含兩個指向prev/next元素的指針和一個指向Integer對象的指針。每個Node都必須創建(並免費)。另外幾乎每個包含Integer的都必須創建(並釋放)。 '接近',因爲Java使用Integer緩存,但通常情況下(可以通過系統屬性更改)在-127..127的範圍內。

爲了得到一個簡單的整數列表,這要做很多事情,並且如果使用密集型方法給GC之後要做很多事情。

這就是說有很多可能的方式以更有效的方式做到這一點。但它們取決於具體的使用模式。僅舉幾例:

  1. 使用數組:如果它採取boolean [] inUse' and set the taken vlan-id to TRUE`
  2. 更妙的是使用位集合,而不是陣列
  3. 不要存放哪個VLAN是免費的,但其VLAN是拍攝。我認爲他們傾向於自由,所以有更多的自由,因爲有人採取。 (這意味着要跟蹤更少)。
  4. 如果您堅持使用LinkedList,請不要使用您的類對它進行初始化,而是讓它已經初始化。這取決於你需要多少人。你可以保持一池。或者你的代碼允許重新使用舊列表。 (是的,你可以在使用後對它們進行排序。)

當然還有更多...

所有這些方法都需要你建立自己的「隊列」界面。但也許這並不像Java那樣豐富。而且它確實不那麼困難。如果你真的使用這個密集型,你可以達到性能改善因子10x-1000x ++。

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

} 
+0

我同意你關於Node對象的觀點,但最簡單的解決方案是使用'ArrayDeque'代替'LinkedList'。 – Boann

+0

無可否認'ArrayDeque'會避免創建節點。但它仍然使用一個支持long [4094]的數組(可以一次分配)和大約4000個新創建(和免費)整數對象。但是我們所需要的全部是4094位(如果有的話)(這可以通過增加Javas integer緩存或保留自己的緩存來改善),但最重要的是缺少一個ArrayDeque(Object [])構造函數,它至少可以使用System .arrayCopy或其他東西來加快速度。 – Scheintod

相關問題