tomviner · February 16, 2019 22:41 · May 30, 2016 · May 30, 2016 · May 30, 2016 · May 30, 2016
diff --git a/time_complexity.py b/time_complexity.py
@@ -0,0 +1,24 @@
+"""
+# python 2 only :-(
+pip install big_o
+"""
+
+from sieve import (
+    sieve_brevity_ad_absurdum,
+    sieve_absurder_brevity,
+    sieve_itertools,
+    genuine_sieve_of_eratosthenes,
+)
+
+import big_o
+
+sieves = (
+    sieve_brevity_ad_absurdum,
+    sieve_absurder_brevity,
+    sieve_itertools,
+    genuine_sieve_of_eratosthenes,
+)
+
+for sieve in sieves:
+    best, rest = big_o.big_o(sieve, big_o.datagen.n_, min_n=10, max_n=10000)
+    print '{:>27} {}'.format(sieve.__name__, best)
diff --git a/sieve.py b/sieve.py
@@ -8,6 +8,12 @@
 except ImportError:
     pass
 
+try:
+    # Python 2 compat
+    range = xrange
+except NameError:
+    pass
+
 
 def sieve_brevity_ad_absurdum(limit):
     candidates = set(range(2, limit + 1))
@@ -58,37 +64,34 @@ def sieve_itertools(limit):
     return list(takewhile(lambda x: x <= limit, _sieve_itertools())), _loops
 
 
-def sieve_tersified(limit):
+def genuine_sieve_of_eratosthenes(limit):
+    """ See https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf """
     candidates = set(range(2, limit + 1))
 
     loops = 0
     for n in candidates:
-        # the pragmatic way to reduce number of loops :-)
         if n > sqrt(limit):
             continue
         loops += 1
-
-        def is_multiple(x):
-            return x % n == 0
-
-        sieved = set(filter(is_multiple, candidates - {n}))
+        # real sieve of eratosthenes!
+        sieved = set(range(n * n, limit + 1, n))
+        # create new candidates object, for loop continues over the original
         candidates = candidates - sieved
 
     return sorted(candidates), loops
 
-
 if __name__ == '__main__':
-    limit = 999
+    limit = 5000
 
     sieves = (
         sieve_brevity_ad_absurdum,
         sieve_absurder_brevity,
         sieve_itertools,
-        sieve_tersified,
+        genuine_sieve_of_eratosthenes,
     )
     for sieve in sieves:
         start = time.time()
         primes, loops = sieve(limit)
         end = time.time()
-        print('{:>27} {:4d} loops, {:.4f}s, {} primes: {}'.format(
+        print('{:>30} {:4d} loops, {:.4f}s, {} primes: [...{}'.format(
             sieve.__name__, loops, end - start, len(primes), str(primes)[-50:]))
diff --git a/sieve.py b/sieve.py
@@ -3,9 +3,10 @@
 import time
 
 try:
-    from itertools import ifilter
-except NameError:
-    ifilter = filter
+    # Python 2 compat
+    from itertools import ifilter as filter
+except ImportError:
+    pass
 
 
 def sieve_brevity_ad_absurdum(limit):

diff --git a/sieve.py b/sieve.py
@@ -1,7 +1,12 @@
-from itertools import count, ifilter, takewhile
+from itertools import count, takewhile
 from math import sqrt
 import time
 
+try:
+    from itertools import ifilter
+except NameError:
+    ifilter = filter
+
 
 def sieve_brevity_ad_absurdum(limit):
     candidates = set(range(2, limit + 1))
@@ -40,13 +45,13 @@ def _sieve_itertools():
         n = next(candidates)
         yield n
 
-        # the ifilter here needs to be wrapped in a function otherwise it
-        # fails to retain the local variable context when later lazily run
-        def filter_out_multiples(it, n=n):
-            return ifilter(lambda x: x == n or x % n != 0, it)
+        # this needs to be wrapped in a function otherwise it fails to retain
+        # the local variable context when later lazily run
+        def filter_out_multiples(it, prime=n):
+            return filter(lambda x: x % prime != 0, it)
 
         # compose a stack of iterators that each remove multiples of a prime
-        candidates = filter_out_multiples(candidates, n=n)
+        candidates = filter_out_multiples(candidates, prime=n)
 
 def sieve_itertools(limit):
     return list(takewhile(lambda x: x <= limit, _sieve_itertools())), _loops
@@ -70,17 +75,19 @@ def is_multiple(x):
 
     return sorted(candidates), loops
 
-limit = 9999
-
-sieves = (
-    sieve_brevity_ad_absurdum,
-    sieve_absurder_brevity,
-    sieve_itertools,
-    sieve_tersified,
-)
-for sieve in sieves:
-    start = time.time()
-    primes, loops = sieve(limit)
-    end = time.time()
-    print('{:>27} {:4d} loops, {:.4f}s, {} primes: {}'.format(
-        sieve.__name__, loops, end - start, len(primes), str(primes)[-50:]))
+
+if __name__ == '__main__':
+    limit = 999
+
+    sieves = (
+        sieve_brevity_ad_absurdum,
+        sieve_absurder_brevity,
+        sieve_itertools,
+        sieve_tersified,
+    )
+    for sieve in sieves:
+        start = time.time()
+        primes, loops = sieve(limit)
+        end = time.time()
+        print('{:>27} {:4d} loops, {:.4f}s, {} primes: {}'.format(
+            sieve.__name__, loops, end - start, len(primes), str(primes)[-50:]))
diff --git a/sieve.py b/sieve.py
@@ -1,14 +1,15 @@
-from itertools import islice, tee, count
+from itertools import count, ifilter, takewhile
 from math import sqrt
+import time
 
 
 def sieve_brevity_ad_absurdum(limit):
     candidates = set(range(2, limit + 1))
 
     loops = 0
-    for i in candidates:
+    for n in candidates:
         loops += 1
-        sieved = set(filter(lambda x: not x % i, candidates - {i}))
+        sieved = set(filter(lambda x: not x % n, candidates - {n}))
         # create new candidates object, for loop continues over the original
         candidates = candidates - sieved
 
@@ -20,62 +21,56 @@ def sieve_absurder_brevity(limit):
     loops = 0
     # make a copy of candidates otherwise changing its size will cause
     # RuntimeError: Set changed size during iteration
-    for i in set(candidates):
+    for n in set(candidates):
         loops += 1
-        candidates &= {i} | set(filter(i.__rmod__, candidates))
+        candidates &= {n} | set(filter(n.__rmod__, candidates))
 
     return sorted(candidates), loops
 
 
-def sieve_itertools(limit):
-    candidates = islice(count(2), limit - 1)
+_loops = 0
+def _sieve_itertools():
+    global _loops
+    candidates = count(2)
 
-    loops = 0
+    _loops = 0
     while True:
-        loops += 1
+        _loops += 1
 
-        # only loop over remaining candidates by grabbing the loopsth element
-        copy, candidates = tee(candidates)
-        try:
-            # i.e. start=loops-1, stop=None
-            i = next(islice(copy, loops - 1, None))
-        except StopIteration:
-            break
+        n = next(candidates)
+        yield n
 
-        def is_multiple(x):
-            return x % i == 0
+        # the ifilter here needs to be wrapped in a function otherwise it
+        # fails to retain the local variable context when later lazily run
+        def filter_out_multiples(it, n=n):
+            return ifilter(lambda x: x == n or x % n != 0, it)
 
-        # unfortunately this unrolls candidates into memory. If we could leave
-        # candidates as an iterator, we could yield primes forever without
-        # limit, via a stack of iterators that each remove multiples of a
-        # previously found prime.
-        candidates = set(
-            c for c in candidates if c == i or not is_multiple(c)
-        )
+        # compose a stack of iterators that each remove multiples of a prime
+        candidates = filter_out_multiples(candidates, n=n)
 
-    return sorted(candidates), loops
+def sieve_itertools(limit):
+    return list(takewhile(lambda x: x <= limit, _sieve_itertools())), _loops
 
 
 def sieve_tersified(limit):
     candidates = set(range(2, limit + 1))
 
     loops = 0
-    for i in candidates:
+    for n in candidates:
         # the pragmatic way to reduce number of loops :-)
-        if i > sqrt(limit):
+        if n > sqrt(limit):
             continue
         loops += 1
 
         def is_multiple(x):
-            return x % i == 0
+            return x % n == 0
 
-        sieved = set(filter(is_multiple, candidates - {i}))
+        sieved = set(filter(is_multiple, candidates - {n}))
         candidates = candidates - sieved
 
     return sorted(candidates), loops
 
-
-limit = 100
+limit = 9999
 
 sieves = (
     sieve_brevity_ad_absurdum,
@@ -84,5 +79,8 @@ def is_multiple(x):
     sieve_tersified,
 )
 for sieve in sieves:
+    start = time.time()
     primes, loops = sieve(limit)
-    print('{:>27} {:3d} loops {}'.format(sieve.__name__, loops, primes))
+    end = time.time()
+    print('{:>27} {:4d} loops, {:.4f}s, {} primes: {}'.format(
+        sieve.__name__, loops, end - start, len(primes), str(primes)[-50:]))
diff --git a/sieve.py b/sieve.py
@@ -1,11 +1,88 @@
-def sieve(limit):
+from itertools import islice, tee, count
+from math import sqrt
+
+
+def sieve_brevity_ad_absurdum(limit):
     candidates = set(range(2, limit + 1))
 
+    loops = 0
     for i in candidates:
+        loops += 1
         sieved = set(filter(lambda x: not x % i, candidates - {i}))
+        # create new candidates object, for loop continues over the original
         candidates = candidates - sieved
 
-    return sorted(candidates)
-
-
-print(sieve(997))
+    return sorted(candidates), loops
+
+def sieve_absurder_brevity(limit):
+    candidates = set(range(2, limit + 1))
+
+    loops = 0
+    # make a copy of candidates otherwise changing its size will cause
+    # RuntimeError: Set changed size during iteration
+    for i in set(candidates):
+        loops += 1
+        candidates &= {i} | set(filter(i.__rmod__, candidates))
+
+    return sorted(candidates), loops
+
+
+def sieve_itertools(limit):
+    candidates = islice(count(2), limit - 1)
+
+    loops = 0
+    while True:
+        loops += 1
+
+        # only loop over remaining candidates by grabbing the loopsth element
+        copy, candidates = tee(candidates)
+        try:
+            # i.e. start=loops-1, stop=None
+            i = next(islice(copy, loops - 1, None))
+        except StopIteration:
+            break
+
+        def is_multiple(x):
+            return x % i == 0
+
+        # unfortunately this unrolls candidates into memory. If we could leave
+        # candidates as an iterator, we could yield primes forever without
+        # limit, via a stack of iterators that each remove multiples of a
+        # previously found prime.
+        candidates = set(
+            c for c in candidates if c == i or not is_multiple(c)
+        )
+
+    return sorted(candidates), loops
+
+
+def sieve_tersified(limit):
+    candidates = set(range(2, limit + 1))
+
+    loops = 0
+    for i in candidates:
+        # the pragmatic way to reduce number of loops :-)
+        if i > sqrt(limit):
+            continue
+        loops += 1
+
+        def is_multiple(x):
+            return x % i == 0
+
+        sieved = set(filter(is_multiple, candidates - {i}))
+        candidates = candidates - sieved
+
+    return sorted(candidates), loops
+
+
+limit = 100
+
+sieves = (
+    sieve_brevity_ad_absurdum,
+    sieve_absurder_brevity,
+    sieve_itertools,
+    sieve_tersified,
+)
+for sieve in sieves:
+    primes, loops = sieve(limit)
+    print('{:>27} {:3d} loops {}'.format(sieve.__name__, loops, primes))
diff --git a/sieve.py b/sieve.py
@@ -0,0 +1,11 @@
+def sieve(limit):
+    candidates = set(range(2, limit + 1))
+
+    for i in candidates:
+        sieved = set(filter(lambda x: not x % i, candidates - {i}))
+        candidates = candidates - sieved
+
+    return sorted(candidates)
+
+
+print(sieve(997))
No results found