Java中Collection类的性能

Question

所有,

我一直在浏览很多关于各种Action类的性能的网站,包括添加元素,搜索和删除.但我也注意到它们都提供了不同的测试环境,即操作系统,内存,线程运行等.

我的问题是,是否有任何网站/材料在最佳测试环境基础上提供相同的性能信息？即,配置不应成为任何特定数据结构性能不佳的问题或催化剂.

[更新]:示例,HashSet和LinkedHashSet都具有插入元素的复杂度O(1).但是,Bruce Eckel的测试声称,LinkedHashSet的插入时间比HashSet要多[http://www.artima.com/weblogs/viewpost.jsp?thread=122295].那么我还应该使用Big-Oh表示法吗？

Answer 1

以下是我的建议:

1. 首先,不要优化:)不是我告诉你设计废话软件,而是仅仅关注设计和代码质量而不是过早优化.假设你已经做到了,现在你真的需要担心哪个集合最好超出纯粹的概念原因,让我们继续前进到第2点
2. 真的,不要优化(大致从MA杰克逊偷来)
3. 精细.所以你的问题是,即使你有最佳案例,最坏情况和平均案例的理论时间复杂度公式,你已经注意到人们说不同的东西,实际设置与理论完全不同.所以运行自己的基准测试!你只能阅读这么多,而当你这样做时,你的代码就不会自己写.完成理论后,编写自己的基准测试 - 针对您的实际应用程序,而不是用于测试目的的一些不相关的迷你应用程序 - 并查看您的软件实际发生了什么以及原因.然后选择最好的算法.它是经验性的,它可以被视为浪费时间,但它是实际上完美无缺的唯一方式(直到你到达下一点).
4. 既然你已经做到了,那么你拥有最快的应用程序.直到下一次更新JVM.或者操作系统的某些底层组件,您的特定性能瓶颈取决于.你猜怎么着？也许你的客户有不同的.有趣的是:您需要确保您的基准测试对其他人或大多数情况有效(或者为不同的情况编写代码很有乐趣).您需要从用户收集数据.手.然后你需要一遍又一遍地看看会发生什么,如果它仍然成立.然后一遍又一遍地重写你的代码(现在已经终止 - 工程Windows 7博客实际上是一个很好的例子,说明用户数据收集如何帮助做出有根据的决策来改善用户体验.

或者你可以......你知道......不优化.平台和编译器将会改变,但一个好的设计 - 平均 - 应该表现得足够好.

您还可以做的其他事情:

• 看看JVM的源代码.这是非常有教育意义的,你发现了一大堆隐藏的东西(我不是说你必须使用它们......)
• 在TODO列表中查看您需要处理的其他事项？是的,靠近顶部的那个,但你总是跳过因为它太难或不够有趣.那一个就在那里.好了,让优化的东西独自一人:它是Pandora's Box和Moebius乐队的邪恶孩子.你永远不会摆脱它,你会深感遗憾的是你试图用它.

话虽如此,我不知道为什么你需要提升性能,所以也许你有一个非常正确的理由.

我并不是说选择正确的收藏并不重要.只有那些你知道哪一个选择特定问题,并且你已经看过其他选择,那么你已经完成了你的工作,而不必感到愧疚.这些集合通常具有语义含义,只要你尊重它,你就没事了.

Answer 2

在我看来,您需要了解的有关数据结构的所有操作都是对其进行操作的Big-O,而不是来自不同体系结构的主观测量.不同的集合有不同的用途.

Maps是字典
Set的断言唯一性
List提供分组和保留迭代顺序
Trees提供廉价的排序和快速搜索动态变化的内容,需要不断的排序

编辑包括bwawok关于树结构用例的声明

从LinkedHashSet上的javadoc 更新

Set接口的哈希表和链表实现,具有可预测的迭代顺序.

...

由于维护链表的额外费用,性能可能略低于HashSet的性能,但有一个例外:对LinkedHashSet的迭代需要与集合大小成比例的时间,无论其容量如何.对HashSet的迭代可能更昂贵,需要与其容量成比例的时间.

现在我们已经从选择适当的数据结构接口的一般情况转变为使用哪种实现的更具体的情况.但是,我们最终得出的结论是,基于每个实现提供的独特,微妙的不变量,特定实现非常适合于特定应用程序.

Answer 3

您需要了解他们,为什么？基准测试显示给定JDK和硬件设置的原因是它们(理论上)可以再现.你应该从基准测试得到的是对事物如何运作的想法.对于ABSOLUTE数字,您需要根据自己的代码运行它来做自己的事情.

最重要的是要知道各种集合的Big O运行时.知道从未排序的ArrayList中获取一个元素是O(n),但是从HashMap中获取它是O(1)是巨大的.

如果您已经为给定的工作使用了正确的集合,那么您将有90%的工作时间.当你需要担心从HashMap中获取项目的速度时,应该是非常罕见的.

一旦你离开单线程域并进入多线程域,你将需要开始担心像ConcurrentHashMap和Collections.synchronized hashmap这样的事情.在你是多线程之前,你可以不用担心这种东西,并专注于哪个集合使用.

更新到HashSet与LinkedHashSet

我还没有找到一个需要链接哈希集的用例(因为如果我关心顺序我倾向于有一个List,如果我关心O(1)得到,我倾向于使用HashSet.实际上,大多数代码将使用ArrayList,HashMap或HashSet.如果您还需要其他任何东西,那么您处于"边缘"状态.