5

我希望这个问题足够具体，可以被认为适合 StackOverflow。我检查了常见问题解答，我认为这是合格的，因为它是特定的并且与编程相关。

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

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

我的结论是我必须将我的 Hasbag 转换为列表。然而不知何故，它感觉很脏，就像是在浪费空间和时间。有没有更聪明的方法来做到这一点，或者这是一个常见的情况，有一个编程问题，你必须在不同的时间以不同的方式对待你的集合，而转换是必要的邪恶？

一种替代方法是制作我自己的界面，它确实是一个列表，但允许“袋式”添加。每次我想添加一些东西时，我都必须保持列表排序并使用自定义比较器执行二进制搜索。构建该集合可能比构建一个 Hashbag 需要更长的时间，但我会在最后节省转换步骤。关于哪个更可取的任何想法？

谢谢！

4

4 回答 4

3

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

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

于 2012-11-02T02:25:08.300 回答
3

如果您使用Guava Multiset而不是Apache——Bag大致类似，但风格不同——您可以在不转换的情况下完成大部分操作。 Multiset.entrySet()返回 a Set<Entry<E>>，Entry<E>有效地表示一对元素和一个计数 - 这听起来可能是解决您对元素计数对进行操作的最佳方式，也许吧？您可以像遍历Map.entrySet().

您可以使用Multisets.copyHighestCountFirst(Multiset)以最高频率优先顺序重新排序多重集，并使用TreeMultiset直接按元素排序。

（披露：我为 Guava 做出了贡献。）

于 2012-11-02T02:28:22.513 回答
2

然而不知何故，它感觉很脏，就像是在浪费空间和时间。有没有更聪明的方法来做到这一点，或者这是一个常见的情况，有一个编程问题，你必须在不同的时间以不同的方式对待你的集合，而转换是必要的邪恶？

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

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

我建议尝试以明显的方式实现事物，看看它是否表现得足够好......如果不是，则分析它以查看数据结构是否是主要瓶颈。然后根据对输入数据集的分析和其他测量，找出从基线实现中提高性能的最佳方法。

于 2012-11-02T03:23:31.053 回答
0

回答我自己的问题！

我对Multiset上面 Louis Wasserman 提到的 Guava 库提供的不同类型进行了一些实验。在我的特定测试用例中，我正在解析一个 1GB 的 XML 文件（书籍和作者的数据库）并创建一个非常大的 Multiset（记录每个作者在数据库中出现的次数）。一旦我到达解析的末尾，我需要获得一个新的 Multiset，它只包含出现x多次的作者，其中 x 是某个阈值。我还希望我的最终集按作者姓名排序。

以下是我尝试过的两种不同方式（除其他外）：

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

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

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

再次感谢你把我带到 Guava 图书馆，路易斯！

于 2012-11-05T00:14:53.957 回答