Re: [Tutor] primes - sieve of odds
On Mar 24, 2005, at 6:01 AM, C Smith [EMAIL PROTECTED] wrote: What follows is an attempt based on the previous tutor-evolved sieve that extends the range in which to find the next prime by a factor of 2 over the last known prime. A similar algorithm is on ASPN (I bellieve), under Space-efficient version of sieve of Eratosthenes. D. Eppstein, May 2004 Oh, please...ignore what I suggested and look at Eppstein's code. It's a thing of beauty and just keeps chugging out primes well past what the inefficient version that I suggested could do with the same memory. It's a tortoise and hare race as the memory gets chewed up by the esieve approach. The ASPN version of Eppstein's program is an older one than the one at the following site: http://www.ics.uci.edu/~eppstein/PADS/Eratosthenes.py How does one actually use this module? For example: import eratosthenes eratosthenes.primes() generator object at 0x640d0 eratosthenes.primes().next() 2 eratosthenes.primes().next() 2 eratosthenes.primes().next() 2 How does one get beyond the first prime? Thanks, John ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes - sieve of odds
John Miller wrote: How does one actually use this module? For example: import eratosthenes eratosthenes.primes() generator object at 0x640d0 eratosthenes.primes().next() 2 eratosthenes.primes().next() 2 eratosthenes.primes().next() 2 How does one get beyond the first prime? it = eratosthenes.primes() it.next() it.next() or # 'it' is shorthand for iterator def primesToN(n): it = eratosthenes.primes() return [ x for x in it if x = n ] You were running into problems because the primes() function returns a new generator. The values are in the generator not the function primes(). ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes - sieve of odds
On Wednesday, Mar 23, 2005, at 04:00 America/Chicago, [EMAIL PROTECTED] wrote: Now it would be fine to have an *equally fast* infinite prime number generator. Has anybody any suggestions? I think when you add the condition of it being an infinite generator, you are changing the rules and can't end up with something as fast. What makes the sieve so fast is that we are generating all the primes in a given range using a very simple strike out method. In the infinite generator scenario, you will get all the primes up to n with the sieve and can yield those back, but at some point you will have to stop and get the next one. To get the next one you will have to pick a range in which a next prime is likely to be found. The previous primes can be used to clear out this range. What follows is an attempt based on the previous tutor-evolved sieve that extends the range in which to find the next prime by a factor of 2 over the last known prime. A similar algorithm is on ASPN (I bellieve), under Space-efficient version of sieve of Eratosthenes. D. Eppstein, May 2004 It's slower than the sieve but about twice as fast as Eppstein's up to 1,000,000. I'll leave it to someone else to see when it finally blows up :-) The output of primes was checked through 1,000,000 against Eppstein's generator without error. /c ### def esieve(): '''extended sieve generator that returns primes on each call. When the end of the existing list is reached, more primes are sought in the range that extends to twice the last known prime. The known primes are used to clear out this extended range using the Sieve of Eratosthenes.''' # get started with primes less than 100; you need at least [2, 3] primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] i=0 while 1: yield primes[i] i+=1 if i==len(primes): #extend range minn=primes[-1]+2 #this is an odd number maxx=2*minn+1 #there should be a prime in this range; +1 makes it odd sqrt=int(maxx**.5) #don't use primes bigger than this length = (maxx-minn)//2 #this is used for computing the crossing out None values nums=range(minn,maxx+1,2) #here is the range in which a primes will be found for p in primes: if psqrt:break j=minn%p #find out where the striking out should start if j0: j=(p-j) #if evens were present, this is where to start, but... if (minn+j)%2==0:j+=p #if it lands on an even, go to the next one j//=2 #and now account for the fact that evens aren't present nums[j::p]=[None]*(1+(length-j)//p) #cross out multiples of p x=filter(None,nums) #clean up the range assert len(x)0 #there should be a prime in here, but check anyway primes.extend(x) #add these to the existing primes and continue yielding ### ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes - sieve of odds
Hi Gregor, I had done the same thing. I also noted that assigning (or inserting) an element into a list is faster than creating a new list: l.insert(0,2) is faster than l = [2]+l. ### def sieve (maximum): if maximum 2: return [] limit = int(maximum**0.5) nums = range(1,maximum+1,2) nums[0] = None for p in nums: if p: if p limit: break nums[(p*p)//2::p] = [False]*(1+(maximum//p- p)//2) nums[0] = 2 return filter(None, nums) ### /c Hi Sean! Thanks for your measurements. In the meantime I did another amendment, leaving out the even numbers from the sieve. It goes like this: def sieve(maximum): nums = range(3, maximum+1, 2) for p in nums: if p: if p*p maximum: break start = (p*p-2)//2 nums[start::p] = [False]*(1+((maximum-3)//2-start)//p) return [2] + filter(None, nums) Perhaps not very elegant. But approximately twice as fast as the former version. ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes (generator)
Karl Pflästerer schrieb: On 19 Mrz 2005, [EMAIL PROTECTED] wrote: [Code] Maybe sombody likes... I did it ... : def sieve (max): max = max + 1 border = round(max**0.5) nums = range(0, max) nums[0] = nums[1] = None for p in nums: if p: if p = border: break for i in xrange(p+p, max, p): nums[i] = None return filter(None, nums) Hi Karl! The following variation of your sieve, using extended slice assignment seems to be sgnificantly faster. Try it out, if you like. def sieve (maximum): limit = int(maximum**0.5) nums = range(maximum+1) nums[0] = nums[1] = None for p in nums: if p: if p limit: break nums[p*p:maximum+1:p] = [False]*(1-p+maximum//p) return filter(None, nums) Regards Gregor Karl ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes (generator)
Gregor Lingl wrote: The following variation of your sieve, using extended slice assignment seems to be sgnificantly faster. Try it out, if you like. Here are the numbers: Primes 1 - 1,000,000 timing: extendedSliceSieve: 0.708388 seconds listPrimes: 0.998758 seconds karlSieve: 1.703553 seconds primeConciseOptimized: 5.133922 seconds setSieve: 7.564576 seconds primeConcise: 1644.683214 seconds -- 27 minutes 24 seconds if __name__ == '__main__': # setup timers as a list of tuples (name, timeit instance) results = [] longest = 0 for t in timers: result = t[1].timeit(1) longest = max(longest, len(t[0])) results.append((t[0], result)) results.sort(lambda x, y: cmp(x[1], y[1])) print Primes 1 - 1,000,000 timing: format_str = %%%ds: %%f seconds % longest for i in results: print format_str % i ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes - sieve of odds
Hi Sean! Thanks for your measurements. In the meantime I did another amendment, leaving out the even numbers from the sieve. It goes like this: def sieve(maximum): nums = range(3, maximum+1, 2) for p in nums: if p: if p*p maximum: break start = (p*p-2)//2 nums[start::p] = [False]*(1+((maximum-3)//2-start)//p) return [2] + filter(None, nums) Perhaps not very elegant. But approximately twice as fast as the former version. Best wishes, Gregor Sean Perry schrieb: Gregor Lingl wrote: The following variation of your sieve, using extended slice assignment seems to be sgnificantly faster. Try it out, if you like. Here are the numbers: Primes 1 - 1,000,000 timing: extendedSliceSieve: 0.708388 seconds listPrimes: 0.998758 seconds karlSieve: 1.703553 seconds primeConciseOptimized: 5.133922 seconds setSieve: 7.564576 seconds primeConcise: 1644.683214 seconds -- 27 minutes 24 seconds if __name__ == '__main__': # setup timers as a list of tuples (name, timeit instance) results = [] longest = 0 for t in timers: result = t[1].timeit(1) longest = max(longest, len(t[0])) results.append((t[0], result)) results.sort(lambda x, y: cmp(x[1], y[1])) print Primes 1 - 1,000,000 timing: format_str = %%%ds: %%f seconds % longest for i in results: print format_str % i ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor -- Gregor Lingl Reisnerstrasse 3/19 A-1030 Wien Telefon: +43 1 713 33 98 Mobil: +43 664 140 35 27 Autor von Python für Kids Website: python4kids.net ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes (generator)
On 19 Mrz 2005, [EMAIL PROTECTED] wrote: [Code] Maybe sombody likes to compare these algorithms to the ones mentioned before in this thread. I would be interested in the results. I did it and on my machine here (a slow one) the following straight forward version is the fastest one. It's no iterator and since all the numbers are stored in a list you need place proportional the number of entries but it's fast and it works nearly the same way the original sieve of Erasthosthens algorithm works. Here it is no error to modify the list which gets iterated over. def sieve (max): max = max + 1 border = round(max**0.5) nums = range(0, max) nums[0] = nums[1] = None for p in nums: if p: if p = border: break for i in xrange(p+p, max, p): nums[i] = None return filter(None, nums) Karl -- Please do *not* send copies of replies to me. I read the list ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
On Mar 18, 2005, at 02:15, Kent Johnson wrote: Max Noel wrote: #!/usr/bin/env python import math import timeit def primeConcise(limit): return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,x,2) if x%y==0]] def primeConciseOptimized(limit): return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,int(math.sqrt(x)), 2) if x%y==0]] Hmm, I didn't know that 9 and 15 were prime... When I'm doing timings like this I usually check the output. You can write a *very* fast algorithm if correctness does not count :-) Damn. Got bitten again by the fact that range/xrange return start = n end and not start = n = end. Python lacks Ruby's range objects ( (start..end) or (start...end) depending on what you want). In the (pythonized) words of E. Dijkstra, if it doesn't have to work, pass is a good solution. I blame sleep deprivation. -.- Note I don't bother testing for divisibility by 2 since the candidates are all odd. This allows using xrange() instead of range() for a significant improvement. My times: listPrimes 0.143752069048 primeConciseOptimized 0.586845814203 primeConciseOptimized2 0.391731351331 Kent Mmh... Good one. Didn't think of it. What can I say... I love stupid optimization challenges. Now I wonder if someone is going to dare come up and kick our asses with a version that does this with a C module... :D -- Max maxnoel_fr at yahoo dot fr -- ICQ #85274019 Look at you hacker... A pathetic creature of meat and bone, panting and sweating as you run through my corridors... How can you challenge a perfect, immortal machine? ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
Gregor Lingl a écrit : Hi! Who knows a more concise or equally concise but more efficient expression, which returns the same result as [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]] Gregor P.S.: ... or a more beautiful one ;-) ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor The fastest know way for your problem is the Eratosten sieve ... Here's an implementation : from sets import Set from math import sqrt def sieve( max ): max_val = int( sqrt( max ) ) s = Set(xrange( 4, max, 2 )) for i in xrange( 3, max_val, 2 ): s.update( xrange( 2*i, max, i ) ) return [ i for i in xrange( 2, max ) if i not in s ] I compared with the implementations of Gregor (optimized) and Max and here is the result : listPrimes(10)= 0.637619972229 (Max implementation) primeConciseOptimized(10) = 2.9141831398 (Gregor optimized) sieve(10) = 0.49525809288 (Eratosten sieve) You'll just notice that Eratosten sieve is O(n) space consumption when others are less (I don't remember the density of prime numbers :o) ) were n is the maximum number you're looking for. Pierre -- Pierre Barbier de Reuille INRA - UMR Cirad/Inra/Cnrs/Univ.MontpellierII AMAP Botanique et Bio-informatique de l'Architecture des Plantes TA40/PSII, Boulevard de la Lironde 34398 MONTPELLIER CEDEX 5, France tel : (33) 4 67 61 65 77fax : (33) 4 67 61 56 68 ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes (generator)
Hi all of you! Many thanks for your remarks, ideas and experiments. When I posted my input yesterday: [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]] my intention was indeed to find a shortest a program, disregarding efficiency. Thus range instead of xrange etc. (About one year ago I was involved in a coding contest at Linux-Tag in Karlsruhe, where the goal was to achive a certain output with a shortest program ;-) Strange. I used Python, but I didn't win :-( ) Clearly there are several criteria concerning the quality of programs as e. g. conciseness, clarity, efficiency, beauty(!) etc. which may not be achieved optimally all together ... I definitely intend to sum up your contibutions (for me) later, but for now (because of lack of time) I'll only present one more idea, induced by Danny's (unfortunately buggy - because of recursion overflow) contribution: Thought it would be nice to use Python's new generator-expressions instead of itertool module. First idea: ## # infinite prime generator # induced by ideas of Danny Yoo, # which themselves were induced by material of SICP import math def prime(n): return [x for x in range(2,1+int(math.sqrt(n))) if n%x==0]==[] def infrange(n): while True: yield n n+=1 primes = (p for p in infrange(2) if prime(p)) ### The generator primes works like this: primes.next() 2 primes.next() 3 primes.next() 5 [primes.next() for i in range(10)] [7, 11, 13, 17, 19, 23, 29, 31, 37, 41] [primes.next() for i in range(100)] [43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617] ### You may also use it this way: for p in primes: if p 1000: break print p, 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 With a fresh generator [primes.next() for p in xrange(1)] produces (on my machine) a list of the first 1 primes (upto 104729) within 4.68 secs. Now for a bit of optimization: instead of building a list of all divisors use a loop and get out as soon as possible: So I replace prime by: def prime(n): for d in range(2,1+int(math.sqrt(n))): if n%d == 0: return False return True This makes the generator nearly 4 times as fast. I get my list in 1.33 secs. Lets optimize a bit more: test only 2 and odd numbers: def infrange(n): yield 2 n=3 while True: yield n n+=2 and do a similar thing for searching for divisors: def prime(n): if n==2: return True for d in [2]+ range(3,1+int(math.sqrt(n)),2): if n%d == 0: return False return True Now the first 1 primes get computed in 0.67 secs. Again double speed. Together seven times as fast as first version. But IMO at the cost of clarity and conciseness. Maybe you have amendments (of course a matter of taste) to this code. I'd be interested in them .. Maybe sombody likes to compare these algorithms to the ones mentioned before in this thread. I would be interested in the results. Regards, Gregor Danny Yoo schrieb: On Thu, 17 Mar 2005, Gregor Lingl wrote: Hi! Who knows a more concise or equally concise but more efficient expression, which returns the same result as ... ## from itertools import ifilter, count def notDivisibleBy(n): ... def f(x): ... return x % n != 0 ... return f ... def sieve(iterable): ... nextPrime = iterable.next() ... yield nextPrime ... restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable)) ... for prime in restOfPrimes: ... yield prime ... primes = sieve(count(2)) primes.next() 2 primes.next() ... primes.next() 23 ## The neat thing about this code is that it produces an infinite iterator of prime numbers. The original code in Scheme is itself quite concise and quite nice. It is described here: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#call_footnote_Temp_455 Best of wishes to you! -- Gregor Lingl Reisnerstrasse 3/19 A-1030 Wien Telefon: +43 1 713 33 98 Mobil: +43 664 140 35 27 Autor von Python für Kids Website: python4kids.net ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes (Cautious remark on Python and Scheme)
Hi Danny! Preliminary remark: I know that beautiful and beauty are concepts very seldom applied to computer programs or programming languages. I suppose mainly because they are to a large extent a matter of taste ... Nevertheless: regardeless of the fact that I'm not a very skilled scheme-programmer, for me Scheme is the most beautiful programming language I know, mainly because of the clear and simple concepts which are purely realized. (I do *not* want to discuss here questions like functional versus object-oriented languages etc...) However - Python - for me - is a programming language for the pragmatic lover. Do you consider this expression as self explanatory? Lover -- because it makes so much fun to use it. Pragmatic -- because it is a language for the real world ;-) im*h*o the primes - examples we are just discussing shows, that going *the Python way* may well be more successful or rewarding than trying to translate, traduce, ...er .. adapt Scheme-concepts quasi trying to show that Python is at least as good as Scheme. This is not the question. (I suppose that this also was not your goal?) A deeper question perhaps would be to what degree the content of cs texts depends on the choice of the mainly used language therein. On the contrary - we may learn from this example that Python is a *very* good language in its own right - with carefully chosen concepts and syntax and a very slow, serious and publicly controlled development process resulting in a more and more easily and efficiently usable language. Finally I'd like to stress that your contribution for me was very valuable and constructive - as are most of your innumerable contributions to the discussions on this list. Thanks an regards, Gregor post scriptum: as always when writing not only about technical facts but about opinions and values in English, I'm a bit axious if I was able to express correctly what I wanted to say. Hmmm. Hope that I didn't create any misunderstandings Danny Yoo schrieb: On Thu, 17 Mar 2005, Gregor Lingl wrote: Hi! Who knows a more concise or equally concise but more efficient expression, which returns the same result as [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]] Hi Gregor, Here is one that's traduced... er... adapted from material from the classic textbook Structure and Interpretation of Computer Programs: ## from itertools import ifilter, count def notDivisibleBy(n): ... def f(x): ... return x % n != 0 ... return f ... def sieve(iterable): ... nextPrime = iterable.next() ... yield nextPrime ... restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable)) ... for prime in restOfPrimes: ... yield prime ... primes = sieve(count(2)) primes.next() 2 primes.next() 3 primes.next() 5 primes.next() 7 primes.next() 11 primes.next() 13 primes.next() 17 primes.next() 19 primes.next() 23 ## The neat thing about this code is that it produces an infinite iterator of prime numbers. The original code in Scheme is itself quite concise and quite nice. It is described here: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#call_footnote_Temp_455 Best of wishes to you! -- Gregor Lingl Reisnerstrasse 3/19 A-1030 Wien Telefon: +43 1 713 33 98 Mobil: +43 664 140 35 27 Autor von Python für Kids Website: python4kids.net ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes (Cautious remark on Python and Scheme)
Concerning my previous posting - perhaps it would suffice to summarize: While Python is a language for the pragmatic lover, Scheme is much more fundamentalistic. (thought-) *PROVOKING*? Gregor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
[OT] Re: [Tutor] primes (Cautious remark on Python and Scheme)
Gregor Lingl said unto the world upon 2005-03-18 19:57: Hi Danny! Preliminary remark: I know that beautiful and beauty are concepts very seldom applied to computer programs or programming languages. I suppose mainly because they are to a large extent a matter of taste ... Hi Gregor and all, Though I've not had the time to follow the details of the thread closely, it's stored for future perusal -- I'm really glad you started it, Gregor. But, your comment above caught my eye. import this to see that beauty is embraced by the zen :-) It's been a long day, so I don't feel I am saying this well, but: When not trying to learn Python, I'm a (grad student) philosopher of logic and mathematics. I've thought some about beauty in proof, and hope to think seriously about it one day. Beauty in maths is like what the judge said about pornography -- I can't define it, but I know it when I see it. I've never met a philosopher or a mathematician who could give a compelling (and robust) account of what makes for beauty, but there is widespread convergence of judgements about which proofs are beautiful and which ugly. (This even though taste does enter into it, too.) I think the same is true of (at least academic) computer science. The comp sci people I know at my uni all work in automated-theorem proving, and I know they use their perceptions of beauty as a design guide. And, with my much more limited experience with programming, my judgements that this code is ugly have been pretty reliable in identifying the problematic parts. If it is beautiful, it might be right. If it is ugly, it is likely wrong seems a safe claim. Anyway, all this is to say that I think that what you know above is wrong :-) SNIP post scriptum: as always when writing not only about technical facts but about opinions and values in English, I'm a bit axious if I was able to express correctly what I wanted to say. Hmmm. Hope that I didn't create any misunderstandings Ich kann Deutsch, aber nur ein bischen. I think I'd be a very happy fellow if my German were half as good as your English :-) Best to all, Brian vdB ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
[Tutor] primes
Hi! Who knows a more concise or equally concise but more efficient expression, which returns the same result as [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]] Gregor P.S.: ... or a more beautiful one ;-) ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
On Mar 17, 2005, at 22:28, Gregor Lingl wrote: Hi! Who knows a more concise or equally concise but more efficient expression, which returns the same result as [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]] Gregor P.S.: ... or a more beautiful one ;-) Hmm... I don't have beautiful or concise, but I can offer fast. Here goes: #!/usr/bin/env python import math def isPrime(x, primeList): limit = math.sqrt(x) for i in primeList: if x % i == 0: return False if i = limit: break return True def listPrimes(upperLimit): listOfPrimes = [] for i in range(2, upperLimit): if isPrime(i, listOfPrimes): listOfPrimes.append(i) return listOfPrimes if __name__ == '__main__': import sys num = int(sys.argv[-1]) print listPrimes(num) That's the fastest way I can think of -- but I can't prove it, as I don't know how to use the timeit module. -- Max maxnoel_fr at yahoo dot fr -- ICQ #85274019 Look at you hacker... A pathetic creature of meat and bone, panting and sweating as you run through my corridors... How can you challenge a perfect, immortal machine? ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
Quoting Gregor Lingl [EMAIL PROTECTED]: [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]] Heh. That's quite neat. I can only offer one suggestion --- if you replace range with xrange, you get a small speed improvement. eg: On my system, it took 415 seconds to generate a list of primes 50,000 using range, but only 386 seconds if I use the same code, but with xrange instead. -- John. ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
On Thu, 17 Mar 2005, Gregor Lingl wrote: Hi! Who knows a more concise or equally concise but more efficient expression, which returns the same result as [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]] Hi Gregor, Here is one that's traduced... er... adapted from material from the classic textbook Structure and Interpretation of Computer Programs: ## from itertools import ifilter, count def notDivisibleBy(n): ... def f(x): ... return x % n != 0 ... return f ... def sieve(iterable): ... nextPrime = iterable.next() ... yield nextPrime ... restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable)) ... for prime in restOfPrimes: ... yield prime ... primes = sieve(count(2)) primes.next() 2 primes.next() 3 primes.next() 5 primes.next() 7 primes.next() 11 primes.next() 13 primes.next() 17 primes.next() 19 primes.next() 23 ## The neat thing about this code is that it produces an infinite iterator of prime numbers. The original code in Scheme is itself quite concise and quite nice. It is described here: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#call_footnote_Temp_455 Best of wishes to you! ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
On Mar 17, 2005, at 23:54, Danny Yoo wrote: Hi Gregor, Here is one that's traduced... er... adapted from material from the classic textbook Structure and Interpretation of Computer Programs: SNIP Ooh, nifty. Okay, I decided to learn how to use the timeit module, so I used it to compare my algorithm (which, I just noticed, is a Python implementation of the Sieve of Erastothenes) to the one Gregor originally posted (albeit slightly optimized -- the only even prime number is 2, so there's no need to test them), and a further optimized version of it (stops looping at sqrt(x)). While I was at it, I optimized my algorithm further (in both memory usage and speed): it uses xrange and doesn't bother testing even numbers. Now, I did expect my algorithm to be the fastest. What I didn't expect, though, was for the differences to be *that* massive. Letting all three functions loose on finding all the prime numbers from 2 to 5, I got the following results (test machine: G4 867 running Python 2.3 on OS X 10.3.8): listPrimes: 0.508284091949 seconds # my algorithm primeConciseOptimized: 2.18135714531 seconds# Gregor's, optimized primeConcise: 399.251116991 seconds # Gregor's, (partially optimized) As I suspected, when increasing the range, so do the differences. listPrimes finds all prime numbers from 2 to 20 in 2.55 seconds, primeConciseOptimized in 15.81. At that point I had dropped primeConcise, as it being O(n^3) as far as I can tell, it would have taken ages to run. However, I thought the difference between listPrimes and primeConciseOptimized would increase faster than that. So primeConciseOptimized seems like the best compromise between speed and conciseness. Here's the (final?) version of the script I used: #!/usr/bin/env python import math import timeit def primeConcise(limit): return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,x,2) if x%y==0]] def primeConciseOptimized(limit): return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,int(math.sqrt(x)), 2) if x%y==0]] def isPrime(x, primeList): limit = int(math.sqrt(x)) for i in primeList: if x % i == 0: return False if i = limit: break return True def listPrimes(upperLimit): listOfPrimes = [2] for i in xrange(3, upperLimit, 2): if isPrime(i, listOfPrimes): listOfPrimes.append(i) return listOfPrimes if __name__ == '__main__': t1 = timeit.Timer('listPrimes(5)', 'from __main__ import listPrimes') t2 = timeit.Timer('primeConciseOptimized(5)', 'from __main__ import primeConciseOptimized') t3 = timeit.Timer('primeConcise(5)', 'from __main__ import primeConcise') print t1.timeit(1) print t2.timeit(1) print t3.timeit(1) -- Max maxnoel_fr at yahoo dot fr -- ICQ #85274019 Look at you hacker... A pathetic creature of meat and bone, panting and sweating as you run through my corridors... How can you challenge a perfect, immortal machine? ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
Max Noel wrote: #!/usr/bin/env python import math import timeit def primeConcise(limit): return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,x,2) if x%y==0]] def primeConciseOptimized(limit): return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,int(math.sqrt(x)), 2) if x%y==0]] Hmm, I didn't know that 9 and 15 were prime... When I'm doing timings like this I usually check the output. You can write a *very* fast algorithm if correctness does not count :-) Here is a version that gives correct results at least up to limit=50: def primeConciseOptimized(limit): return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,int(math.sqrt(x))+1, 2) if x%y==0]] One reason your listPrimes() function is faster is that it short-circuits the test - as soon as a divisor is found for a candidate, no further testing is done. primeConciseOptimized() always tests all the candidate divisors. In the spirit of useless optimizations of bad algorithms ;) I used itertools to make a short-circuiting version of primeConciseOptimized(): import itertools def no(seq, pred=bool): '''Returns True if pred(x) is False for every element in the iterable From the itertools recipes. ''' for elem in itertools.ifilter(pred, seq): return False return True def primeConciseOptimized2(limit): return [2] + [x for x in xrange(3, limit, 2) if no(xrange(3,int(math.sqrt(x))+1, 2), lambda y: x%y==0)] Note I don't bother testing for divisibility by 2 since the candidates are all odd. This allows using xrange() instead of range() for a significant improvement. My times: listPrimes 0.143752069048 primeConciseOptimized 0.586845814203 primeConciseOptimized2 0.391731351331 Kent def isPrime(x, primeList): limit = int(math.sqrt(x)) for i in primeList: if x % i == 0: return False if i = limit: break return True def listPrimes(upperLimit): listOfPrimes = [2] for i in xrange(3, upperLimit, 2): if isPrime(i, listOfPrimes): listOfPrimes.append(i) return listOfPrimes if __name__ == '__main__': t1 = timeit.Timer('listPrimes(5)', 'from __main__ import listPrimes') t2 = timeit.Timer('primeConciseOptimized(5)', 'from __main__ import primeConciseOptimized') t3 = timeit.Timer('primeConcise(5)', 'from __main__ import primeConcise') print t1.timeit(1) print t2.timeit(1) print t3.timeit(1) -- Max maxnoel_fr at yahoo dot fr -- ICQ #85274019 Look at you hacker... A pathetic creature of meat and bone, panting and sweating as you run through my corridors... How can you challenge a perfect, immortal machine? ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
On Thursday, Mar 17, 2005, at 17:49 America/Chicago, [EMAIL PROTECTED] wrote: On my system, it took 415 seconds to generate a list of primes 50,000 using range, but only 386 seconds if I use the same code, but with xrange instead. If you only calculate y up to sqrt(x) you will see a dramatic time reduction: ### import math big=5 [x for x in xrange(2,big) if not [y for y in range(2,int(math.sqrt(x)+1)) if x%y==0]] ### /c ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] primes
Danny Yoo wrote: Here is one that's traduced... er... adapted from material from the classic textbook Structure and Interpretation of Computer Programs: ## from itertools import ifilter, count def notDivisibleBy(n): ... def f(x): ... return x % n != 0 ... return f ... def sieve(iterable): ... nextPrime = iterable.next() ... yield nextPrime ... restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable)) ... for prime in restOfPrimes: ... yield prime ... primes = sieve(count(2)) primes.next() which is cool, until you try to use it (-: It dies at 999 primes due to an overloaded stack. Bummer. It is such a nifty implementation. I modified this version to follow it better. from itertools import ifilter, count def notDivisibleBy(n): def f(x): return x % n != 0 return f def sieve(iterable): nextPrime = iterable.next() print 'x', nextPrime yield nextPrime restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable)) for prime in restOfPrimes: print 'p', prime yield prime primes = sieve(count(2)) current = primes.next() count = 1 while current = 20: print 'Prime:', current current = primes.next() count += 1 The output is (note this is each prime 20): x 2 Prime: 2 x 3 p 3 Prime: 3 x 5 p 5 p 5 Prime: 5 x 7 p 7 p 7 p 7 Prime: 7 x 11 p 11 p 11 p 11 p 11 Prime: 11 x 13 p 13 p 13 p 13 p 13 p 13 Prime: 13 x 17 p 17 p 17 p 17 p 17 p 17 p 17 Prime: 17 x 19 p 19 p 19 p 19 p 19 p 19 p 19 p 19 Prime: 19 x 23 p 23 p 23 p 23 p 23 p 23 p 23 p 23 p 23 Not exactly efficient. ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor