Little novice program written in Python

R

Rogério Brito

Hi, All.

I'm just getting my feet wet on Python and, just for starters, I'm coding some
elementary number theory algorithms (yes, I know that most of them are already
implemented as modules, but this is an exercise in learning the language idioms).

As you can see from the code below, my background is in C, without too much
sophistication.

What I would like is to receive some criticism to my code to make it more
Python'esque and, possibly, use the resources of the computer in a more
efficient way (the algorithm implemented below is the Sieve of Eratosthenes):

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#!/usr/bin/env python

n = int(raw_input())
a = [i for i in range(0,n+1)]
a[1] = 0 # not a prime
prime = 1 # last used prime
finished = False

while (not finished):
prime = prime + 1
# find new prime
while prime*prime <= n and a[prime] == 0:
prime += 1
# cross the composite numbers
if prime*prime <= n:
j = 2*prime
while j <= n:
a[j] = 0
j += prime
else:
finished = True

# print out the prime numbers
i = 2
while i <= n:
if a != 0:
print a
i += 1
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Thank you for any help in improving this program,
 
R

Raymond Hettinger

What I would like is to receive some criticism to my code to make it more
Python'esque and, possibly, use the resources of the computer in a more
efficient way (the algorithm implemented below is the Sieve of Eratosthenes):

It looks like straight-forward code and is fine as it stands.
If you want to tweak it a bit, you can avoid using a flag like
"finished" by using a break-statement.


Raymond
 
S

Steve Holden

Rogério Brito said:
Hi, All.

I'm just getting my feet wet on Python and, just for starters, I'm
coding some elementary number theory algorithms (yes, I know that most
of them are already implemented as modules, but this is an exercise in
learning the language idioms).

As you can see from the code below, my background is in C, without too
much sophistication.

What I would like is to receive some criticism to my code to make it
more Python'esque and, possibly, use the resources of the computer in a
more efficient way (the algorithm implemented below is the Sieve of
Eratosthenes):

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#!/usr/bin/env python

n = int(raw_input())
a = [i for i in range(0,n+1)]
a[1] = 0 # not a prime
prime = 1 # last used prime
finished = False

while (not finished):
prime = prime + 1
# find new prime
while prime*prime <= n and a[prime] == 0:
prime += 1
# cross the composite numbers
if prime*prime <= n:
j = 2*prime
while j <= n:
a[j] = 0
j += prime
else:
finished = True

# print out the prime numbers
i = 2
while i <= n:
if a != 0:
print a
i += 1
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Thank you for any help in improving this program,

Your Python is actually pretty good - if Raymond Hettinger pronounces it
OK then few would dare to disagree.

As for your English, though, the word you sought was "Pythonic" (not
that you will ever find such a word in Webster's dictionary). To suggest
that your code is Pythonesque would mean you found it farcical or
ridiculous (like a Monty Python sketch), which it clearly is not.

Another wrinkle you might consider is simply printing the primes out as
they are generated rather than doing the printing in a separate loop,
though whether that approach would be preferable in "real life" would
depend on the application, of course.

regards
Steve

PS: I think either my mailer or yours has mangled the indentation.
 
C

castironpi

a = [i for i in range(0,n+1)]

        Uhm... At least in 2.4 and earlier, range() returns a list.... No
need for the list-comp in that era... range() also begins with 0


[0, 1, 2, 3, 4, 5]

        So just

        a = range(n+1)

could be used. Of course, if using a version where range() and xrange()
have been unified...
[0, 1, 2, 3, 4, 5]

--
        Wulfraed        Dennis Lee Bieber               KD6MOG
        (e-mail address removed)              (e-mail address removed)
                HTTP://wlfraed.home.netcom.com/
        (Bestiaria Support Staff:               (e-mail address removed))
                HTTP://www.bestiaria.com/

You're talking hardware-native, which machines don't guarantee.
Python can in another dimension of machine compatibility. Stacks are
hardware native, the location of an array is not. Python can retrieve
your stack in higher dimensions.

Fortunately, Python's community is sturdy against counterproductivity
en masse, so it's okay to hairbrain it. Cover features of
improvements, though, and you might get a Bayes Net change to make and
courses to steer. The community values the flexibility of machine-
independency too.

However, real numbers are not integers, so opinion mass of integer
algorithms may favor C. But you just need micro-sales (and scales!)
to examine the future of Python. Welcome to our group.
 
P

Peter Otten

Rogério Brito said:
i = 2
while i <= n:
     if a != 0:
        print a
     i += 1


You can spell this as a for-loop:

for p in a:
if p:
print p

It isn't exactly equivalent, but gives the same output as we know that a[0]
and a[1] are also 0.

Peter
 
R

Robert Bossy

Peter said:
Rogério Brito wrote:

i = 2
while i <= n:
if a != 0:
print a
i += 1


You can spell this as a for-loop:

for p in a:
if p:
print p

It isn't exactly equivalent, but gives the same output as we know that a[0]
and a[1] are also 0.

If the OP insists in not examining a[0] and a[1], this will do exactly
the same as the while version:

for p in a[2:]:
if p:
print p


Cheers,
RB
 
J

John Machin

Peter said:
Rogério Brito wrote:
i = 2
while i <= n:
if a != 0:
print a
i += 1

You can spell this as a for-loop:
for p in a:
if p:
print p
It isn't exactly equivalent, but gives the same output as we know that a[0]
and a[1] are also 0.

If the OP insists in not examining a[0] and a[1], this will do exactly
the same as the while version:

for p in a[2:]:
if p:
print p


... at the cost of almost doubling the amount of memory required.
 
R

Robert Bossy

John said:
Peter said:
Rogério Brito wrote:

i = 2
while i <= n:
if a != 0:
print a
i += 1

You can spell this as a for-loop:

for p in a:
if p:
print p

It isn't exactly equivalent, but gives the same output as we know that a[0]
and a[1] are also 0.

If the OP insists in not examining a[0] and a[1], this will do exactly
the same as the while version:

for p in a[2:]:
if p:
print p


... at the cost of almost doubling the amount of memory required.

Indeed. Would it be a sensible proposal that sequence slices should
return an iterator instead of a list?

RB
 
H

hellt

Rogério Brito:
Hi, All.

I'm just getting my feet wet on Python and, just for starters, I'm coding some
elementary number theory algorithms (yes, I know that most of them are already
implemented as modules, but this is an exercise in learning the language idioms).

As you can see from the code below, my background is in C, without too much
sophistication.

What I would like is to receive some criticism to my code to make it more
Python'esque and, possibly, use the resources of the computer in a more
efficient way (the algorithm implemented below is the Sieve of Eratosthenes):

my variant of the sieve

def GetPrimes(N):
arr = []
for i in range(1,N+1):
arr.append(i)
#Set first item to 0, because 1 is not a prime
arr[0]=0
#sieve processing
s=2
while s < math.sqrt(N):
if arr[s-1] != 0:
j = s*s
while j <= N:
arr[j-1] = 0
j += s
s += 1
return [x for x in arr if x != 0]
 
H

hellt

also, i would recommend you to visit projecteuler.net
you can solve math tasks and then see how others have done the same.

you can fetch very good and pythonic solution there.
 
A

Arnaud Delobelle

hellt said:
my variant of the sieve

Since you posted it, you are also looking for advice to improve your
code ;)
def GetPrimes(N):
arr = []
for i in range(1,N+1):
arr.append(i)
This is the same as:
arr = range(1, N+1)
!-)
#Set first item to 0, because 1 is not a prime
arr[0]=0
#sieve processing
remove this line
while s < math.sqrt(N):
for s in xrange(2, int(math.sqrt(N))+1):
if arr[s-1] != 0:
if arr[s-1]:
remove this line
while j <= N:
for j in xrange(s*s, N+1, s):
arr[j-1] = 0
remove this line
remove this line
return [x for x in arr if x != 0]
return filter(None, arr)


Altogether now:

def getprimes(N):
arr = range(1, N+1)
arr[0] = 0
for s in xrange(2, int(math.sqrt(N))+1):
if arr[s-1]:
for j in xrange(s*s, N+1, s):
arr[j-1] = 0
return filter(None, arr)

It's the same, but it looks a bit less like the litteral translation
of some C code.


Lastly, the lines:

for j in xrange(s*s, N+1, s):
arr[j-1] = 0

from above can be condensed using extended slices:

arr[s*s-1 : N+1 : s] = [0] * (N/s - s + 1)

(If I can count correctly)

Giving the following, slightly shorter and probably faster:

def getprimes(N):
arr = range(1, N+1)
arr[0] = 0
for s in xrange(2, int(math.sqrt(N))+1):
if arr[s-1]:
arr[s*s-1 : N+1 : s] = [0] * (N/s - s + 1)
return filter(None, arr)


If it was me, I would include 0 in the array, giving the slightly simpler:

def getprimes(N):
arr = range(N+1)
arr[1] = 0
for s in xrange(2, int(math.sqrt(N))+1):
if arr:
arr[s*s : N+1 : s] = [0] * (N/s - s + 1)
return filter(None, arr)

(I think)

This all needs to be tested.
 
H

hellt

hellt said:
my variant of the sieve

Since you posted it, you are also looking for advice to improve your
code ;)
def GetPrimes(N):
arr = []
for i in range(1,N+1):
arr.append(i)

This is the same as:
arr = range(1, N+1)
!-)
#Set first item to 0, because 1 is not a prime
arr[0]=0
#sieve processing
s=2

remove this line
while s < math.sqrt(N):

for s in xrange(2, int(math.sqrt(N))+1):
if arr[s-1] != 0:

if arr[s-1]:

remove this line
while j <= N:

for j in xrange(s*s, N+1, s):
arr[j-1] = 0
j += s

remove this line

remove this line
return [x for x in arr if x != 0]

return filter(None, arr)

Altogether now:

def getprimes(N):
arr = range(1, N+1)
arr[0] = 0
for s in xrange(2, int(math.sqrt(N))+1):
if arr[s-1]:
for j in xrange(s*s, N+1, s):
arr[j-1] = 0
return filter(None, arr)

It's the same, but it looks a bit less like the litteral translation
of some C code.

Lastly, the lines:

for j in xrange(s*s, N+1, s):
arr[j-1] = 0

from above can be condensed using extended slices:

arr[s*s-1 : N+1 : s] = [0] * (N/s - s + 1)

(If I can count correctly)

Giving the following, slightly shorter and probably faster:

def getprimes(N):
arr = range(1, N+1)
arr[0] = 0
for s in xrange(2, int(math.sqrt(N))+1):
if arr[s-1]:
arr[s*s-1 : N+1 : s] = [0] * (N/s - s + 1)
return filter(None, arr)

If it was me, I would include 0 in the array, giving the slightly simpler:

def getprimes(N):
arr = range(N+1)
arr[1] = 0
for s in xrange(2, int(math.sqrt(N))+1):
if arr:
arr[s*s : N+1 : s] = [0] * (N/s - s + 1)
return filter(None, arr)

(I think)

This all needs to be tested.


nice, but i'm a newbie to python too, so some things for me seems a
liitle complicated)))
 
M

Marc 'BlackJack' Rintsch

John said:
Peter Otten wrote:
If the OP insists in not examining a[0] and a[1], this will do exactly
the same as the while version:

for p in a[2:]:
if p:
print p

... at the cost of almost doubling the amount of memory required.
Indeed. Would it be a sensible proposal that sequence slices should
return an iterator instead of a list?

I don't think so as that would break tons of code that relies on the
current behavior. Take a look at `itertools.islice()` if you want/need
an iterator.

Ciao,
Marc 'BlackJack' Rintsch
 
M

Max M

Rogério Brito skrev:
Hi, All.

What I would like is to receive some criticism to my code to make it
more Python'esque and, possibly, use the resources of the computer in a
more efficient way (the algorithm implemented below is the Sieve of
Eratosthenes):


I agree with the rest here. Your code generally looks fine.

But on another note, this type of code is not something you often see in
Python. It is very dense with regard to algorithm.

Most code is not like that so perhaps you should try something more
"usual" like sending email, fetching webpages etc. to get a feel for the
language.


--

hilsen/regards Max M, Denmark

http://www.mxm.dk/
IT's Mad Science
 
H

hellt

Rog¨¦rio Brito skrev:



I agree with the rest here. Your code generally looks fine.

But on another note, this type of code is not something you often see in
Python. It is very dense with regard to algorithm.

Most code is not like that so perhaps you should try something more
"usual" like sending email, fetching webpages etc. to get a feel for the
language.

--

hilsen/regards Max M, Denmark

http://www.mxm.dk/
IT's Mad Science

em, i would say, that python (esp. with NumPy+Psyco) is very popular
in numerical processing also.
 
M

Max M

hellt skrev:
em, i would say, that python (esp. with NumPy+Psyco) is very popular
in numerical processing also.

I know, and I might be way of, but I would believe that even that would
be more like stringing ready built modules together, calling methods etc.

I have written far denser code that the above example in Python
regularly. But It is like 1%-5% of my code I believe.

Unlike the c family of languages where there is a lot more algorithms
due to the low level coding. Memory handling, list, dicts etc. qickly
becomes more like math algorithms than in Python.


--

hilsen/regards Max M, Denmark

http://www.mxm.dk/
IT's Mad Science
 
R

Robert Bossy

Marc said:
I don't think so as that would break tons of code that relies on the
current behavior. Take a look at `itertools.islice()` if you want/need
an iterator.
A pity, imvho. Though I can live with islice() even if it is not as
powerful as the [:] notation.

RB
 
R

Rogério Brito

a = [i for i in range(0,n+1)]

Uhm... At least in 2.4 and earlier, range() returns a list... No
need for the list-comp in that era... range() also begins with 0

Thanks for the suggestion. As I stated in my original message, I'm only
"side-learning" Python, and I naturally think in list-comprehensions (it is like
a set in Mathematics and you've seen that my program is Mathematical in its nature).

This is exactly the kind of suggestion that I was looking for.


Thanks, Rogério.
 
R

Rogério Brito

Your Python is actually pretty good - if Raymond Hettinger pronounces it
OK then few would dare to disagree.

Thank you.
As for your English, though, the word you sought was "Pythonic" (not
that you will ever find such a word in Webster's dictionary). To suggest
that your code is Pythonesque would mean you found it farcical or
ridiculous (like a Monty Python sketch), which it clearly is not.

I didn't know about the pejorative meaning of Pythonesque. :) Thanks for the
comment on my English (which should be obvious that I'm not a native speaker).
PS: I think either my mailer or yours has mangled the indentation.

I think that it was mine.


Thanks, Rogério Brito.
 
R

Rogério Brito

If the OP insists in not examining a[0] and a[1], this will do exactly
the same as the while version:

for p in a[2:]:
if p:
print p

... at the cost of almost doubling the amount of memory required.

Yes, despite the asymptotic consumption of memory being the same, the practical
one is also a concern. And in my original version of that loop (sketched in
paper) was a for loop, but with C syntax.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top