7 java performance data-structures
我有一个文件,它有许多随机整数(大约一百万),每个整数由一个空格分隔.我需要在该文件中找到前10个最常出现的数字.在java中执行此操作的最有效方法是什么？我能想到1.创建一个哈希映射,key是文件中的整数,值是count.对于文件中的每个数字,检查哈希映射中是否已存在该键,如果是,则值为++,否则在哈希值2中创建一个新条目.创建一个BST,每个节点都是该文件中的整数.对于文件中的每个整数,如果是,则查看BST中是否有节点,执行值++,value是节点的一部分.
如果我能提出良好的散列函数,我觉得哈希映射是更好的选择,有人可以告诉我这样做最好吗？我还能使用其他有效的算法吗？
编辑#2:
好吧,我搞砸了自己的第一条规则 - 永远不要过早优化.最糟糕的情况可能是使用范围广泛的股票HashMap - 所以我就这样做了.它仍然在一秒钟内运行,所以忘记这里的其他一切,就这样做.
在担心棘手的实施之前,我会另外注意自己总是测试速度.
(以下是较旧的过时帖子,如果有人有超过一百万的点数,那么它仍然有效)
HashSet可以工作,但是如果你的整数有一个合理的范围(比如1-1000),那么创建一个1000个整数的数组会更有效,并且对于你的每一百万个整数,增加数组的那个元素.(与HashMap几乎相同的想法,但优化Hash必须允许的一些未知数应该使它快几倍).
您还可以创建一棵树.树中的每个节点都包含(value,count),树将按值组织(左侧较低值,右侧较高).遍历到您的节点,如果它不存在 - 插入它 - 如果是,则只增加计数.
值的范围和分布将决定这两个(或常规哈希)中的哪一个会表现得更好.我认为常规哈希不会有很多"获胜"的情况(它必须是一个宽范围和"分组"的数据,即使这样树也可能获胜.
由于这非常简单 - 我建议您针对实际数据集实施多个解决方案和测试速度.
编辑:RE评论
TreeMap可以工作,但仍会添加一层间接(实现自己非常容易和有趣).如果使用stock实现,则必须使用Integers并在每次增加时不断地转换为int.指向Integer的指针是间接的,并且您存储的对象数量至少为2x.这甚至不计算方法调用的任何开销,因为它们应该内联运气.
通常这将是一个优化(邪恶),但是当你开始接近数十万个节点时,你偶尔必须确保效率,因此内置的TreeMap由于内置HashSet的原因而效率低下将.
Java处理散列.您不需要编写哈希函数.刚开始在哈希映射中推送东西.
此外,如果这只需要运行一次(或仅偶尔运行),那么不要同时进行优化.它会足够快.如果它是在应用程序中运行的东西,那就麻烦了.