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

Question

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").

Answer 1

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.