設置大量集合的大小

Question

我有一個用例，我需要爲每個集合存儲大量具有唯一集合大小的條目。如果我們將其簡化爲聯繫人（問題非常嚴重）。我們必須像一個問題：

由於用戶知道他們有多少朋友有：

喬 - 瑪麗，約翰，鮑勃，湯姆

瑪麗 - 卡羅爾，蘇茜，邁克，弗雷德， Robert

因此friends(Joe) = 4 - 唯一支持的操作是addFriend(Joe, Sam)。雖然瑪麗可能是喬的朋友，但沒有必要存儲任何相關信息。

我不想做的是將所有條目存儲在每個集合中，但是布隆過濾器並不完全正確。還有其他的選擇嗎？

更新：挑戰是我有20M喬/瑪麗/ ...在頂層設置與每組4M半獨特的成員。快速代碼示例如下（爲簡單起見，python） - 但是在規模+持久存儲中，Universe即將結束。

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]) 

Answer 1

由於您正在考慮使用Bloom過濾器，因此聽起來好像近似的答案是可以的。使用像HyperLogLog這樣的小空間基數估計器代替self.friends。