O(n^2) is bad - can it be fixed?
aleaxit at yahoo.com
Tue May 22 10:45:53 CEST 2001
"E. Mark Ping" <emarkp at CSUA.Berkeley.EDU> wrote in message
news:9ed20b$jfj$1 at agate.berkeley.edu...
> In article <3B09FBF9.8691EBFE at accessone.com>,
> Helen Dawson <helend at accessone.com> wrote:
> >List does much better. Why? It probably does the same thing that the
> >STL vector typically does - the allocabe space doubles whenever it
> >runs out of room, and then the newly allocated space is filled in
> >as needed.
> Doubtful. It most likely does what std::list<> does--it allocates
No need to wonder in a void about such issues... listobject.c is
open for inspection in the Objects directory of any Python source
distribution! A python list is nothing like a C++ std::list --
the latter is a doubly-linked-list (fast insertion/removal at
any point, but O(N) to get the Nth item), the former is actually
an array or vector.
> space each time a new entry is added. That's linear, not n^2 time.
> std::vector<> uses geometric allocation to get amortized constant
> allocation time.
> If you need to add on character at a time, choose the data structure
> that does what you want. Perhaps a list of char?
Testing is better than wondering:
import time, array
head = repr(listorarray)
start = time.clock()
for i in range(0, 100):
for x in range(0, 2000):
# print i
stend = time.clock()
print "%s: %.2f" % (head, stend-start)
So, an array.array of characters turns out to be
systematically and repeatably 20% faster than a
list for this task on my box (an old clunky P3-266
NT4SP5 at this time:-). Unsurprising:-) -- it
has less overhead since it keeps 1 byte per char
rather than 4 bytes per item (a reference) plus
space for the char itself.
By the way, once your built-one-char-at-a-time
array.array('c') object is ready, just call its
method .tostring() to get the string equivalent
(if you choose to use a list instead, then the
best way to get the string is ''.join(thelist)).
The dominance of array.array for this shines
out clearly from Guido's essay/anecdote on
More information about the Python-list