TreeMap需要多少時間？

-1

我正在使用TreeMap，其中的鍵爲String，值爲Custom對象的List。事情是這樣的：在一個TreeMapTreeMap需要多少時間？

Map<String, List<CustomObject>> map = new TreeMap<String, List<CustomObject>>();

我知道，插入和獲取操作有O（log n）的時間複雜度。但是，我並不完全知道如何推測將會處理一個TreeMap所花費的時間，

有人可以幫我一個你想用查不到

時間採取的辦法把大約40,000記錄到TreeMap（考慮所有的字符串是隨機的和唯一的）。即，繼線40000次：
```
map.put("SomeString", listOfCustomObjects) 
```

時間採取了鍵集合一次迭代包括調用get()方法：

for(String s: map.keySet()){ 
    List<CustomObject> listOfCustomObjects =map.get(s); 
    //do something with the list 
}

來源

2017-05-26 Aman

您可以使用Google的Guava秒錶庫和一個循環增加記錄40,000次來測試這一點。或者你甚至可以比較循環之前和之後的System.currentTimeMillis（）。 –

樹形圖根據其按鍵的自然排序進行排序。爲什麼不在插入和檢索循環前後放置'System.currentTimeMillis（）'或納秒。 – Shriram

測試和測量。任何人都不可能在你的硬件和配置上爲你做這件事。 – EJP

編寫測試和測量時間。如果沒有實際的執行，沒有可靠的方法來估計執行時間。

確保基準密鑰分配與實際密鑰分配匹配，因爲平衡算法可能嚴重影響執行時間。

來源

2017-05-26 07:37:17 Dariusz

這很難估計。這裏是一個小測試：

System.out.println("put\titeration"); 
for (int r = 0; r < 10; ++r) { 
    Map<String, List<Object>> map = new TreeMap<>(); 
    List<Object> dummyList = new ArrayList<>(); 

    long start, end, putTime, iterTime; 
    start = System.currentTimeMillis(); 
    for (int i = 0; i < 1_000_000; ++i) { 
     map.put(String.valueOf(), dummyList); 
    } 
    end = System.currentTimeMillis(); 
    putTime = (end - start); 

    start = System.currentTimeMillis(); 
    for(String s: map.keySet()){ 
     List<Object> listOfCustomObjects = map.get(s); 
    } 
    end = System.currentTimeMillis(); 
    iterTime = (end - start); 
    System.out.println(putTime + "ms\t" + iterTime + "ms"); 
}

此測試添加1.000.000條目到TreeMap。這重複了十次。

爲什麼我使用1.000.000而不是40.000？ 40.000是很少的東西。我的結果是大約40毫秒到70毫秒。更多條目導致結果之間的差異更大：

put  iteration 
1224ms 211ms 
626ms 198ms 
769ms 199ms 
577ms 193ms 
1179ms 194ms 
438ms 190ms 
445ms 201ms 
309ms 200ms 
378ms 198ms 
396ms 205ms

我使用了2.40 GHz的CPU。

所以大部分時間需要〜400ms，但有些時候需要兩到三倍的時間。這是由於及時優化，內存管理或僅僅因爲OS進程調度。如何知道...

來源

2017-05-26 08:16:14 Obenland

微指點是棘手和困難的。使用JMH，但首先閱讀文檔和一些教程，例如this one。

因此，對於1），只需使用JMH並查看需要多長時間。

關於2），請執行相同的操作：設計一個microbenchmark並查看需要多長時間。然而，有一個更有效的方式來遍歷圖，這是使用Map.entrySet方法的條目：

for (Entry<String>, List<CustomObjects>> e : map.entrySet()) { 
    String key = e.getKey(); 
    List<CustomObjects> value = e.getValue(); 
    // do something with the list 
}

這種方式是更好，因爲在一個TreeMap，get有O(log n)時間複雜度，因此調用getn時間將是O(n log n)，而使用entrySet方法是恆定的（entrySet返回一個集合是地圖條目的視圖），並且您已在每個條目中具有該值。

來源

2017-05-26 23:00:58

TreeMap需要多少時間？

回答

相關問題