什么是最有效的Java Collections库？
几年前,我做了很多的Java和有印象背那么宝库是最好的(最有效的)Java集合实现.但是,当我读了回答这个问题:" 最有用的免费Java库？ "我注意到宝库是几乎没有提及.那么哪个Java Collections库现在最好？
更新:为了澄清,我主要想知道当我必须在哈希表等中存储数百万个条目时要使用的库(需要小的运行时和内存占用).
问题是(现在)关于存储大量数据,这些数据可以使用原始类型(如intMap)来表示.在我看来,这里的一些答案非常具有误导性.让我们看看为什么.
我从trove修改了基准来测量运行时和内存消耗.我还将PCJ添加到此基准测试中,这是基本类型的另一个集合库(我广泛使用它)."官方"宝库基准测试不会将IntIntMaps与Java Collection进行比较Map,从技术角度来看,存储Integers和存储可能ints并不相同.但是用户可能不关心这个技术细节,他希望有效地存储可表示的数据ints.
首先是代码的相关部分:
new Operation() {
private long usedMem() {
System.gc();
return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}
// trove
public void ours() {
long mem = usedMem();
TIntIntHashMap ours = new TIntIntHashMap(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
ours.put(i, i);
}
mem = usedMem() - mem;
System.err.println("trove " + mem + " bytes");
ours.clear();
}
public void pcj() {
long mem = usedMem();
IntKeyIntMap map = new IntKeyIntOpenHashMap(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
map.put(i, i);
}
mem = usedMem() - mem;
System.err.println("pcj " + mem + " bytes");
map.clear();
}
// java collections
public void theirs() {
long mem = usedMem();
Map map = new HashMap(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
map.put(i, i);
}
mem = usedMem() - mem;
System.err.println("java " + mem + " bytes");
map.clear();
}
我假设数据是原始的ints,这似乎是理智的.但这意味着java util的运行时损失,因为自动装箱,这对于原始集合框架来说不是必需的.
gc()WinXP,jdk1.6.0_10上的运行时结果(当然没有调用):
100000 put operations 100000 contains operations
java collections 1938 ms 203 ms
trove 234 ms 125 ms
pcj 516 ms 94 ms
虽然这可能看起来很激烈,但这并不是使用这种框架的原因.
原因是内存性能.包含100000 int个条目的Map的结果:
java collections oscillates between 6644536 and 7168840 bytes trove 1853296 bytes pcj 1866112 bytes
与原始集合框架相比,Java集合需要的内存是内存的三倍以上.也就是说,您可以在内存中保留三倍的数据,而无需借助磁盘IO,这会降低运行时性能的大小.这很重要.阅读高度可读性以找出原因.
根据我的经验,高内存消耗是Java最大的性能问题,这当然也会导致运行时性能下降.原始集合框架在这里可以提供帮助.
所以:不,java.util不是答案.在询问效率时,"添加功能"到Java集合并不是重点.现代JDK系列也不会 "超越专业的Trove系列".
免责声明:这里的基准测试远非完整,也不完美.它旨在将我在许多项目中经历过的观点带回家.如果您处理大量数据,原始集合足以容忍可疑API .
从检查来看,看起来Trove只是一个原始类型的集合库 - 它并不像是要在JDK中添加大量功能而不是普通集合.
个人(我有偏见)我喜欢Guava(包括以前的Google Java Collections项目).它使各种任务(包括集合)变得更加容易,其方式至少相当有效.鉴于集合操作很少在我的代码中形成瓶颈(根据我的经验),这比集合API"更好",集合API可能更有效但不会使我的代码可读.
鉴于Trove和Guava之间的重叠几乎为零,或许您可以从集合库中澄清您实际需要的内容.
我知道这是一个老帖子,这里有很多答案.但是,在建议图书馆方面,上面的答案是肤浅的,而且过于简化.没有一个图书馆在这里提供的各种基准测试中表现良好.我得出的唯一结论是,如果你关心性能和内存,特别是处理原始类型,那么它非常值得关注非jdk替代方案.
在基准力学和涵盖的库方面,这是一个更健全的分析. 这是mahout开发列表中的一个主题.
涵盖的图书馆是
HPPC
特罗韦
FastUtil
Mahout(柯尔特)
Java集合
2015年6月更新:不幸的是,原来的基准测试已经不再可用,而且有点过时了. 这是一个由其他人完成的最新(2015年1月)基准测试.它不是那么全面,也没有原始链接的交互式探索工具.
正如其他评论家所注意到的那样,"高效"的定义投入了广泛的网络.但是还没有人提到Javolution库.
一些亮点:
Javolution类快速,非常快(例如,在O [Log(n)]中插入/删除文本而不是标准StringBuffer/StringBuilder的O [n]).
所有Javolution类都是硬实时兼容的,并且具有高度确定性的行为(在微秒范围内).此外(与标准库不同),Javolution是RTSJ安全的(与Java Real-Time扩展一起使用时没有内存冲突或内存泄漏).
Javolution的实时集合类(map,list,table和set)可用于代替大多数标准集合类,并提供其他功能.
Javolution集合提供并发保证,使并行算法的实现更容易.
Javolution发行版包含一个基准测试套件,因此您可以看到它们如何与其他库/内置集合进行叠加.
一些集合库要考虑:
java.util中的Java集合
特罗韦
Google Collections库
Apache Commons Collections
来自Cliff Click的高规模lib
Doug Lea的集合库 - 不再受支持,大部分都是在JDK中重建的
我首先要到达JDK集合库.它涵盖了您需要做的最常见的事情,显然已经可以使用了.
Google Collections可能是JDK之外最好的高质量库.它使用频繁且得到很好的支持.
Apache Commons Collections比较老,并且受到"太多厨师"问题的影响,但也有很多有用的东西.
Trove为原始键/值等案例提供了非常专业的集合.现在,我们发现在现代JDK和Java 5+集合以及并发用例中,JDK集合甚至超过了专门的Trove集合.
如果你有很高的并发用例,那么你应该在高规模的lib中查看像NonBlockingHashMap这样的东西,这是一个无锁的实现,如果你有合适的用例,它可以踩踏ConcurrentHashMap.
java.util
很抱歉显而易见的答案,但对于大多数用途,默认的Java集合绰绰有余.
要String在地图中存储数百万个内容,请查看http://code.google.com/p/flatmap
京公网安备 11010802040832号 | 京ICP备19059560号-6 