Page 1 of 1
Python Boolean Array
Posted: Sun Oct 26, 2008 12:52 am
by stalepretzel
I'd like to make a prime sieve in python. It should be fairly large, from 0 to 10**8. The first step, was this:
Code: Select all
primes=[];
n = 0;
while n <= 10**8:
primes.append(False);
n+=1;
However, it took over 3 minutes just to complete that! Is there any way I can do this more efficiently?
Thanks,
Jason
Re: Python Boolean Array
Posted: Sun Oct 26, 2008 1:13 am
by daniel.is.fischer
I don't know if it's really more efficient, but try
Edit: Yep, definitely faster
Re: Python Boolean Array
Posted: Sun Oct 26, 2008 2:49 am
by stalepretzel
On a related note:
When, in Python, I use a for loop, it generates an entire array of numbers, which seriously clogs up my computer. For example:
This will cause my computer to freeze and, most likely, crash.
Is there any way around this, besides using a while loop?
Re: Python Boolean Array
Posted: Sun Oct 26, 2008 3:06 am
by daniel.is.fischer
Use xrange:
Well, don't print 'em all
Re: Python Boolean Array
Posted: Sun Oct 26, 2008 11:15 am
by 3n1gm4
daniel.is.fischer wrote:Use xrange:
Well, don't print 'em all
LOL!
Python is not for heavy math/cpu work. You should some external tool if you want to do it fast, try
gmpy for example
Re: Python Boolean Array
Posted: Mon Nov 03, 2008 3:16 am
by stalepretzel
xrange. Well I feel sheepish. Baaa-a-a-a-a.
Thanks a bunch.
Wait... why, then, would anybody ever use range(a,b) instead of xrange(a,b)?
Re: Python Boolean Array
Posted: Mon Nov 03, 2008 3:07 pm
by quilan
stalepretzel wrote:xrange. Well I feel sheepish. Baaa-a-a-a-a.
Thanks a bunch.
Wait... why, then, would anybody ever use range(a,b) instead of xrange(a,b)?
range() will be replaced by xrange() I believe in future versions.
Re: Python Boolean Array
Posted: Mon Nov 03, 2008 8:30 pm
by 3n1gm4
range() returns a
list, xrange() returns an
iterator.
You can "re-code" range and xrange in python like this:
Code: Select all
def xrange(start, stop, step = 1):
while start<stop:
yield start
start += step
def range(stop, start = 0, step = 1):
return [i for i in xrange(start,stop,step)]
xrange compute each iteration one by one (it yields it after it has calculated it), range compute all iterations then return the list. xrange will use less memory (ram) than range.
Testing it is very easy: run these codes:
Code: Select all
for i in xrange(0,100000000): print '.',
print 'Now with range...'
for i in range(100000000): print '.',
Now, you don't want python to print 100000000 '.'s ... so try them separately, you will see that the xrange version will start immediately to print out points, the range version will not, you'll see (i mean, wait for...) it loading all the 100000000 numbers in memory before to start looping :\
Anyway there are some interesting thing about this on
stackoverflow.