java在集合类型之间转换被认为是不好的形式吗？

Question

我希望这个问题足够具体，可以被认为适合我们的讨论。我查看了FAQ，我认为这是符合条件的，因为它是特定的，并且与编程相关

我正在用Java实现一个复杂的数据挖掘算法（FP-growth）。算法的一些初始阶段要求我扫描一个大型数据库，并对找到的每种项目类型保持运行计数。这似乎非常适合Hashbag接口。我在ApacheCommons中找到了一个似乎适合我的

现在，我的HashBag中充满了[itemType，count]条目（成对）。在后面的算法中，我需要对这些对执行很多类似列表的操作。在某些情况下，我必须按itemType对集合进行排序。在其他情况下，我必须按计数排序。这似乎非常适合List接口

我的结论是，我必须把我的行李袋转换成一份清单。但不知何故，它感觉脏兮兮的，像是在浪费空间和时间。有没有更聪明的方法来做到这一点，或者在编程问题上，您必须在不同的时间以不同的方式对待您的收藏，而转换是一种必要的罪恶，这是一种常见的情况

另一种选择是制作我自己的界面，它确实是一个列表，但允许添加“包样式”。每次我想添加一些东西时，我必须保持列表的排序，并使用自定义比较器执行二进制搜索。构建该集合可能需要比构建Hashbag更长的时间，但我会在最后的转换步骤中节省时间。你认为哪一个更好

谢谢

Answer 1

我假设您使用的是Apache Commons Collections HashBag类。你考虑过用TreeBag来代替吗？它实现了相同的行李接口，但可以根据您提供的比较器有效地对数据进行排序

也就是说，当您需要更改排序顺序时，通常没有比将集合复制到具有不同比较器的新集合更好的答案了

Answer 2

Yet it feels dirty somehow, like a waste of space and time. Is there a smarter way to do this, or is it a common situation to have a programming problem where you must treat your collection differently at different times, and conversions are a necessary evil?

有时需要在集合类型之间进行转换。如果有必要，“肮脏”或“不雅”或“愚蠢”都不是真正相关的

预先考虑这些事情也可能是错误的。实际的计算权衡通常很难把握。例如，如果将HashBag更改为TreeBag，则插入从O(1)到O(logN)，但这样可以避免排序和复制的开销。“大Oh”分析/思考不会给你一个明确的答案。实际上，真正的性能将取决于缩放因子、N值、包中的命中和未命中比率等等

我建议试着以显而易见的方式实施，看看它是否表现得足够好。。。如果不是，请对其进行分析，看看数据结构是否是主要瓶颈。然后，根据分析、和输入数据集的其他测量值，找出从基线实现中提高性能的最佳方法

Answer 3

回答我自己的问题

我用路易斯·沃瑟曼（Louis Wasserman）提到的番石榴图书馆提供的不同类型的Multiset做了一些实验。在我的特定测试用例中，我正在解析一个1GB的XML文件（书籍和作者数据库），并创建一个非常大的多集（记录每个作者在数据库中出现的次数）。一旦解析结束，我需要得到一个新的Multiset，其中只包含出现次数超过x次的作者，其中x是一些阈值。我还希望我的最后一集按作者姓名排序

以下是我尝试的两种不同方式（其中包括）：

1）收集TreeMultiset中的原始计数，然后删除任何不符合阈值的计数 2） 收集HashMultiset中的原始计数，然后创建一个新的TreeMultiset，在这里我添加哈希集中的每个项目，其中的计数满足阈值

第二种方法被证明速度明显更快（大约25%），尽管转换和额外的内存使用。显然，这其中很大一部分是从二叉树中删除是非常低效的

所以这里有一个明确的结论，在这种情况下，转换是一个很好的举动（除非你的内存限制不允许）

再次感谢你把我转到番石榴图书馆，路易斯