473,698 Members | 1,846 Online

# Algorithm used by keyword 'in'

#using python 2.4a3

say there is a list:

list = range(10000)

Now randomize it.

Next, command the interpreter:
465 in list True

What algorithm is used here?
-Derek.
Jul 18 '05 #1
8 1365

"Derek Rhodes" <rh****@worldpa th.net> wrote in message
news:lY******** ************@tw ister.nyroc.rr. com...
#using python 2.4a3

say there is a list:

list = range(10000)

Now randomize it.

Next, command the interpreter:
465 in list True

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

-Derek.

Jul 18 '05 #2
On Sat, 09 Oct 2004 14:54:09 +0000, Derek Rhodes wrote:
What algorithm is used here?

In addition to John Roth's post, see the bottom of
Jul 18 '05 #3
> In addition to John Roth's post, see the bottom of

Thanks for quick response guys.

-Derek.
Jul 18 '05 #4
Derek Rhodes wrote:
In addition to John Roth's post, see the bottom of

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?

Jul 18 '05 #5
John Roth wrote:
.... For any other object, it will do whatever that object wants.

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

Don't anthropomorphiz e computers.... They don't like that.

-Scott David Daniels
Sc***********@A cm.Org
Jul 18 '05 #6
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[i] < lst[i+1]

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

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

Jul 18 '05 #7
"Derek Rhodes" <rh****@worldpa th.net> wrote in message news:<lY******* *************@t wister.nyroc.rr .com>...
#using python 2.4a3

say there is a list:

list = range(10000)

Now randomize it.

Next, command the interpreter:
465 in list True

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.

--
Chris Connett
Jul 18 '05 #8
dataangel <k0*****@kzoo.e du> writes:
Derek Rhodes wrote:
In addition to John Roth's post, see the bottom of

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?

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

--
The ability to quote is a serviceable substitute for wit.
-- W. Somerset Maugham
Jul 18 '05 #9

This thread has been closed and replies have been disabled. Please start a new discussion.