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

[Dave Angel]

On 03/23/2015 09:42 PM, boB Stepp wrote:
> On Thu, Mar 19, 2015 at 12:10 AM, Dave Angel <davea at davea.name> wrote:
>> The catch to a list comprehension is it has to visit all the elements, while
>> a binary search would visit log-base-2 of them.  So instead of 10000
>> elements, you'd be searching about 14 items.
>
> I suspected as much, but had not verified this. Nonetheless, this may
> prove sufficiently fast. I will have to test this with my final data
> files. Right now I am using test cases, while I continue to design,
> check, rewrite, etc.
>
>> For large lists, it'd probably be much quicker to use the bisect module.
>> https://docs.python.org/3.4/library/bisect.html
>
> Can you give me a ballpark number for "large", where this would start
> making a meaningful difference?
>

Not really.  See Steve's response for some numbers. If I had to guess, 
I'd say that for lists over 100 items, you should use bisect or 
equivalent.  But I'd also say you should have one algorithm in your 
final code, even if it's sub-optimal for tiny lists.  If even a fraction 
of the searches are going to be on a list of 10k items, you should 
switch to a bisect approach.

I'd have to measure it, same as anyone.  And because of the 
reverse-ordering problem, you have to weigh the advantages of using a 
standard library (which is unlikely to be buggy), versus making an 
edited version which works directly on reversed lists.

It also can matter how many times you're searching the same list.  If 
you're going to be many lookups, it's worth keeping a reversed copy. 
You can reverse as simply as   rlist = mylist[::-1]



-- 
DaveA