Some questions can't be answered by one shard. "list everything" has to visit them all. That fan-out-and-combine pattern is scatter-gather, and it's why cross-shard queries are expensive.
all_items(): merge every shard's contents into one dict of all key/value pairs (count() is already implemented)class ShardedDB:
def __init__(self, num_shards):
self.num_shards = num_shards
self.shards = [dict() for _ in range(num_shards)]
def _hash(self, key):
h = 0
for ch in str(key):
h = (h * 31 + ord(ch)) & 0xffffffff
return h
def _shard_for(self, key):
return self._hash(key) % self.num_shards
def put(self, key, value):
self.shards[self._shard_for(key)][key] = value
def get(self, key):
return self.shards[self._shard_for(key)].get(key)
def all_items(self):
"""Gather every key/value pair from all shards into one dict."""
# TODO: visit each per-shard dict in self.shards and merge its pairs
# into one fresh combined dict, then hand that dict back.
# A database with nothing stored must gather an empty dict.
pass
def count(self):
return sum(len(shard) for shard in self.shards)
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Some questions can't be answered by one shard. "list everything" has to visit them all. That fan-out-and-combine pattern is scatter-gather, and it's why cross-shard queries are expensive.
all_items(): merge every shard's contents into one dict of all key/value pairs (count() is already implemented)Press Run Tests or ⌘↩ to check your solution.