Cached infinite prime generator

Question

For a project I am working on, I need to use a lot of primes, frequently. To do this, I added a cache to Will Ness's prime sieve, that stores already generated primes so getting them is quick. How can I improve this code?

def prime_sieve(): # postponed sieve, by Will Ness
 for c in (2,3,5,7): # original code David Eppstein,
 yield c
 sieve = {} # Alex Martelli, ActiveState Recipe 2002
 ps = prime_sieve() # a separate base Primes Supply:
 p = next(ps) and next(ps) # (3) a Prime to add to dict
 q = p*p # (9) its sQuare
 for c in count(9,2): # the Candidate
 if c in sieve: # c’s a multiple of some base prime
 s = sieve.pop(c) # i.e. a composite ; or
 elif c < q:
 yield c # a prime
 continue
 else: # (c==q): # or the next base prime’s square:
 s=count(q+2*p,2*p) # (9+6, by 6 : 15,21,27,33,...)
 p=next(ps) # (5)
 q=p*p # (25)
 for m in s: # the next multiple
 if m not in sieve: # no duplicates
 break
 sieve[m] = s # original test entry: ideone.com/WFv4f
class cached_primes:
 def __init__(self):
 self.prime_gen = prime_sieve()
 self.vals = [2]
 next(self.prime_gen)
 def get(self, start=2, end=float('inf')):
 vals = self.vals
 lo = self.get_ind(start)
 if vals[-1] >= end:
 hi = self.get_ind(end)
 yield from islice(vals, lo, hi)
 return
 else:
 while vals[-1] < end:
 if len(vals) > lo:
 bound = len(vals)
 yield from takewhile(lambda p: p <=end, islice(vals, lo, bound))
 lo = bound
 vals.append(next(self.prime_gen))
 hi = self.get_ind(end)
 yield from islice(vals, lo, hi)
 def get_ind(self, x):
 if x <= 2:
 return 0
 vals = self.vals
 B = x/log(x)
 if x < 17:
 return bisect(vals, x, 0, min(len(vals), int(B)))
 return bisect(vals, x, int(B), min(len(vals), int(1.25506*B)))

• Martin R: Can you add a link to the prime sieve solution on which your code is based?
• Oscar Smith: ideone.com/WFv4f

Answer 1

prime_sieve() isn't your code, so I won't review it (although I will express my opinion that it's in dire need of more commenting).

However, the choice to use it is firmly within the scope of this review, and frankly I can't understand it. The whole point of that particular implementation is to optimise memory use at the cost of considerable code complexity. But given that your goal is a fully cached list (i.e. optimising speed at the cost of memory usage), it would make far more sense to me to use a simpler implementation which directly accesses the cache.

---

 if vals[-1] >= end:
 hi = self.get_ind(end)
 yield from islice(vals, lo, hi)
 return
 else:
 while vals[-1] < end:
 if len(vals) > lo:
 bound = len(vals)
 yield from takewhile(lambda p: p <=end, islice(vals, lo, bound))
 lo = bound
 vals.append(next(self.prime_gen))
 hi = self.get_ind(end)
 yield from islice(vals, lo, hi)

Taking a step back to look at the structure, we have

 if condition():
 foo()
 return
 else:
 while not condition():
 bar()
 foo()
 return # implicit because it's the end of the function

Firstly,

 return
 else:

can often be clearer without the else, which is unnecessary: the scope it defines is unreachable if the if block executed. That gives

 if condition():
 foo()
 return
 while not condition():
 bar()
 foo()
 return

which is semantically identical to

 while not condition():
 bar()
 foo()
 return

---

 while vals[-1] < end:
 if len(vals) > lo:
 bound = len(vals)
 yield from takewhile(lambda p: p <=end, islice(vals, lo, bound))
 lo = bound
 vals.append(next(self.prime_gen))

The whole if clause in here seems dubious to me. Why can't it be removed entirely? (I figured out the reason, but IMO there should be a comment to save me the effort).

Given that all but the first time round it will yield from a slice containing precisely one value (the one appended the previous time round), it seems rather heavyweight. It would probably make sense to refactor as:

 yield from (something)
 while vals[-1] < end:
 extension = next(self.prime_gen)
 vals.append(extension)
 yield extension

---

Further modification to the final refactors implemented for the above points may come from the simpler replacement of prime_gen. Do you want a replacement with produces primes one at a time, or something like a paged sieve? The latter should be more efficient, but at the cost of slight complication.

---

 def get_ind(self, x):

If I had to guess without any contextual clues, I would assume that ind is short for independent. If it's necessary to abbreviate index then I consider idx to be the best option. But here there is a clear correct name for the method: index, for consistency with list.index.

(Of course, that's assuming you want it to be public. Given that it returns incorrect values for primes which haven't yet been reached by get, it would probably be better to call it _index).