Steven Bethard wrote:
> Dustan wrote:
>> On Aug 12, 7:35 pm, Dustan <[EMAIL PROTECTED]> wrote:
>>> On Aug 12, 5:09 pm, Steven Bethard <[EMAIL PROTECTED]> wrote:
>>>
>>>> def iter_primes():
>>>> # an iterator of all numbers between 2 and +infinity
>>>> numbers = itertools.count(2)
>>>> # generate primes forever
>>>> while True:
>>>> # get the first number from the iterator (always a prime)
>>>> prime = numbers.next()
>>>> yield prime
>>>> # remove all numbers from the (infinite) iterator that are
>>>> # divisible by the prime we just generated
>>>> numbers = itertools.ifilter(prime.__rmod__, numbers)
>>> This is kind of OT (from the thread), but in this iter_primes
>>> function, numbers is becoming an ifilter of an ifilter of an ifilter
>>> of an ifilter of an ifilter of an ifilter of... Is that really at all
>>> efficient for larger numbers (millions or billions, or even bigger)?
>>
>> To word my question better:
>>
>> How does this algorithm compare and contrast to maintaining a
>> dictionary or set and iterating through those structures to find out
>> if a number is divisible? All of those algorithms I've described are
>> O(n^2), if I'm not mistaken, but as far as memory-efficiency and the
>> likes, how do they compare/contrast?
>
> I don't have the answer off hand, but if anyone wants to report some
> timeit results or memory consumption here, I'd be interested.
Ok, I played around with it myself. Here are the two implementations I
tested::
def iter_primes_recursive():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)
# generate primes forever
while True:
# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime
# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)
def iter_primes_mapping():
# mapping from composite number to first prime that revealed
# that number as a composite
composite_to_factor_map = {}
# generate primes forever
for i in itertools.count(2):
# find a factor of the number
factor = composite_to_factor_map.pop(i, None)
# if no factor is found, the number is prime
if factor is None:
yield i
composite_to_factor_map[i * i] = i
# add the factor to the number until we find a new
# composite number
else:
composite = i + factor
while composite in composite_to_factor_map:
composite += factor
composite_to_factor_map[composite] = factor
And here are some timeit results::
$ python -m timeit -s "from script import iter_primes_recursive as
iter_primes" "for i in iter_primes():" " if i >= 100:"
" break"
10000 loops, best of 3: 102 usec per loop
$ python -m timeit -s "from script import iter_primes_mapping as
iter_primes" "for i in iter_primes():" " if i >= 100:"
" break"
10000 loops, best of 3: 75.2 usec per loop
$ python -m timeit -s "from script import iter_primes_recursive as
iter_primes" "for i in iter_primes():" " if i >= 10000:"
" break"
10 loops, best of 3: 111 msec per loop
$ python -m timeit -s "from script import iter_primes_mapping as
iter_primes" "for i in iter_primes():" " if i >= 10000:"
" break"
100 loops, best of 3: 8.4 msec per loop
So, somewhat unsurprisingly, the non-recursive version is much faster
for larger primes. (Someone should check that both my implementations
are right -- I only did a couple of spot checks on the output.)
STeVe
--
http://mail.python.org/mailman/listinfo/python-list
