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需要多少时间？

回答

相关问题