我尝试用 std::priority_queue 替换 std::multiset。但我对速度结果感到失望。算法运行时间增加 50%...

以下是相应的命令：

我对priority_queue 实现的速度感到惊讶，我期待不同的结果（对PQ 更好）......从概念上讲，多重集被用作优先级队列。为什么优先级队列和多重集具有如此不同的性能，即使是-O2？

十个结果的平均值，MSVS 2010，Win XP，32 位，方法 findAllKNN2()（请参见下文）

什么可能导致这些结果？没有对源代码进行其他更改...感谢您的帮助...

微软实施：

方法：

PQ 实施（较慢，为什么？）

方法：

如何访问存储在数据结构 multiset、C++ 中的值？

我希望有人能够帮助我，至少对我来说，这是一个相当棘手的算法。

问题

我有一个 List ( 1 <= size <= 5，但直到运行时大小未知) List ( 1 <= size <= 2) 需要组合。这是我正在查看的示例：-

所以，我需要做的有两个阶段：-

(1)。我需要以这样一种方式组合内部列表，即任何组合在每个列表中都只有一个项目，也就是说，这里结果集中的可能组合是：-

• 1,2,2,4,2
• 1,2,2,4,3
• 1,2,3,4,2
• 1,2,3,4,3
• 1,3,2,4,2
• 1,3,2,4,3
• 1,3,3,4,2
• 1,3,3,4,3

笛卡尔积会处理这个问题，所以第 1 阶段已经完成......现在，我想不通的转折出现了 - 至少我想不出 LINQ 的方法（我仍然一个 LINQ 菜鸟）。

(2)。我现在需要从这个笛卡尔积中过滤掉任何重复的结果。在这种情况下，重复构成结果集中的任何行，每个不同列表元素的数量与另一行相同，即，

1,2,2,4,3 与 1,3,2,4,2 “相同”

因为第一个列表中的每个不同项目在两个列表中出现的次数相同（1 在每个列表中出现一次，2 在每个列表中出现两次，...

因此，最终结果集应如下所示...

• 1,2,2,4,2
• 1,2,2,4,3
• --
• 1,2,3,4,3
• --
• --
• --
• 1,3,3,4,3

另一个例子是最坏的情况（从组合的角度来看）ListOfLists 是 {{2,3}, {2,3}, {2,3}, {2,3}, {2,3} }，即包含最大大小的内部列表的列表 - 在这种情况下，笛卡尔积结果集中显然会有 32 个结果，但我试图得到的修剪结果集只是： -

• 2,2,2,2,2
• 2,2,2,2,3 <-- 所有其他带有四个 2 和一个 3（以任何顺序）的结果都被抑制
• 2,2,2,3,3 <-- 三个 2 和两个 3 的所有其他结果都被抑制，等等
• 2,2,3,3,3
• 2,3,3,3,3
• 3,3,3,3,3

对于任何有数学头脑的人-我希望你能提供帮助。实际上，我已经为第 2 部分找到了一个可行的解决方案，但它完全是 hack，并且计算量很大，我正在寻找指导以找到更优雅、更有效的 LINQ 解决方案来解决修剪问题。

谢谢阅读。

点子

到目前为止使用的一些资源（获取笛卡尔积）

• 使用 linq 计算笛卡尔积
• c-permutation-of-an-array-of-arraylists
• 微软

更新 - 解决方案

抱歉没有早点发布……见下文

我已经定义了一个java.util.Collection有效的子接口是一个多重集（又名包）。它可能不包含null元素，尽管这对我的问题并不重要。接口定义的 equals 契约如你所料：

• obj instanceof MyInterface
• objthis包含与(by equals)相同的元素
• obj每个元素包含相同数量的重复项
• 元素的顺序被忽略

现在我想写我的hashCode方法。我最初的想法是：

但是，我注意到com.google.common.collect.Multiset（来自 Guava）将哈希码定义如下：

让我感到奇怪的是，一个空的 Multiset 的哈希码为 0，但更重要的是，我不明白^ count(o)简单地将每个重复项的哈希码相加的好处。也许这是关于不多次计算相同的哈希码，但为什么不* count(o)呢？

我的问题：什么是有效的哈希码计算？在我的情况下，一个元素的数量不能保证很便宜。

我在番石榴中有一个多重集，我想检索给定元素的实例数而不迭代这个多重集（我不想迭代，因为我假设迭代需要相当长的时间，因为它会查看所有集合）。

为此，我首先考虑使用 multiset 的 entryset() 方法，以获取具有单个实例及其相应计数的集合。然后，将此集合转换为哈希图（其中键是我的集合的元素，值是它们的实例计数）。因为那时我可以使用 hashmap 的方法直接从它的键中检索一个值 - 完成！但这只有在我可以快速将集合转换为哈希图时才有意义（无需遍历所有元素）：这可能吗？

（正如我所说，我希望这个问题在多个方面存在缺陷，如果您能阐明我可能在这里犯的概念错误，我会很高兴。谢谢！）

I am given a bag B (multiset) of characters with the size m and a string text S of size n. Is it possible to find all substrings that can be created by B (4!=24 combinations) in S in linear time O(n)?

Example:

The fastest solution I found is to keep a counter for each character and compare it with the Bag in each step, thus the runtime is O(n*m). Algorithm can be shown if needed.

有没有一种有效的方法可以从排序的多重集（TreeMultiset）中获取 n 个较高的条目？

为了说明我的意思，我发布了我效率低下的解决方案：

在这个例子中，DataSet 可以看作是 Object，而 this.coreData 是下属的 TreeMultiset。

我对这个话题真的很陌生，所以各种评论将不胜感激。

我目前正在处理一项尝试实现 Bag 抽象数据类型的任务（所以我宁愿不发布完整的代码）。

以下是我目前正在尝试实现的方法：

我将元素存储为动态数组。

我的问题是，当新包被退回时，我可以很好地打印基数（打印到 4，原始包每个有两个元素），但是动态数组不包含数字（它打印出一些随机数，例如-1789102)。但是，当我尝试在返回袋子之前打印出元素时，它打印得很好。

毫无疑问，这将是一件微不足道的事情，但我会很感激你的帮助。

谢谢。

我的 MultiSet 类的一些方法存在一些问题。这是一个测试器，MultiSet 类应该得到输出：“Succes！” 如果它工作正常。这是测试仪：

还有我的 Multiset 类：

也许如果您可以在添加或删除的过程中帮助我，那么我可能可以解决另一个问题。

此外，我的 equals 似乎无法正常工作，我不确定如何在 String toString 处计算“res”。不要介意我的退货声明，稍后我会加上一些括号等以使其看起来不错。

谢谢您的帮助。// 克里斯

这是我的课：

所以基本上，我需要正确实现我的添加/删除方法，向/从Set.

对我来说，我的观点似乎equals是正确的，但 Eclipse 在一行中说：

有unchecked cast from object to Multiset<E> 什么想法吗？

另外，在我的toString方法中，我不是 100% 确定如何定义“res”？

谢谢，//克里斯