java在集合类型之间转换被认为是不好的形式吗?
我希望这个问题足够具体,可以被认为适合我们的讨论。我查看了FAQ,我认为这是符合条件的,因为它是特定的,并且与编程相关
我正在用Java实现一个复杂的数据挖掘算法(FP-growth)。算法的一些初始阶段要求我扫描一个大型数据库,并对找到的每种项目类型保持运行计数。这似乎非常适合Hashbag
接口。我在ApacheCommons中找到了一个似乎适合我的
现在,我的HashBag中充满了[itemType,count]条目(成对)。在后面的算法中,我需要对这些对执行很多类似列表的操作。在某些情况下,我必须按itemType对集合进行排序。在其他情况下,我必须按计数排序。这似乎非常适合List
接口
我的结论是,我必须把我的行李袋转换成一份清单。但不知何故,它感觉脏兮兮的,像是在浪费空间和时间。有没有更聪明的方法来做到这一点,或者在编程问题上,您必须在不同的时间以不同的方式对待您的收藏,而转换是一种必要的罪恶,这是一种常见的情况
另一种选择是制作我自己的界面,它确实是一个列表,但允许添加“包样式”。每次我想添加一些东西时,我必须保持列表的排序,并使用自定义比较器执行二进制搜索。构建该集合可能需要比构建Hashbag更长的时间,但我会在最后的转换步骤中节省时间。你认为哪一个更好
谢谢
# 1 楼答案
我假设您使用的是Apache Commons Collections HashBag类。你考虑过用TreeBag来代替吗?它实现了相同的行李接口,但可以根据您提供的比较器有效地对数据进行排序
也就是说,当您需要更改排序顺序时,通常没有比将集合复制到具有不同比较器的新集合更好的答案了
# 2 楼答案
有时需要在集合类型之间进行转换。如果有必要,“肮脏”或“不雅”或“愚蠢”都不是真正相关的
预先考虑这些事情也可能是错误的。实际的计算权衡通常很难把握。例如,如果将HashBag更改为TreeBag,则插入从
O(1)
到O(logN)
,但这样可以避免排序和复制的开销。“大Oh”分析/思考不会给你一个明确的答案。实际上,真正的性能将取决于缩放因子、N值、包中的命中和未命中比率等等我建议试着以显而易见的方式实施,看看它是否表现得足够好。。。如果不是,请对其进行分析,看看数据结构是否是主要瓶颈。然后,根据分析、和输入数据集的其他测量值,找出从基线实现中提高性能的最佳方法
# 3 楼答案
回答我自己的问题
我用路易斯·沃瑟曼(Louis Wasserman)提到的番石榴图书馆提供的不同类型的
Multiset
做了一些实验。在我的特定测试用例中,我正在解析一个1GB的XML文件(书籍和作者数据库),并创建一个非常大的多集(记录每个作者在数据库中出现的次数)。一旦解析结束,我需要得到一个新的Multiset,其中只包含出现次数超过x
次的作者,其中x是一些阈值。我还希望我的最后一集按作者姓名排序以下是我尝试的两种不同方式(其中包括):
1)收集
TreeMultiset
中的原始计数,然后删除任何不符合阈值的计数 2) 收集HashMultiset
中的原始计数,然后创建一个新的TreeMultiset
,在这里我添加哈希集中的每个项目,其中的计数满足阈值第二种方法被证明速度明显更快(大约25%),尽管转换和额外的内存使用。显然,这其中很大一部分是从二叉树中删除是非常低效的
所以这里有一个明确的结论,在这种情况下,转换是一个很好的举动(除非你的内存限制不允许)
再次感谢你把我转到番石榴图书馆,路易斯