Little novice program written in Python

Discussion in 'Python' started by Rogério Brito, Apr 25, 2008.

  1. 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,

    --
    Rogério Brito : rbrito@{mackenzie,ime.usp}.br : GPG key 1024D/7C2CAEB8
    http://www.ime.usp.br/~rbrito : http://meusite.mackenzie.com.br/rbrito
    Projects: algorithms.berlios.de : lame.sf.net : vrms.alioth.debian.org
    Rogério Brito, Apr 25, 2008
    #1
    1. Advertising

  2. > 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
    Raymond Hettinger, Apr 25, 2008
    #2
    1. Advertising

  3. Rogério Brito

    Steve Holden Guest

    Rogério Brito wrote:
    > 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.
    --
    Steve Holden +1 571 484 6266 +1 800 494 3119
    Holden Web LLC http://www.holdenweb.com/
    Steve Holden, Apr 25, 2008
    #3
  4. Rogério Brito

    Guest

    On Apr 24, 11:09 pm, Dennis Lee Bieber <> wrote:
    > On Thu, 24 Apr 2008 21:31:15 -0300, Rogério Brito <>
    > declaimed the following in comp.lang.python:
    >
    > > 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
    >
    >
    >
    > >>> n = 5
    > >>> a = range(n+1)
    > >>> a

    > [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...
    >
    > >>> c = list(xrange(n+1))
    > >>> c

    > [0, 1, 2, 3, 4, 5]
    >
    > --
    >         Wulfraed        Dennis Lee Bieber               KD6MOG
    >                      
    >                 HTTP://wlfraed.home.netcom.com/
    >         (Bestiaria Support Staff:               )
    >                 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.
    , Apr 25, 2008
    #4
  5. Rogério Brito

    Peter Otten Guest

    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.

    Peter
    Peter Otten, Apr 25, 2008
    #5
  6. Rogério Brito

    Robert Bossy Guest

    Peter Otten wrote:
    > 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
    Robert Bossy, Apr 25, 2008
    #6
  7. Rogério Brito

    John Machin Guest

    On Apr 25, 5:44 pm, Robert Bossy <> wrote:
    > Peter Otten wrote:
    > > 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.
    John Machin, Apr 25, 2008
    #7
  8. Rogério Brito

    Robert Bossy Guest

    John Machin wrote:
    > On Apr 25, 5:44 pm, Robert Bossy <> wrote:
    >
    >> Peter Otten wrote:
    >>
    >>> 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
    Robert Bossy, Apr 25, 2008
    #8
  9. Rogério Brito

    hellt Guest

    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]
    hellt, Apr 25, 2008
    #9
  10. Rogério Brito

    hellt Guest

    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.
    hellt, Apr 25, 2008
    #10
  11. hellt <> writes:

    > 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]:

    > j = s*s

    remove this line

    > while j <= N:

    for j in xrange(s*s, N+1, s):

    > arr[j-1] = 0


    > j += s

    remove this line

    > s += 1

    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.

    --
    Arnaud
    Arnaud Delobelle, Apr 25, 2008
    #11
  12. Rogério Brito

    hellt Guest

    On 25 ÁÐÒ, 13:29, Arnaud Delobelle <> wrote:
    > hellt <> writes:
    > > 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]:
    >
    > > j = s*s

    >
    > remove this line
    >
    > > while j <= N:

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

    >
    > remove this line
    >
    > > s += 1

    >
    > 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.
    >
    > --
    > Arnaud


    nice, but i'm a newbie to python too, so some things for me seems a
    liitle complicated)))
    hellt, Apr 25, 2008
    #12
  13. On Fri, 25 Apr 2008 10:24:16 +0200, Robert Bossy wrote:

    > John Machin wrote:
    >> On Apr 25, 5:44 pm, Robert Bossy <> wrote:
    >>
    >>> 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
    Marc 'BlackJack' Rintsch, Apr 25, 2008
    #13
  14. Rogério Brito

    Max M Guest

    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
    Max M, Apr 25, 2008
    #14
  15. Rogério Brito

    hellt Guest

    On 25 §Ñ§á§â, 15:02, Max M <> wrote:
    > 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


    em, i would say, that python (esp. with NumPy+Psyco) is very popular
    in numerical processing also.
    hellt, Apr 25, 2008
    #15
  16. Rogério Brito

    Max M Guest

    hellt skrev:

    >> 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.
    >>

    > 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
    Max M, Apr 25, 2008
    #16
  17. Rogério Brito

    Robert Bossy Guest

    Marc 'BlackJack' Rintsch wrote:
    >> 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.

    A pity, imvho. Though I can live with islice() even if it is not as
    powerful as the [:] notation.

    RB
    Robert Bossy, Apr 25, 2008
    #17
  18. On 04/25/2008 01:09 AM, Dennis Lee Bieber wrote:
    > On Thu, 24 Apr 2008 21:31:15 -0300, Rogério Brito <>
    > declaimed the following in comp.lang.python:
    >> 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.

    --
    Rogério Brito : rbrito@{mackenzie,ime.usp}.br : GPG key 1024D/7C2CAEB8
    http://www.ime.usp.br/~rbrito : http://meusite.mackenzie.com.br/rbrito
    Projects: algorithms.berlios.de : lame.sf.net : vrms.alioth.debian.org
    Rogério Brito, Apr 28, 2008
    #18
  19. On 04/25/2008 01:30 AM, Steve Holden wrote:
    > Rogério Brito wrote:
    >> 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).

    > 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.

    --
    Rogério Brito : rbrito@{mackenzie,ime.usp}.br : GPG key 1024D/7C2CAEB8
    http://www.ime.usp.br/~rbrito : http://meusite.mackenzie.com.br/rbrito
    Projects: algorithms.berlios.de : lame.sf.net : vrms.alioth.debian.org
    Rogério Brito, Apr 28, 2008
    #19
  20. On 04/25/2008 05:00 AM, John Machin wrote:
    > On Apr 25, 5:44 pm, Robert Bossy <> 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.


    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.

    --
    Rogério Brito : rbrito@{mackenzie,ime.usp}.br : GPG key 1024D/7C2CAEB8
    http://www.ime.usp.br/~rbrito : http://meusite.mackenzie.com.br/rbrito
    Projects: algorithms.berlios.de : lame.sf.net : vrms.alioth.debian.org
    Rogério Brito, Apr 28, 2008
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Steve C. Orr, MCSD
    Replies:
    1
    Views:
    556
    reaway lee
    Aug 24, 2003
  2. Roedy Green

    Little job for novice programmer

    Roedy Green, Sep 9, 2003, in forum: Java
    Replies:
    0
    Views:
    351
    Roedy Green
    Sep 9, 2003
  3. David Stockwell
    Replies:
    2
    Views:
    543
    Grant Edwards
    Jun 8, 2004
  4. KaiWen
    Replies:
    102
    Views:
    2,717
    Jorgen Grahn
    Sep 15, 2011
  5. Joao Pedrosa
    Replies:
    0
    Views:
    103
    Joao Pedrosa
    Jun 21, 2004
Loading...

Share This Page