3
\$\begingroup\$

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

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks! Made the changes in github. Just for my future reference:int.bit_count() was added in Python 3.10. \$\endgroup\$
    – joseville
    Oct 12, 2021 at 19:38
  • 1
    \$\begingroup\$ 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") \$\endgroup\$
    – AJNeufeld
    Oct 12, 2021 at 19:47
  • \$\begingroup\$ Still, it's very useful to know about the new function. Thanks again! \$\endgroup\$
    – joseville
    Oct 12, 2021 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.