3
\$\begingroup\$

I attempted to write a read-only dictionary, containing primes:

#inspired by http://ceasarjames.wordpress.com/2011/07/10/the-quadratic-sieve/
class PrimeDict(dict):
    def __init__(self):
        super(PrimeDict,self).__setitem__(2,2)
        self.previous_max = 2

    def __setitem__(self, key, value):
        return self.__getitem__(key) #it's a read-only dict

    def __delitem__(self, key):
        return self.__getitem__(key) #it's a read-only dict

    def __find_primes(self,n):
        if n < self.previous_max: return
        sieve = range(self.previous_max,n)
        for x in self.keys():
            i = x * ((self.previous_max - 1)//x + 1)
            while i < n:
                sieve[i - self.previous_max] = 0
                i += x
        index = self.previous_max
        while index <= n ** 0.5:
            if sieve[index-self.previous_max]:
                i = index ** 2
                while i < n:
                    sieve[i-self.previous_max] = 0
                    i += index
            index += 1
        self.previous_max = n
        for x in sieve:
            if x:
                super(PrimeDict,self).__setitem__(x,x)

    def __getitem__(self,key):
        key = int(key)
        if key>= self.previous_max:
            self.__find_primes((key+1))
        try:
            return super(PrimeDict,self).__getitem__(key)
        except:
            return False

https://gist.github.com/aausch/6709819

Is there any way for me to make this class definition cleaner and/or shorter?

\$\endgroup\$
0

1 Answer 1

8
\$\begingroup\$

1. Comments on your code

  1. No docstrings! What does your class do and how am I supposed to use it? Also, no doctests.

  2. Wouldn't it be more natural for this class to be a set of primes, rather than a dictionary mapping primes to True and other keys to False?

  3. There's only one set of primes, so this is a rare opportunity to make use of the Singleton pattern. That is, each call to PrimeDict() ought to return the same object.

  4. By implementing __setitem__ like this:

    def __setitem__(self, key, value):
        return self.__getitem__(key) #it's a read-only dict
    

    you give callers the false impression that this operation succeeded:

    >>> p = PrimeDict()
    >>> p[1] = True
    >>> # looks good, but:
    >>> p[1]
    False
    

    Instead, you should raise an exception:

    def __setitem__(self, key, value):
        raise TypeError("'PrimeDict' object doesn't support item assignment")
    

    Similarly for __delitem__:

    def __delitem__(self, key):
        raise TypeError("'PrimeDict' object doesn't support item deletion")
    
  5. By deriving your class from Python's dict, you make all of the dict methods available. This means that a caller might accidentally bypass your attempt to make the dictionary read-only, by calling some other method that you haven't overridden. For example:

    >>> p = PrimeDict()
    >>> p.update({1: True})
    >>> p[1]
    True
    

    The thing to do is not to subclass dict, but to subclass collections.abc.Mapping and have the actual dictionary be a member variable. Or, if you take my suggestion in point 2 above, subclass collections.abc.Set and have the actual set as a member variable. I'll show how to do this in my revised code in section 2 below.

  6. The method __find_primes has a private name. Why do you do that? The intended use of private names in Python is to "avoid name clashes of names with names defined by subclasses" but that's obviously not necessary here. All that the private name achieves here is to make your code a bit harder to debug:

    >>> p = PrimeDict()
    >>> p.__find_primes(10)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    AttributeError: 'PrimeDict' object has no attribute '__find_primes'
    >>> p._PrimeDict__find_primes(10)
    >>> p
    {2: 2, 3: 3, 5: 5, 7: 7}
    
  7. You start out by adding 2 to the set of primes and then set self.previous_max = 2. But it would be simpler to start out with the empty set of primes and self.previous_max = 1. The sieve of Eratosthenes is self-starting.

  8. Instead of:

    i = index ** 2
    while i < n:
        sieve[i-self.previous_max] = 0
        i += index
    

    make use of Python's range function, and write:

    for i in range(index ** 2, n, index):
        sieve[i - self.previous_max] = 0
    
  9. The code in __find_primes has to subtract self.previous_max from the array index every time it looks up something in sieve. It would be more efficient to do this subtraction once when setting up the loop bounds. For example, instead of the code that I suggested above:

    for i in range(index ** 2, n, index):
        sieve[i - self.previous_max] = 0
    

    you could write:

    for i in range(index ** 2 - self.previous_max, n - self.previous_max, index):
        sieve[i] = 0
    
  10. The line:

    key = int(key)
    

    can raise ValueError. Wouldn't it be better to return False if key can't be converted to an integer?

2. Revised code

try:
    from collections.abc import Set
except ImportError:
    from collections import Set # Python 3.2 or earlier

class PrimeSet(Set):
    """A PrimeSet object acts like the set of prime numbers:

        >>> p = PrimeSet()
        >>> 2 in p
        True
        >>> 4 in p
        False

    The object sieves for primes as needed. When iterated over, it
    yields the primes found so far:

        >>> 30 in p
        False
        >>> list(p)
        [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    """
    # Singleton pattern: there is only one set of primes.
    instance = None
    def __new__(cls):
        if cls.instance is None:
            cls.instance = super(PrimeSet, cls).__new__(cls)
        return cls.instance

    def __init__(self):
        super(PrimeSet, self).__init__()
        self.max = 1            # Highest number sieved to so far.
        self.set = set()        # Set of primes up to self.max.

    def __iter__(self):
        return iter(self.set)

    def __len__(self):
        return len(self.set)

    def __contains__(self, key):
        try:
            key = int(key)
        except ValueError:
            return False
        if key > self.max:
            self.find_primes(key)
        return key in self.set

    def find_primes(self, n):
        """Sieve for primes from self.max + 1 up to and including n."""
        if n <= self.max:
            return
        sieve = [True] * (n - self.max)
        for p in self:
            for i in range(p - 1 - self.max % p, len(sieve), p):
                sieve[i] = False
        for p, isprime in enumerate(sieve):
            if isprime:
                p += self.max + 1
                self.set.add(p)
                for i in range(p * p - self.max - 1, len(sieve), p):
                    sieve[i] = False
        self.max = n
\$\endgroup\$
4
  • \$\begingroup\$ 2. <-- it's a dictionary mapping primes to themselves; there's no space wasted mapping non-primes to false. I figured a dictionary lookup is faster than a test for inclusion in a set. \$\endgroup\$ Sep 26, 2013 at 17:56
  • \$\begingroup\$ I wasn't concerned about wasted space. My point is that the set of primes is a more natural idea than its characteristic function, and so representing it by a Python set seems more natural to me. \$\endgroup\$ Sep 26, 2013 at 21:53
  • \$\begingroup\$ yeah, i'll definitely re-name the class a "set" instead of a "dictionary", but i'm still not convinced it's a good idea to store all of the "false's" in there. it's probably easier to convince me to use a set data-structure as the underlying store, but i'm not there yet on that one \$\endgroup\$ Sep 26, 2013 at 21:59
  • 1
    \$\begingroup\$ Point 2 is about appropriate interface for an object representing the prime numbers (should it be set-like or dictionary-like?), not about the implementation. My implementation suggestion is that you use a Python set, which of course has no values (False or otherwise), just keys. \$\endgroup\$ Sep 26, 2013 at 22:19

Your Answer

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

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