3

多数のエントリをそれぞれに固有のセット サイズで保存する必要があるユース ケースがあります。これを連絡先に単純化すると(問題はほとんどありません)。次のような問題があります。

ユーザーが自分の友達の数を知っているとします。

ジョー - メアリー、ジョン、ボブ、トム

メアリー - キャロル、スージー、マイク、フレッド、ロバート

したがってfriends(Joe) = 4、サポートされている唯一の操作は ですaddFriend(Joe, Sam)。Mary は Joe の友達かもしれませんが、その関連情報を保存する必要はありません。

すべてのエントリを各セットに格納することは避けたいと思いますが、ブルーム フィルタはあまり適切ではありません。他の選択肢はありますか?

更新:課題は、各セットに 400 万人の半個別メンバーを持つトップ レベル セットに 2,000 万人のジョー/メアリー/... がいるということです。簡単なコード例を以下に示します (わかりやすくするために 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

ブルーム フィルターを検討しているため、おおよその答えで問題ないように思えます。の代わりに、HyperLogLogのような小さなスペースの基数推定器を使用しself.friendsます。

于 2013-04-05T12:38:47.197 に答える