item access time: sets v. lists

[Paul McGuire]

"David Isaac" <aisaac0 at verizon.net> wrote in message 
news:QWQUg.15396$3T2.2982 at trnddc06...
> Is it expected for access to set elements to be much
> slower than access to list elements?  Explanation?
> Thanks,
> Alan Isaac
>
>>>> t1=timeit.Timer("for i in set(xrange(10000)):pass","")
>>>> t2=timeit.Timer("for i in list(xrange(10000)):pass","")
>>>> t1.timeit(1000)
> 9.806250235714316
>>>> t2.timeit(1000)
> 3.9823075279120701
>
>
A couple of points:
1. Your use of timeit is a bit flawed.  You are not only timing the access 
into the set or list, but also the construction of the set/list, *every 
time*.  Use the second string arg (the one you are passing as "") for 
one-time initialization, so that you measure only access, which is what you 
say your are interested in.
2. Ooops, it turns out you're not really *accessing* the set/list, you are 
*iterating* over it.  Given that sets are implemented internally using a 
tree structure, I would expect that iterating over a list could be faster, 
although only marginally so.
3. Here are some stats for a little more correct timeits:

Construct list/set
set  -> 1.89524618352
list -> 0.299499796762

Iterate over list/set
set  -> 0.646887523414
list -> 0.552001162159

Random access to first item in list/set
set  -> 0.000189409547861
list -> 0.000160076210804

Random access to item in list/set when item exists
set  -> 0.000241650824337
list -> 0.0245168031132

Random access to item in list/set when item does not exist
set  -> 0.000187733357172
list -> 0.522086186932


The code:
import timeit

print "\nConstruct list/set"
t1=timeit.Timer("z = set(xrange(10000))","")
t2=timeit.Timer("z = list(xrange(10000))","")
print "set  ->", t1.timeit(1000)
print "list ->", t2.timeit(1000)

print "\nIterate over list/set"
t1=timeit.Timer("for i in z: pass","z = set(xrange(10000))")
t2=timeit.Timer("for i in z: pass", "z = list(xrange(10000))")
print "set  ->", t1.timeit(1000)
print "list ->", t2.timeit(1000)

print "\nRandom access to first item in list/set"
t1=timeit.Timer("0 in z","z = set(xrange(10000))")
t2=timeit.Timer("0 in z", "z = list(xrange(10000))")
print "set  ->", t1.timeit(1000)
print "list ->", t2.timeit(1000)

print "\nRandom access to item in list/set when item exists"
t1=timeit.Timer("500 in z","z = set(xrange(10000))")
t2=timeit.Timer("500 in z", "z = list(xrange(10000))")
print "set  ->", t1.timeit(1000)
print "list ->", t2.timeit(1000)

print "\nRandom access to item in list/set when item does not exist"
t1=timeit.Timer("10500 in z","z = set(xrange(10000))")
t2=timeit.Timer("10500 in z", "z = list(xrange(10000))")
print "set  ->", t1.timeit(1000)
print "list ->", t2.timeit(1000)


-- Paul