3

我有一个用例，我需要存储大量条目，每个条目具有唯一的集合大小。如果我们将其简化为联系人（问题不是很大）。我们会遇到这样的问题：

假设用户知道他们有多少朋友：

乔 - 玛丽、约翰、鲍勃、汤姆

玛丽 - 卡罗尔、苏西、迈克、弗雷德、罗伯特

因此friends(Joe) = 4，唯一支持的操作是addFriend(Joe, Sam). 虽然 Mary 可能与 Joe 成为朋友，但无需存储任何相关信息。

我不想做的是存储每组中的所有条目，但是布隆过滤器感觉不太对。还有其他选择吗？

更新：挑战在于我有 20M Joe/Mary/... 在顶级集合中，每个集合中有 400 万半不同成员。快速代码示例如下（为简单起见，python）-但在规模+持久存储中，宇宙走到了尽头。

class World:
    def __init__(self):
        self.friends = defaultdict(set)

    def addFriend(self, id, member):
        self.friends[id].add(member)

    def friends(self, id):
        return len(friends[id])
4

1 回答 1

1

由于您正在考虑使用 Bloom 过滤器，因此听起来近似答案就可以了。使用HyperLogLog之类的小空间基数估计器代替self.friends.

于 2013-04-05T12:38:47.197 回答