Python 'for' loop is memory inefficient

Ethan Furman ethan at stoneleaf.us
Sat Aug 15 03:43:42 CEST 2009


Dr. Phillip M. Feldman wrote:
> I wrote the following correct but inefficient test of primality for purposes
> of demonstrating that the simplest algorithm is often not the most
> efficient.  But, when I try to run the following code with a value of n that
> is large enough to produce a significant amount of running time, I get an
> out-of-memory error!
> 
> def is_prime(n):
>    for j in range(2,n):
>       if (n % j) == 0: return False
>    return True
> 
> It seems as though Python is actually expanding range(2,n) into a list of
> numbers, even though this is incredibly wasteful of memory. There should be
> a looping mechanism that generates the index variable values incrementally
> as they are needed.

You already have an answer to the range issue, so I will only add that 
putting a loop inside another loop is a decent way to expand the time taken.

I will also observe that if you were to stop programming whatever 
language you are more familiar with in Python, and start programming 
Python in Python, you'll have an easier time of it.

The Dive Into Python is an excellent start for that.

~Ethan~



More information about the Python-list mailing list