How to read source code of python?

[Ian Kelly]

On Wed, Jun 9, 2010 at 11:54 PM, Benjamin Kaplan
<benjamin.kaplan at case.edu> wrote:
> On Wed, Jun 9, 2010 at 10:25 PM, Qijing Li <qjing.li at gmail.com> wrote:
>> Thanks for your reply.
>> I'm trying to understand python language deeply and  use it efficiently.
>> For example: How the operator "in" works on list? the running time is
>> be O(n)?  if my list is sorted, what the running time would be?
>>
>>
>
> Still O(n). Python doesn't know that your list is sorted, so nothing
> changes. And the check to make sure it is sorted would be O(n) anyway.

However, if the programmer knows that the list is sorted, then the
following would be O(log n):

from bisect import bisect_left

index = bisect_left(the_list, item)
item_in_list = index < len(the_list) and the_list[index] == item

But in general, if you want the "in" operator to be efficient, then
you probably want to use a set or a dict, not a list.

Cheers,
Ian