David Isaac said:
Is it expected for access to set elements to be much
slower than access to list elements? Explanation?
Thanks,
Alan Isaac
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