2012年8月22日 星期三

ArrayList 與 LinkedList 的效率比較 (未完待續)

網路上能夠獲得的資料大概都是說 ArrayList 擅長隨機讀取
而 LinkedList 擅長隨機插入和刪除資料~
不過目前根據我自己跑出來的測試結果,刪除我還沒測試
但插入尾端跟隨機插入,在我的測試當中都是 ArrayList 大勝......囧"
原因不明,不知道是不是我的測試方法有問題~

我的測試程式碼如下:
public void insertValuesToLinkedList () {
  System.out.println("LinkedList");
  LinkedList<Integer> list = new LinkedList<Integer>();
  Random ran = new Random();
  for(int i=0 ; i<this.count ; i++)
    list.add(i);
  int randomNumber = 0;
  
  long start = Calendar.getInstance().getTimeInMillis();
  for(int i=0 ; i<this.count ; i++) {
    randomNumber = ran.nextInt(list.size());
    randomNumber = (randomNumber > 0) ? randomNumber : randomNumber*-1;
    list.add(randomNumber, i);
    //System.out.println("Add "+ i);
  }
  long end = Calendar.getInstance().getTimeInMillis();
  
  System.out.println("Spent time for inserting: " + (end-start));
  System.out.println("List size: " + list.size());
}

public void insertValuesToArrayList () {
  System.out.println("ArrayList");
  ArrayList<Integer> list = new ArrayList<Integer>();
  Random ran = new Random();
  for(int i=0 ; i<this.count ; i++)
    list.add(i);
  int randomNumber = 0;
  
  long start = Calendar.getInstance().getTimeInMillis();
  for(int i=0 ; i<this.count ; i++) {
    randomNumber = ran.nextInt(list.size());
    randomNumber = (randomNumber > 0) ? randomNumber : randomNumber*-1;
    list.add(randomNumber, i);
    //System.out.println("Add "+ i);
  }
  long end = Calendar.getInstance().getTimeInMillis();
  
  System.out.println("Spent time for inserting: " + (end-start));
  System.out.println("List size: " + list.size());
}

兩個函式都是先在 List 裡面插入 N 筆資料(N 即程式碼中的 this.count)
接著開始計時,隨機再插入 N 筆資料,看看需要花多少時間。
測試結果如下(在我的測試中,N = 100000):
ArrayList
Spent time for inserting: 5225 ms
List size: 200000

LinkedList
Spent time for inserting: 51107 ms
List size: 200000

目前還沒研究出為什麼測出來的結果跟網路上的資料都不同....
所以待續~還需要再想看看有沒有其他因素造成這個結果。

補充:
[3] 裡面討論了類似的問題,回應中有人的回答是說因為該篇原 po 在宣告時指定了 ArrayList 的長度
所以插入時 ArrayList 等於是先偷跑了~
不過在我的測試程式碼中,我沒有宣告 ArrayList 的初始長度,理論上應該就不存在這個問題,但結果仍然是 ArrayList 樂勝....。
但雖然如此,[3] 還是有一些值得看一下的討論內容~

[4] 是一樣在討論 ArrayList 和 LinkedList 的問題,但不是在討論效率,而是在討論互相置換的問題
這也是值得研究和思考的問題,但老實說以我目前的程度,回應中的討論有些地方我看不太懂....XD

[5] 是討論如何測量使用的記憶體的問題,這篇我還沒仔細看回應,不過這也是我在做上面的測試時有在想的問題。

參考資料:
1、ArrayList 與 LinkedList 的差異
2、Performance differences between ArrayList and LinkedList
3、ArrayList与LinkedList的效率比较
4、一道面试题 ArrayList和LinkedList
5、[問題] 如何測量出LinkList / ArrayList 的記憶體使用量

1 則留言:

Unknown 提到...

因為時間還包括LinkedList找到插入點的時間