# LetterDict, a dictionary whose keys must be lowercase letters [a-z]

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 oth lowercase letter is a key in the dictionary, then the oth 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").

# Counting bits

        K = self.K
i = 0
while (K := K & (K - 1)) & target:
i += 1


This loop is counting the number of 1-bits below the target bit.

The int.bit_count() function can give you the population of 1's in any integer, so this loop could be replaced with one statement:

        i = (self.K & (target - 1)).bit_count()


Note: In Python 3.9 and earlier, you could use:

        i = bin(self.K & (target - 1)).count("1")


but the efficiency of this is questionable due to conversion to string.

# Public -vs- Private

The members K and V should be named _k and _v (or even _keys and _vals)

• The leading underscore, by convention, indicates they are not part of the public interface.
• PEP 8: The Style Guide for Python Code recommends all members use lowercase_lettering. Upper case letters are reserved for use in CONSTANT_VALUES and ClassNames.

# Unused members

The member K is unused in LetterDictSparse, and should be removed.

• Thanks! Made the changes in github. Just for my future reference:int.bit_count() was added in Python 3.10. Oct 12 at 19:38
• Whoops! Didn't notice that. Knew Java has Integer.bitCount() for ever (well, since 1.5 anyway), and knew Python integers had .member_function() methods. Opened an IDLE shell, typed x = 1 and x., pressed tab, saw bit_count in the possible completions, searched bit_count in the Python docs I had open in my browser, copy-pasted the link, and moved on. Didn't notice it was a newly added function. :-p For Python 3.9 and earlier, i = bin(self.K & (target - 1)).count("1") Oct 12 at 19:47
• Still, it's very useful to know about the new function. Thanks again! Oct 12 at 20:10