__lt__ slowing the "in" operator even if not called

[Maric Michaud]

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