我需要改进这个问题的有效解决方案:
系统从网络中的用户获取消息。 每次用户发布消息时，我们都会为该用户增加总计数器 (totCounter) 和用户消息计数器 (userMessagesCounter)。为此，我们有一个包含 users(keys) 和 userMessagesCounter(values) 的 HashMap 。 因此，为了获得在网络中发送超过 10% 消息的用户，我们所做的就是遍历哈希表，检查每个用户是否 (userMessagesCounter/totCounter) > 0.1 ，如果是，我们将用户 key 添加到一个数组列表。最后我们返回这个列表。 这需要 O(n)，因为我们遍历所有用户。
我需要改进这个系统，让它以最快的速度运行。 我想到的是这个事实:负载超过 10% 的用户不能超过 10 个(因为我们有超过 100%)。 因此，我可以创建一个大小为 10 的数组并在消息到达时更新它。问题是当一条新消息到达时，这个数组信息可能不再有效，我需要为每条到达的消息重新检查所有数组元素。
有没有人知道如何使用我提出的想法在 O(10)(实际上就像 O(1))中解决这个问题？
非常感谢。
最佳答案
您正在寻找频繁挖掘算法，该算法寻找重复 theta 的项目(在您的情况下为 theta=0.1 )集合中的时间。
使用 1/theta 处理它的方法线性时间中的空间由 Karp-Papadimitriou-Shanker 提出:A Simple Algorithm for Finding Frequent
Elements in Streams and Bags
1. PF = ∅
2. foreach element e∈S {
3. if PF.hasKey(e) { // increase counter
4. PF.value(e)++ // of existing elements
5. }
6. Else {
7. PF.insert(e,1) // insert new element
8. If |PF|== 1/θ { // but if PF is full
9. Foreach key ∈ PF {
10. PF.value(k)-- // decrease all counters
11. if PF.value(k) == 0 { // and remove
12. PF.remove(k) // elements at 0
13. } } } } }
14. Output PF
伪代码取自 lecture notes in Tehcnion's big data course
在这里，您的“流”是发送的消息，当您寻找频繁发送消息的用户时 - 检查当前候选人 PF ，即 O(1)对于常量 theta=0.1 .
该算法产生 1/theta (在你的情况下是 10 个)“频繁”的候选者，但它有误报——这意味着它可能指出某些东西“可能频繁”，而事实并非如此——但这对你来说不应该很难，因为你可以简单验证一下，
关于arrays - 查找负载超过 10% 网络的用户，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29186643/