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

Mark Lawrence breamoreboy at yahoo.co.uk
Thu Mar 19 06:14:15 CET 2015


On 19/03/2015 04:20, boB Stepp wrote:
> I hope extolling the beauty and power of Python on this list is
> allowed, because I have had a large "WOW!!!" moment tonight. I had a
> problem I was working on at work this afternoon. I have a list of ~
> 10,000 floating point numbers, which run from largest to smallest.
> There are duplicates scattered throughout, so I might have something
> like: [5942.6789, 5942.6789, 5941.000003, 5941.01, 5941.01, ... ],
> etc. I wanted to search the list for a test value, which, depending on
> the particular list (I can have many such lists, each different from
> the other.), could conceivably be anywhere within the given list. I
> needed to return the index where the list values change from being
> just greater than the test value to just less than the test value at
> the very next index position. I spent a good chunk of my afternoon
> writing a binary search function and wondering what theoretically the
> optimum search algorithm would be, got interrupted (as usual on this
> project), and decided to look at my books at home to see if a better
> solution would be staring at me from some book (Like there usually
> is!).
>
> I haven't studied list comprehensions formally yet, but a snippet of
> code in a book caught my eye where the author was discussing filtering
> data in a list. This led me to try:
>
> 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!!!
>
>

How does the performance of your code compare to the bisect module 
https://docs.python.org/3/library/bisect.html#module-bisect ?

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence



More information about the Tutor mailing list