0

I have a list of ~30 floats. I want to see if a specific float is in my list. For example:

1 >> # For the example below my list has integers, not floats
2 >> list_a = range(30)
3 >> 5.5 in list_a
False
4 >> 1 in list_a
True

The bottleneck in my code is line 3. I search if an item is in my list numerous times, and I require a faster alternative. This bottleneck takes over 99% of my time.

I was able to speed up my code by making list_a a set instead of a list. Are there any other ways to significantly speed up this line?

Paul Terwilliger
  • 1,596
  • 1
  • 20
  • 45
  • 4
    Making the `list` a `set` (one time) and then use the `set` for membership testing is the standard way to speed this up. There are other things that can help in certain cases (bisection if the list is sorted), but no other "general" solutions. – mgilson Aug 22 '16 at 21:18
  • 2
    Btw. Are you sure you want to test for membership? It checks equality, and [floating-point math is known to be broken](http://stackoverflow.com/questions/588004/is-floating-point-math-broken). – Łukasz Rogalski Aug 22 '16 at 21:28
  • Possible duplicate of [Most efficient way for a lookup/search in a huge list (python)](http://stackoverflow.com/questions/2701173/most-efficient-way-for-a-lookup-search-in-a-huge-list-python) – Eli Korvigo Aug 22 '16 at 21:40

2 Answers2

2

The best possible time to check if an element is in list if the list is not sorted is O(n) because the element may be anywhere and you need to look at each item and check if it is what you are looking for

If the array was sorted, you could've used binary search to have O(log n) look up time. You also can use hash maps to have average O(1) lookup time (or you can use built-in set, which is basically a dictionary that accomplishes the same task).

That does not make much sense for a list of length 30, though.

Dmitry Torba
  • 3,004
  • 1
  • 14
  • 24
  • 3
    I'm one of the down-voters. My reasons are: 1. built-in `set` is nothing like a search tree, it is a hash-table with `O(1)` amortised search complexity, while seach-trees usually have `O(log(n))`; 2. your post is a comment at best. – Eli Korvigo Aug 22 '16 at 21:34
  • @EliKorvigo I'm okay with reason 1, but the thing about the comment i don't share. This answer does not show code and might be short, but mentions a lot of important stuff (lower-bound, sorting-based search, difference between asymptotic-complexity and real execution-time (short list)). – sascha Aug 22 '16 at 22:18
  • Why don't you edit your post to remove misinformation? – Eli Korvigo Aug 23 '16 at 10:00
  • @DmitryTorba wrong once again, `set`'s implementation is not based on the `dict`, read the sources. – Eli Korvigo Aug 23 '16 at 13:43
0

In my experience, Python indeed slows down when we search something in a long list.

To complement the suggestion above, my suggestion will be subsetting the list, of course only if the list can be subset and the query can be easily assigned to the correct subset.

Example is searching for a word in an English dictionary, first subsetting the dictionary into 26 "ABCD" sections based on each word's initials. If the query is "apple", you only need to search the "A" section. The advantage of this is that you have greatly limited the search space and hence the speed boost.

For numerical list, either subset it based on range, or on the first digit.

Hope this helps.

dgg32
  • 1,409
  • 1
  • 13
  • 33