__lt__ slowing the "in" operator even if not called

[Emanuele Aina]

I have some code which does a lot of "in" on lists containing objects
with no __eq__ defined.

It all goes fast until I add the __lt__() method: then I have a
slowdown comparable to the one I get using the overridden __eq__, while
the __lt__ method is never called.

Someone can explain me why?


I have here a simple program which shows the behaviour:

*-------------------------------------------------------------------*

#!/usr/bin/env python

import timing

class State(object):
    def __init__(self, value):
        self.v = value

    def generate(self):
        return [self.__class__(self.v+1)]

class StateLT(State):
    def __lt__ (self, other):
        print 'Foo'
        return self.v < other.v

class StateEQ(State):
    def __eq__ (self, other):
        return self.v == other.v


def test(state_cls):
    print state_cls

    timing.start()
    initial = state_cls(0)
    l = [initial]
    for i in xrange(3000):

        successors = l[i].generate()
        successors = [s for s in successors if s not in l]

        l += successors
    timing.finish()
    print timing.milli()

if __name__ == '__main__':
    test(State)
    print '     '
    test(StateLT)
    print '     '
    test(StateEQ)

*-------------------------------------------------------------------*

On my machine the output is:

<class '__main__.State'>
406

<class '__main__.StateLT'>
4982

<class '__main__.StateEQ'>
5395

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.

I use the python 2.3.5-8 package on a debian unstable, but even the
python 2.4.3-5 package shows the same behaviour.