range() is not the best way to check range?

[Dan Bishop]

Paul Boddie wrote:
> John Machin wrote:
> > On 19/07/2006 1:05 AM, Dan Bishop wrote:
> > >
> > > xrange already has __contains__.
> >
> > As pointed out previously, xrange is a function and one would not expect
> > it to have a __contains__ method.
>
> Well, you pointed out that range is a function, but xrange seems to be
> a type...
>
> >>> xrange
> <type 'xrange'>
> >>> dir(xrange)
> ['__class__', '__delattr__', '__doc__', '__getattribute__',
> '__getitem__', '__hash__', '__init__', '__iter__', '__len__',
> '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__',
> '__setattr__', '__str__']
>
> No __contains__ method, though, at least in 2.4.1.
>
> > The objects returned by xrange do not (according to my reading of the
> > 2.4.3 version of Objects/rangeobject.c) have a __contains__ method.
>
> As confirmed by the above evidence.
>
> > I find it difficult to believe that an inefficient __contains__ has been
> > implemented since.
>
> So do I. As you go on to say, the usual sequence traversal mechanisms
> are probably used to support the "in" operator. Whether it's a pressing
> matter to add support for a more efficient mechanism depends on how
> often people want to use ranges in the way described. Perhaps I'll
> write a patch - who knows? ;-)

My mistake.  I should have looked at dir(xrange) before posting.

But the point remains that xrange's "implicit __contains__" runs in
linear time when a constant-time algorithm exists.