Looking for any suggestions - alternative design, improvements to readability, improvements to the comments, etc.
I implemented this letter dictionary to see if it would faster than a regular dictionary in a Trie implementation. Keys into this dictionary must be lowercase letters. LetterDict
maintains an integer bitset, K
, and a list, V
s.t. if the o
th lowercase letter is a key in the dictionary, then the o
th bit of K
is set and V
holds the value corresponding to the letter key. For example, the regular dictionary {'c': 22, 'a': 0, 'b': 11, 'd': 33, 'x': 23, 'j': 10}
would be maintained as:
zy xwvu tsrq ponm lkji hgfe dcba <- letter
54 3210 9876 5432 1098 7654 3210 <- letter/bit index
K = 0b00_1000_0000_0000_0010_0000_1111 <- keys
a b c d j x <- keys
V = [0, 11, 22, 33, 10, 23] <- values
class LetterDictCompact:
'''A dicitionary whose keys must be lowercase letters [a-z].'''
ORD_a = ord('a')
def __init__(self):
self.K = 0b0 # keys are lowercase letters [a-z]
self.V = [] # values can be anything
def __contains__(self, key: str) -> bool:
o = ord(key) - self.ORD_a
return self.K & (1 << o)
def __getitem__(self, key: str):
present, i = self.__i(key)
if present:
return self.V[i]
raise KeyError(key)
def __setitem__(self, key: str, val):
present, i = self.__i(key)
if present:
self.V[i] = val
else:
self.V.insert(i, val)
def setdefault(self, key: str, defval=None):
present, i = self.__i(key)
if present:
return self.V[i]
self.V.insert(i, defval)
return defval
# SIDE EFFECT: Modifies self.K
# As such, __contains__ should not call this method
def __i(self, key: str) -> tuple[bool, int]:
o = ord(key) - self.ORD_a
target = 1 << o
present = self.K & target
self.K |= target
K = self.K
i = 0
while (K := K & (K - 1)) & target:
i += 1
return present, i
I also implemented a version of LetterDict
that is not as compact because it maintains V
as a constant-26-length list
(actually, as a constant-27-length because an extra character is needed to denote the end of a word in the Trie implementation). As mentioned, this version is not as compact, but it does simplify the logic a lot:
class LetterDictSparse:
'''A dicitionary whose keys must be lowercase letters [a-z].'''
NUM_LETTERS = 26 + 1 # + 1 to accomoated Trie.END = chr(ord('z') + 1)
EMPTY_VALUE = object() # Cannot be `None` because `None` is a possible value
ORD_a = ord('a')
def __init__(self):
self.K = 0b0 # keys are lowercase letters [a-z]
self.V = [self.EMPTY_VALUE] * self.NUM_LETTERS # values can be anything
def __contains__(self, key: str) -> bool:
o = ord(key) - self.ORD_a
return self.V[o] != self.EMPTY_VALUE
def __getitem__(self, key: str):
o = ord(key) - self.ORD_a
if (val := self.V[o]) == self.EMPTY_VALUE:
raise KeyError(key)
return val
def __setitem__(self, key: str, val):
o = ord(key) - self.ORD_a
self.V[o] = val
def setdefault(self, key: str, defval=None):
o = ord(key) - self.ORD_a
if (val := self.V[o]) == self.EMPTY_VALUE:
self.V[o] = defval
return defval
return val
Both of the above implementations of LetterDict
are correct in as much as I used them to implement a Trie and that Trie passed all the leetcode Trie tests. Here you can see the code in context.
In general, any dictionary whose keys are restricted to fall within a contiguous range of values can be implemented like LetterDictCompact
and LetterDictSparese
for some definition of "contiguous range of values" (what's required is that there's a one-to-one mapping between the "contiguous range of values" to the range [0..N]
for N
equal to the number of values in the "contiguous range of values").