On Tue, 09 Jun 2009 04:57:48 -0700, samwyse wrote:
> Time to test things! I'm going to compare three things using Python
> 3.0:
> X={...}\nS=lambda x: x in X
> S=lambda x: x in {...}
> S=lambda x: x in (...)
> where the ... is replaced by lists of integers of various lengths.
> Here's the test bed:
[snip]
Hmmm... I think your test-bed is unnecessarily complicated, making it
difficult to see what is going on. Here's my version, with lists included
for completeness. Each test prints the best of five trials of one million
repetitions of ten successful searches, then does the same thing again
for unsuccessful searches.
from timeit import Timer
def test(size):
global s, l, t, targets
print("Testing search with size %d" % size)
rng = range(size)
s, l, t = set(rng), list(rng), tuple(rng)
# Calculate a (more or less) evenly distributed set of ten
# targets to search for, including both end points.
targets = [i*size//9 for i in range(9)] + [size-1]
assert len(targets) == 10
setup = "from __main__ import targets, %s"
body = "for i in targets: i in %s"
# Run a series of successful searches.
for name in "s l t".split():
obj = globals()[name]
secs = min(Timer(body % name, setup % name).repeat(repeat=5))
print("Successful search in %s: %f s" % (type(obj), secs))
# Also run unsuccessful tests.
targets = [size+x for x in targets]
for name in "s l t".split():
obj = globals()[name]
secs = min(Timer(body % name, setup % name).repeat(repeat=5))
print("Unsuccessful search in %s: %f s" % (type(obj), secs))
Results are:
>>> test(1)
Testing search with size 1
Successful search in <class 'set'>: 1.949509 s
Successful search in <class 'list'>: 1.838387 s
Successful search in <class 'tuple'>: 1.876309 s
Unsuccessful search in <class 'set'>: 1.998207 s
Unsuccessful search in <class 'list'>: 2.148660 s
Unsuccessful search in <class 'tuple'>: 2.137041 s
>>>
>>>
>>> test(10)
Testing search with size 10
Successful search in <class 'set'>: 1.943664 s
Successful search in <class 'list'>: 3.659786 s
Successful search in <class 'tuple'>: 3.569164 s
Unsuccessful search in <class 'set'>: 1.935553 s
Unsuccessful search in <class 'list'>: 5.833665 s
Unsuccessful search in <class 'tuple'>: 5.573177 s
>>>
>>>
>>> test(100)
Testing search with size 100
Successful search in <class 'set'>: 1.907839 s
Successful search in <class 'list'>: 21.704032 s
Successful search in <class 'tuple'>: 21.391875 s
Unsuccessful search in <class 'set'>: 1.916241 s
Unsuccessful search in <class 'list'>: 41.178029 s
Unsuccessful search in <class 'tuple'>: 41.856226 s
>>>
>>>
>>> test(1000)
Testing search with size 1000
Successful search in <class 'set'>: 2.256150 s
Successful search in <class 'list'>: 189.991579 s
Successful search in <class 'tuple'>: 187.349630 s
Unsuccessful search in <class 'set'>: 1.869202 s
Unsuccessful search in <class 'list'>: 398.451284 s
Unsuccessful search in <class 'tuple'>: 388.544178 s
As expected, lists and tuples are equally as fast (or slow if you
prefer). Successful searches are about twice as fast as unsuccessful
ones, and performance suffers as the size of the list/tuple increases.
However, sets are nearly just as fast no matter the size of the set, or
whether the search is successfully or unsuccessful.
> You will note that testing against a list constant is just as fast as
> testing against a set. This was surprising for me; apparently the
> __contains__ operator turns a tuple into a set.
I doubt that very much.
--
Steven
--
http://mail.python.org/mailman/listinfo/python-list
