[Tutor] List comprehensions to search a list--amazing!
Patrick Thunstrom
pathunstrom at gmail.com
Thu Mar 19 18:15:33 CET 2015
>>> 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.
P
More information about the Tutor
mailing list