array, list, performance...
gabor
how fast is list?
i mean accessing an item at an arbitrary position is O[n] or O[1]?
i need O[1].... are there any suitable classes in python?
thanks,
gabor
Michael Hudson
> hi,
>
> how fast is list?
>
> i mean accessing an item at an arbitrary position is O[n] or O[1]?
They are more like what tend to be called vectors in other languages,
in particular accessing an arbitrary element is O(1) (ignoring cache
effects and other little pesky details).
Cheers,
M.
--
Gullible editorial staff continues to post links to any and all
articles that vaguely criticize Linux in any way.
-- Reason #4 for quitting slashdot today, from
http://www.cs.washington.edu/homes/klee/misc/slashdot.html
Michael Chermside
li = [x0, x1, x2, ...]
li[n] element access is O(1)
li.append(x) appending is O(1)
(actually, it SOMETIMES takes O(len(li)) as it
resizes the list. But if you grow a list by
continually appending, the amortized time is
linear (ie, constant amortized time per element)
li.insert(0) prepending is O(len(li))
(so grow the list from the end!)
del li[0] deleting from the front (or middle) is O(len(li))
li.pop() deleting from the end is O(1)
li[n] = x assignment to the middle is O(len(li))
len(li) determining length is O(1)
li.index(x) search is O(len(li)) (NOT efficient)
li.sort() sort is O(len(li)*ln(len(li)))
(I believe it uses quicksort, but if a python
function has to be executed for the compare
that may take some time.)
It's really just your basic auto-growing array, but with a bunch of
clever things done to speed up common cases, and I don't know those well
enough to comment on them.
-- Michael Chermside
Christopher Armstrong
> Michael Chermside <mch...@destiny.com> writes::
> li[n] = x assignment to the middle is O(len(li))
This doesn't seem right. Shouldn't that be O(1), just like
access-time?
--
Chris Armstrong
<< ra...@twistedmatrix.com >>
http://twistedmatrix.com/users/carmstro.twistd/
Steve Holden
news:mailman.1023373030...@python.org...
>
> > Michael Chermside <mch...@destiny.com> writes::
> > li[n] = x assignment to the middle is O(len(li))
>
> This doesn't seem right. Shouldn't that be O(1), just like
> access-time?
>
If you can do it in O(1) you should go work for Zope corporation :-)
The problem is the need to make a new entry in the middle of the existing
structure. This can involve memory allocation and value copying, etc.
regards
-----------------------------------------------------------------------
Steve Holden http://www.holdenweb.com/
Python Web Programming http://pydish.holdenweb.com/pwp/
-----------------------------------------------------------------------
Steve Holden
news:mailman.1023373030...@python.org...
>
> > li[n] = x assignment to the middle is O(len(li))
>
> This doesn't seem right. Shouldn't that be O(1), just like
> access-time?
>
(I should have specifically said I was talking about INSERTION. You are
correct about assignment over an existing element).
--
Aahz
Michael Chermside <mch...@destiny.com> wrote:
>
> li.sort() sort is O(len(li)*ln(len(li)))
> (I believe it uses quicksort, but if a python
> function has to be executed for the compare
> that may take some time.)
Nope. I forget what Uncle Timmy used as his base, but while the
algorithm is O(NlogN) like quicksort, worst-case time is significantly
improved over quicksort's worst-case O(N^2), and the algorithm is
specifically designed to minimize compares precisely because even if a
Python function isn't listed for L.sort(), if L contains Python class
instances, it's quite likely to call instance methods.
--
Aahz (aa...@pythoncraft.com) <*> http://www.pythoncraft.com/
"I had lots of reasonable theories about children myself, until I
had some." --Michael Rios
gabor
> "Christopher Armstrong" <ra...@twistedmatrix.com> wrote in message
> news:mailman.1023373030...@python.org...
> >
> > > Michael Chermside <mch...@destiny.com> writes::
> > > li[n] = x assignment to the middle is O(len(li))
> >
> > This doesn't seem right. Shouldn't that be O(1), just like
> > access-time?
how can you use li[n] = x to INSERT an element into a list..
IndexError: list assignment index out of range
as far as i know:
if n<len(li) then it overwrites the existing value.
else you get an "IndexError: list assignment index out of range".
am i wrong?
thanks,
gabor
Michael Chermside
What I SHOULD have said was:
li[n] = x assignment to the middle is O(1)
li[n:n] = x INSERTION in the middle is O(len(li))
-- Michael Chermside
Ype Kingma
Michael Chermside wrote:
>
> Here is my understanding of it:
>
> li = [x0, x1, x2, ...]
>
> li[n] element access is O(1)
> li.append(x) appending is O(1)
> (actually, it SOMETIMES takes O(len(li)) as it
> resizes the list. But if you grow a list by
> continually appending, the amortized time is
> linear (ie, constant amortized time per element)
Append is often enough linear in the length of the list
that growing by appending is O(len(li) * len(li)).
You can prevent that by creating a list a large enough list
when starting, eg:
li = [None] * neededSize
> li.insert(0) prepending is O(len(li))
> (so grow the list from the end!)
> del li[0] deleting from the front (or middle) is O(len(li))
> li.pop() deleting from the end is O(1)
> li[n] = x assignment to the middle is O(len(li))
Assigment to the middle of a list is O(1), ie. same as element access.
> len(li) determining length is O(1)
> li.index(x) search is O(len(li)) (NOT efficient)
> li.sort() sort is O(len(li)*ln(len(li)))
> (I believe it uses quicksort, but if a python
> function has to be executed for the compare
> that may take some time.)
>
> It's really just your basic auto-growing array, but with a bunch of
> clever things done to speed up common cases, and I don't know those well
> enough to comment on them.
>
> -- Michael Chermside
Have fun,
Ype
--
email at xs4all.nl
Tim Peters
> li = [x0, x1, x2, ...]
> li.append(x) appending is O(1)
> (actually, it SOMETIMES takes O(len(li)) as it
> resizes the list. But if you grow a list by
> continually appending, the amortized time is
> linear (ie, constant amortized time per element)
[Ype Kingma]
> Append is often enough linear in the length of the list
> that growing by appending is O(len(li) * len(li)).
For Python 2.2 Michael is correct. For Python 2.1 and earlier, you're
correct "in theory", although in practice it was often linear-time anyway,
depending on internal details of the platform realloc.
> You can prevent that by creating a list a large enough list
> when starting, eg:
>
> li = [None] * neededSize
Yup, and that can save time regardless.
Ype Kingma
Tim Peters wrote:
>
> [Michael Chermside]
> > li = [x0, x1, x2, ...]
> > ...
> > li.append(x) appending is O(1)
> > (actually, it SOMETIMES takes O(len(li)) as it
> > resizes the list. But if you grow a list by
> > continually appending, the amortized time is
> > linear (ie, constant amortized time per element)
>
> [Ype Kingma]
> > Append is often enough linear in the length of the list
> > that growing by appending is O(len(li) * len(li)).
>
> For Python 2.2 Michael is correct. For Python 2.1 and earlier, you're
> correct "in theory", although in practice it was often linear-time anyway,
> depending on internal details of the platform realloc.
Good news.
Multiplying the list's size by a constant factor when necessary would
give O(log(len(li)) * len(li)) behaviour, so how was this made
O(len(li)) in 2.2?
I checked 'What's new in 2.2' but found nothing about this.
Regards,
Ype
Tim Peters
> li = [x0, x1, x2, ...]
> ...
> li.append(x) appending is O(1)
> (actually, it SOMETIMES takes O(len(li)) as it
> resizes the list. But if you grow a list by
> continually appending, the amortized time is
> linear (ie, constant amortized time per element)
[Ype Kingma]
> Append is often enough linear in the length of the list
> that growing by appending is O(len(li) * len(li)).
[Tim]
> For Python 2.2 Michael is correct. For Python 2.1 and earlier, you're
> correct "in theory", although in practice it was often
> linear-time anyway,> depending on internal details of the platform
> realloc.
[back to Ype]
> Good news.
> Multiplying the list's size by a constant factor when necessary would
> give O(log(len(li)) * len(li)) behaviour, so how was this made
> O(len(li)) in 2.2?
By increasing a list's size (when needed) by an amount proportional to its
current size.
> I checked 'What's new in 2.2' but found nothing about this.
Probably not. I don't write up a news item when I optimize away a useless
branch in the code either <wink>. Seriously, it's an internal
implementation detail, and, like I said, it often *acted* linear-time
anyway. The only platforms I know of where it appeared to make a real
difference were assorted flavors of Windows, and some flavor of BSD Unix (I
don't recall which). On those it helped a lot in cases of extreme list
abuse.
John Machin
> Multiplying the list's size by a constant factor when necessary would
> give O(log(len(li)) * len(li)) behaviour
I'm not sure where you get this from. Here's my take:
The theoretical amortised cost is O(N), not O(log(N)*N), where N is
the utimate size of the list.
Let F be the factor by which the list size is expanded when necessary.
Let e be the number of expansions required to grow to size N.
F**e is O(N).
The ith expansion involves fiddling with O(F**i) elements, with O(1)
cost each. The total of this over e expansions is O(F**e). As above,
F**e is O(N).
The O(1) cost each is theoretical. The operating system's memory
allocator may exhibit worse-than-linear behaviour.
Cheers,
John
Ype Kingma
John Machin wrote:
>
> Ype Kingma <yki...@accessforall.nl> wrote in message news:
> > Multiplying the list's size by a constant factor when necessary would
> > give O(log(len(li)) * len(li)) behaviour
>
> I'm not sure where you get this from. Here's my take:
>
> The theoretical amortised cost is O(N), not O(log(N)*N), where N is
> the utimate size of the list.
>
> Let F be the factor by which the list size is expanded when necessary.
> Let e be the number of expansions required to grow to size N.
> F**e is O(N).
>
> The ith expansion involves fiddling with O(F**i) elements, with O(1)
> cost each. The total of this over e expansions is O(F**e). As above,
> F**e is O(N).
Thanks. I thought each of the e expansions would involve fiddling with
O(N) elements.
Perhaps I should post before my working day instead of after...
Regards,
Ype
Kragen Sitaker
> Michael Chermside wrote:
> > li.append(x) appending is O(1)
> > (actually, it SOMETIMES takes O(len(li)) as it
> > resizes the list. But if you grow a list by
> > continually appending, the amortized time is
> > linear (ie, constant amortized time per element)
>
> Append is often enough linear in the length of the list
> that growing by appending is O(len(li) * len(li)).
Not when I try it:
Python 2.1.1 (#2, Dec 19 2001, 12:19:22)
[GCC 2.95.2 20000220 (Debian GNU/Linux)] on linux2
Type "copyright", "credits" or "license" for more information.
>>> import MetaPy.Speed
>>> def mklist(n):
... ar = []
... for ii in xrange(n):
... ar.append(ii)
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(0))
1.7825510264682151e-05
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(1))
2.862680041153042e-05
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(10))
7.8054009556034588e-05
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(100))
0.00057740376706547905
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(1000))
0.0055893541133707342
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(10000))
0.055918868174255905
>>> MetaPy.Speed.seconds_per_call(lambda: mklist(100000))
0.59515897688580466
Looks linear to me.
Scott Gilbert
> >>> import MetaPy.Speed
> >>> def mklist(n):
> ... ar = []
> ... for ii in xrange(n):
> ... ar.append(ii)
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(0))
> 1.7825510264682151e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(1))
> 2.862680041153042e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(10))
> 7.8054009556034588e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(100))
> 0.00057740376706547905
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(1000))
> 0.0055893541133707342
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(10000))
> 0.055918868174255905
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(100000))
> 0.59515897688580466
>
> Looks linear to me.
In a very practical sense your test is the one that matters, since
it's usually time that we care about. Your test could just as easily
be measuring how linear the memory allocator is or whether cache
effects are linear, since either of those could dwarf the cost of the
list operations. Who knows, you might actually have a realloc() that
does something smart. Also, it's pretty tough to tell the difference
between O(N) and O(N*log(N)) with such small numbers.
Here's some code that just counts the operations:
def roundupsize(n):
"Very similar to what is actually in listobject.c"
nbits = 0
n2 = n>>5
n2>>=3
nbits+= 3
while n2:
n2>>=3
nbits+=3
return ((n>>nbits) + 1) << nbits
def count(N):
ops = 0
size = 0
i = 0
while i<N:
i += 1
if i>size:
# have to pay for a copy and append
ops += size
ops += 1
size = roundupsize(i)
else:
# only pay for append
ops += 1
return ops
# N, ops, N/ops for powers of 10
1 1 1.0
10 18 0.555555555556
100 724 0.138121546961
1000 12264 0.0815394651011
10000 139536 0.0716660933379
100000 1590432 0.0628759984709
1000000 18333760 0.0545441851535
10000000 165188736 0.0605368152947
100000000 1425399552 0.0701557678054
# N, ops, N/ops for powers of 2
1 1 1.0
2 2 1.0
4 4 1.0
8 8 1.0
16 24 0.666666666667
32 80 0.4
64 288 0.222222222222
128 1088 0.117647058824
256 4224 0.0606060606061
512 5888 0.0869565217391
1024 12288 0.0833333333333
2048 37376 0.0547945205479
4096 50688 0.0808080808081
8192 101888 0.0804020100503
16384 302592 0.0541455160745
32768 409088 0.0801001251564
65536 818688 0.0800500312695
131072 2424320 0.054065469905
262144 3276288 0.0800125019534
524288 6553088 0.0800062504883
1048576 19398144 0.0540554807718
2097152 26213888 0.0800015625305
4194304 52428288 0.0800007812576
8388608 155188736 0.0540542323896
16777216 209714688 0.080000195313
33554432 419429888 0.0800000976564
The powers of 10 wave up and down a bit, but the powers of 2 make a
nice .08 .08 .05 pattern. Still looks linear, but it has bouts of
being non-linear before the next major step compensates for it. It
doesn't look to be O(N*N), and that's what really matters for large N.
Tim Peters
> >>> import MetaPy.Speed
> >>> def mklist(n):
> ... ar = []
> ... for ii in xrange(n):
> ... ar.append(ii)
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(0))
> 1.7825510264682151e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(1))
> 2.862680041153042e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(10))
> 7.8054009556034588e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(100))
> 0.00057740376706547905
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(1000))
> 0.0055893541133707342
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(10000))
> 0.055918868174255905
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(100000))
> 0.59515897688580466
>
> Looks linear to me.
[Scott Gilbert]
> In a very practical sense your test is the one that matters, since
> it's usually time that we care about. Your test could just as easily
> be measuring how linear the memory allocator is or whether cache
> effects are linear, since either of those could dwarf the cost of the
> list operations. Who knows, you might actually have a realloc() that
> does something smart.
In the old days, Guido was running on a Solaris box whose realloc eventually
moved a growing list to the end of memory, so that subsequent growth only
resulted in an sbrk call to boost the VM highwater mark. This was pretty
common, and gave linear time for such tests despite outraged theoreticians'
attempts to demonstrate it was quadratic time <wink>. The sbrk gimmick
fails if you're growing *more* than one list repeatedly, though, and for
that reason simplified benchmarks may not have anything to do with real-life
performance. More modern systems eventually move a growing thing into its
own mmap'ed memory segment, and then the true behavior depends on how some
other inscrutable OS subsystem behaves.
> Also, it's pretty tough to tell the difference between O(N) and
> O(N*log(N)) with such small numbers.
Yup!
> Here's some code that just counts the operations:
> [followed by code and some output]
> ...
> The powers of 10 wave up and down a bit, but the powers of 2 make a
> nice .08 .08 .05 pattern. Still looks linear, but it has bouts of
> being non-linear before the next major step compensates for it. It
> doesn't look to be O(N*N), and that's what really matters for large N.
It's linear. Ponder the comment in listobject.c:
/* Round up:
* If n < 256, to a multiple of 8.
* If n < 2048, to a multiple of 64.
* If n < 16384, to a multiple of 512.
* If n < 131072, to a multiple of 4096.
* If n < 1048576, to a multiple of 32768.
* If n < 8388608, to a multiple of 262144.
* If n < 67108864, to a multiple of 2097152.
* If n < 536870912, to a multiple of 16777216.
* ...
* If n < 2**(5+3*i), to a multiple of 2**(3*i).
...
The last line implies that overallocation, when it occurs, is never by less
than n/32 "extra" elements [2**(3*i)/2**(5+3*i) == 1/2**5]. That puts a
lower bound of 3.125% on excess, and that alone is enough to guarantee
amortized linear time. Let r = 1+1/32. If the final size is N, then
(ignoring details <wink>) you had to copy N/r elements on the last resize,
N/r**2 on the penultimate resize, N/r**3 on the one before that, etc. The
total number of element copies is thus bounded above by N/r + N/r**2 + ... =
N/r * (1 + 1/r + 1/r**2 + ...) = N/(r-1) = 32*N. Add N more for the
individual appends to get an upper bound of 33*N operations. Then your "N /
operations" statistic is bounded below by N/(33*N) = 1/33 ~= 0.03. You
never saw a number near that low because overallocation actually varies
between factors of 1/32 and 1/4 (right after a boundary is crossed in the
table) "extra" elements.
This may seem like too-mild overallocation anyway, but "even on Win95" most
reallocs under this scheme don't actually copy anything. So much for trying
to guess what happens <wink>.