而 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 則留言:
因為時間還包括LinkedList找到插入點的時間
張貼留言