Le Mercredi 14 Juin 2006 22:57, Emanuele Aina a écrit :
> Here you can see that even with only the __lt__ method it goes 10x
> slower, but __lt__ is never called as "Foo" is not printed.
No, that is not what it shows. The only thing it shows is that in operator is
slow for lists, and as it iterates over the entire list untill it find an
element, it is much slower when it fails a lot.
Use dict in operator instead.
Here is a program to show this in details :
import timing
class State(object):
def __init__(self, value):
self.v = value
class StateEQ(State):
def __eq__ (self, other):
if isinstance(other, State) :
return self.v == other.v
else :
return self.v == other
class StateLT(State) :
def __lt__ (self, other):
if isinstance(other, State) :
return self.v < other.v
else :
return self.v < other
class StateLTEQ(StateEQ, StateLT) : pass
def test(state_cls):
num_elem = 3*10**4
print
print state_cls
l = [state_cls(0)]
for i in xrange(num_elem): l.append(state_cls(i+1))
print
print "in operator at the beginning of list:",
timing.start()
for i in xrange(300): i in l
timing.finish()
print timing.milli()
print "in operator at the end of list:",
timing.start()
for i in xrange(num_elem-300, num_elem): i in l
timing.finish()
print timing.milli()
print
print "converting to dict :",
timing.start()
d = {}.fromkeys(l)
timing.finish()
print timing.milli()
print "in operator for a dict for %s elements:" % (num_elem*2),
timing.start()
for i in xrange(num_elem, num_elem*2): i in d
timing.finish()
print timing.milli()
if __name__ == '__main__':
test(State)
test(StateLT)
test(StateEQ)
test(StateLTEQ)
for which the output is :
<class '__main__.State'>
in operator at the beginning of list: 1983
in operator at the end of list: 2011
converting to dict : 82
in operator for a dict for 60000 elements: 12
<class '__main__.StateLT'>
in operator at the beginning of list: 3866
in operator at the end of list: 3871
converting to dict : 332
in operator for a dict for 60000 elements: 50
<class '__main__.StateEQ'>
in operator at the beginning of list: 173
in operator at the end of list: 28249
converting to dict : 79
in operator for a dict for 60000 elements: 14
<class '__main__.StateLTEQ'>
in operator at the beginning of list: 202
in operator at the end of list: 30472
converting to dict : 68
in operator for a dict for 60000 elements: 50
Every classes that define the __eq__ operator will find quickly the elements
if they are at the beginning of the list.
If they are at the end, the in oprerator is slower in these classes because of
the overhead of function calls (in StateLt there is also an overhead due to
internal lookup, IMO).
Converting to dicts and looking for keys is *really* and equally fast in all
cases, it does not depend on success or failure.
--
_____________
Maric Michaud
_____________
Aristote - www.aristote.info
3 place des tapis
69004 Lyon
Tel: +33 426 880 097
--
http://mail.python.org/mailman/listinfo/python-list
