Can't wait.
Try it whilst it's fresh rather than waiting for a new year.
Monday, December 31, 2012
Tuesday, December 11, 2012
Extensible sieve of Eratosthenes
I was creating a Carmichael triplets generator and needed a function to tell me if a number was prime. It wasn't immediately clear what the largest prime for checking would be so I decided to look into creating an extensible prime generator - If given a number to check for prime-ness that was outside its range, it would attempt to extend its range.
I stopped modifying the class as soon as it was working as the Carmichael generator task then ran in acceptable time.
class Isprime(): ''' Extensible sieve of Erastosthenes >>> isprime.check(11) True >>> isprime.multiples {2, 4, 6, 8, 9, 10} >>> isprime.primes [2, 3, 5, 7, 11] >>> isprime(13) True >>> isprime.multiples {2, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22} >>> isprime.primes [2, 3, 5, 7, 11, 13, 17, 19] >>> isprime.nmax 22 >>> ''' multiples = {2} primes = [2] nmax = 2 def __init__(self, nmax): if nmax > self.nmax: self.check(nmax) def check(self, n): if type(n) == float: if not n.is_integer(): return False n = int(n) multiples = self.multiples if n <= self.nmax: return n not in multiples else: # Extend the sieve primes, nmax = self.primes, self.nmax newmax = max(nmax*2, n) for p in primes: multiples.update(range(p*((nmax + p + 1) // p), newmax+1, p)) for i in range(nmax+1, newmax+1): if i not in multiples: primes.append(i) multiples.update(range(i*2, newmax+1, i)) self.nmax = newmax return n not in multiples __call__ = check
Now I wouldn't be surprised if some of the loop indices are not optimum and are maybe recomputing a few values that don't need to be, and this code is only efficient enough for my purposes; (a couple of Rosetta Code entries in other languages state that they are based on the Python but make changes so that is an indication).
Wednesday, December 05, 2012
That grouping by zip/iter trick explained
In Python 2.7 you can get the following neat chunking of items in a list through application of zip and iter:
It is not as neat in Python 3.X as you have to wrap the expression in list(..) to see the final list.
I thought I had to think hard about what was going on here so here is my annottated Python 3.x session that explains what is going on:
For me it remains a curiosity as I doubt I will have a use for its functionality. (List-size must be a multiple of chunk-size; its functionality is obscure).
Python 2.7.3 (default, Apr 10 2012, 23:24:47) [MSC v.1500 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> items, chunk = [1,2,3,4,5,6,7,8,9], 3 >>> zip(*[iter(items)]*chunk) [(1, 2, 3), (4, 5, 6), (7, 8, 9)] >>>
It is not as neat in Python 3.X as you have to wrap the expression in list(..) to see the final list.
I thought I had to think hard about what was going on here so here is my annottated Python 3.x session that explains what is going on:
Python 3.3.0 (v3.3.0:bd8afb90ebf2, Sep 29 2012, 10:57:17) [MSC v.1600 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> from pprint import pprint as pp >>> items, chunk = [1,2,3,4,5,6,7,8,9], 3 >>> items [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> chunk 3 >>> # A quick recap of what an iterator does >>> i = iter(items) >>> i.__next__() 1 >>> i.__next__() 2 >>> i.__next__() 3 >>> i.__next__() 4 >>> i.__next__() 5 >>> i.__next__() 6 >>> i.__next__() 7 >>> i.__next__() 8 >>> i.__next__() 9 >>> i.__next__() Traceback (most recent call last): File "" , line 1, ini.__next__() StopIteration >>> >>> # Three copies of the same iterator >>> threei = [iter(items)] * chunk >>> pp(threei) [object at 0x0000000003259D30>, object at 0x0000000003259D30>, object at 0x0000000003259D30>] >>> # (notice that the addresses above are the same) >>> >>> # Lets break-out the three copies >>> i, j, k = threei >>> i object at 0x0000000003259D30> >>> j object at 0x0000000003259D30> >>> k object at 0x0000000003259D30> >>> # i,j and k are the same iterator >>> i.__next__() 1 >>> j.__next__() 2 >>> k.__next__() 3 >>> # ... >>> >>> # Lets try that again with zip: >>> i, j, k = threei = [iter(items)] * chunk >>> list(zip(i, j, k)) [(1, 2, 3), (4, 5, 6), (7, 8, 9)] >>> # zip pulls from i, j, k once to form its first tuple of the list >>> # then pulls from i, j, k again to form its second tuple of the list >>> # and so on ... >>> # Because i,j, and k are names for the same iterator we get the >>> # given grouping action as output. >>> >>> # We could use *threei instead of i,j,k as the arguments to zip: >>> i, j, k = threei = [iter(items)] * chunk >>> list(zip(*threei)) [(1, 2, 3), (4, 5, 6), (7, 8, 9)] >>> >>> # Or we could use the expression generating threei: >>> i, j, k = threei = [iter(items)] * chunk >>> list(zip(*[iter(items)] * chunk)) [(1, 2, 3), (4, 5, 6), (7, 8, 9)] >>> # But note that we are relying on the unary '*' operator >>> # binding less strongly than binary '*' >>>
For me it remains a curiosity as I doubt I will have a use for its functionality. (List-size must be a multiple of chunk-size; its functionality is obscure).