5

有没有办法通过指定项目的顺序来优化 java.util.Collection 中的插入速度?

例如

java.util.Set<String> set = java.util.TreeSet<String>();

将这个解决方案:

set.add("A");
set.add("B");
set.add("C");
set.add("D");
set.add("E");

比这个更快(随机顺序)?

set.add("E");
set.add("D");
set.add("C");
set.add("A");
set.add("B");

(以及其他集合的相同问题:HashMap,hastable ...)

谢谢

4

5 回答 5

8

简单的答案是“时间看看”。

另一个答案是“没关系”。这似乎是一个微优化,几乎不值得付出努力。我认为它属于“微优化剧院的悲惨悲剧”的范畴。

于 2009-02-22T18:11:33.520 回答
6

java.util.Map 和 java.util.Set 不行,因为它们是接口,有不同的实现。

对于具体的实现,这不是值得的优化。如果您在性能方面遇到问题,请选择更合适的实现,或者重新考虑您需要存储什么以及如何存储。

在一台普通的笔记本电脑上,将 5000 个随机数插入 HashSet 大约需要一毫秒,那么您要插入多少百万个元素才能使这种优化变得有价值?

于 2009-02-22T18:15:37.440 回答
3

红黑树(用于实现 Java 的TreeSet/TreeMap )的插入时间保证最坏情况为 O(log n)。如果项目按特定顺序排列可能会更快,但我不确定那会是什么(可能预排序最快?)。

插入哈希表是 O(1)(恒定时间)操作。插入的主要工作是计算hashcode


编辑:Starblue 建议预排序可能会产生最差的性能,因此您可以尝试随机排序。

于 2009-02-22T18:11:16.437 回答
2

基于散列的集合和基于树的集合之间自然存在巨大差异。

基于树的对象受益于插入的元素排序(例如,字符串之间的比较),因此当您有可比较的对象(如字符串)时,最好使用它们。TreeSet/TreeMap/等。在标准集合中应该是平衡的(红黑树),所以插入顺序并不重要。如果它不平衡,那么插入顺序就会很重要,因为您最终可能会得到一个链而不是树。

在哈希表中,加载因子和哈希函数决定了一切,但如果您正在处理字符串,您可能甚至不打扰哈希会更好。

如果您需要一组字符串来处理许多重叠的字符串,Trie 可能会更节省内存,但我认为库中没有。

于 2009-02-22T18:14:03.157 回答
1

在采取优化措施时要小心考虑数据结构的特征。举一个极端的例子,将元素按排序顺序插入二叉树会产生一个链表。

于 2009-02-22T18:53:14.310 回答