[Tutor] List comprehensions to search a list--amazing!

[Peter Otten]

Patrick Thunstrom wrote:

>>>> The generalized problem:
>>>>
>>>> L = [V0, V1, ..., Vn], where V0 >= V1 >= V2 >= ... >= Vn .
>>>> Find index i, such that V[i] >= Vt >= V[i + 1], where Vt is the test
>>>> value being searched for. I need to know the indices i and i + 1,
>>>> which I need to interpolate based on where Vt falls.
>>>>
>>>> The solution (As a sublist, S)  I worked out tonight after
>>>> experimenting with comprehension syntax is:
>>>> S = [i for i, V in enumerate(L) if L[i] >= Vt >= L[i + 1]]
>>>>
>>>> And, of course, the index i I need is:
>>>> i = S[0]
>>>>
>>>> I tested this out with concrete examples in the interpreter, such as
>>>> with a list, L:
>>>>
>>>> L = [item for item in range(10000, 0, -1)]
>>>>
>>>> and trying different test values. It was blazingly fast, too!
>>>>
>>>> All I can say is: WOW!!!
>>
>> By the way, if you were to use a plain old loop the expected speedup over
>> the listcomp would be 2. You can break out of the loop when you have
>> found the gap, after iterating over one half of the list on average.
>>
>> So for-loops are twice as amazing ;)
> 
> For the same basic speed up, a generator expression with a call to
> next() will produce similar results. Without the additional code to
> get the indexed item.
> 
> index = (i for i, _ in enumerate(original_list) if original_list[i] >=
> target >= original_list[i + 1]).next()
> 
> The only catch is it raises a StopIteration exception if no element
> fits the test.

In new code you shouldn't call the next() method (renamed __next__() in 
Python 3) explicitly. Use the next() builtin instead which also allows you 
to provide a default:


>>> exhausted = iter(())
>>> next(exhausted)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> next(exhausted, "default_value")
'default_value'


That said, rather than polishing the implementation of the inferior 
algorithm pick the better one.

Ceterum censeo bisect is the way to go here ;)