Re: [OVC-demo-team] Random ballot generator

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Sat Mar 06 2004 - 12:37:29 CST

On Saturday, March 6, 2004, at 10:17 AM, Jan Karrman wrote:
> http://gnosis.python-hosting.com/voting-project/OVC-Demo/0166.html
from evm2003.utils.getxml import ballotxml
[...]

Btw. I just took a look at getxml.py from CVS (and likewise convert.py
which provides quite a few handy functions for our API).

It's still true that I should have used that rather than duplicating
much of its code in my own random_ballot.py script. However,
ballotxml() suffers from what is probably the most common of all Python
pitfalls... maybe the one area in Python where the "one obvious way" is
also the wrong way.

When you concatenate strings in Python, it seems straightforward to use:

        xml += '<some new tag>'

But if you do that in a loop of many such concatenations, you get
quadratic run time behavior. Since strings are immutable, each such
append must allocate space for a brand new string, then copy the old
string "xml" together with the "<some new tag>" string into the newly
allocated space, then deallocate the old strings (exact timing of
deallocation is not specified, but it needs to happen at some point).

For the small ballot files created by this function, it doesn't make a
lot of difference. For files that might get larger than you think in a
loop (...like, say, an old version of gnosis.xml.pickle :-( ), the time
can get quite bad.

In general, the right way to concatenate a bunch of strings in Python
is either:

(1) Append to a list, then join the list at the end:

        lines = []
    for thing in stuff:
                lines.append(doSomething(thing))
        return '\n'.join(lines)

(2) Use cStringIO to buffer lines:

     from cStringIO import StringIO
     buf = StringIO()
     for thing in stuff:
         buf.write(doSomething(thing)+"\n")
     return buf.getvalue()

Yours, David...

---
Dred Scott 1857; Santa Clara 1876; Plessy 1892; Korematsu 1944; Eldred 
2003
==================================================================
= The content of this message, with the exception of any external 
= quotations under fair use, are released to the Public Domain    
==================================================================
Received on Thu Apr 1 02:40:25 2004

This archive was generated by hypermail 2.1.8 : Thu Apr 01 2004 - 02:40:36 CST