Algorithm used by keyword 'in'

[Derek Rhodes]

#using python 2.4a3

say there is a list:

list = range(10000)

Now randomize it.

Next, command the interpreter:

What algorithm is used here?


-Derek.

 

[John Roth]

#using python 2.4a3

say there is a list:

list = range(10000)

Now randomize it.

Next, command the interpreter:


What algorithm is used here?

"in" asks the object to determine if the
operand is in the object. Since this is
a list, it's probably using a sequential
search. If it was a dictionary, it would
use a keyword lookup, as you would
expect. For any other object, it will
do whatever that object wants.

John Roth

 

[Jeremy Bowers]

What algorithm is used here?

In addition to John Roth's post, see the bottom of
http://docs.python.org/ref/sequence-types.html , which will help you
create your own algorithms for your own classes, if you like.

 

[Derek Rhodes]

In addition to John Roth's post, see the bottom of

http://docs.python.org/ref/sequence-types.html , which will help you
create your own algorithms for your own classes, if you like.

Thanks for quick response guys.

-Derek.

 

[dataangel]

Thanks for quick response guys.

-Derek.

Is python smart enough to do say a binary search if you sort the list
right before using in?

 

[Josiah Carlson]

Is python smart enough to do say a binary search if you sort the list
right before using in?

No, use the bisect module if you want to binary search. Knowing that a
sequence is sorted requires keeping an 'is_sorted' boolean attached to
the object (which may end up increasing the space used by each list).

It is also ambiguous to say that a list is "sorted". Even if the
following passes without exception:

for i in xrange(len(lst)-1):
assert lst < lst[i+1]

That does not mean that there isn't an ambiguous ordering that would
make binary search and/or list.sort() incorrect:True

One should need to be explicit when they want to binary search, because
it may not be correct in some cases.

"In the face of ambiguity, refuse the temptation to guess."


- Josiah

 

[Scott David Daniels]

.... For any other object, it will do whatever that object wants.

Reminds me of one of my favorite technical one-liners:

Don't anthropomorphize computers.... They don't like that.

-Scott David Daniels
(e-mail address removed)

 

[Chris Connett]

#using python 2.4a3

say there is a list:

list = range(10000)

Now randomize it.

Next, command the interpreter:


What algorithm is used here?

Since there are no guarantees about the list or the items it contains,
the best list can do is a linear search. Do be aware however that
each class can implement it's own behavior for keyword ``in``, by
implementing the ``__contains__`` method. For example, sets and dicts
use a hash table implementation for their __contains__ method, so
performance there will be O(1), but sets and dicts can only contain
hashable items. Your classes can implement it however they want, with
whatever semantics you want.

 

[Michael Hudson]

Is python smart enough to do say a binary search if you sort the list
right before using in?

No. How would Python be able to tell the list was sorted? There's
the bisect module for when *you* know the list is sorted.

Cheers,
mwh