CODEWITHSUNDEEP
pythonlistoptimizationset
Paul Terwilliger
Paul Terwilliger

Reputation: 1646

Python: faster alternatives to searching if an item is "in" a list

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?

Upvotes: 0

Views: 2129

Answers (2)

Dmitry Torba
Dmitry Torba

Reputation: 3194

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.

Upvotes: 2

dgg32
dgg32

Reputation: 1447

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.

Upvotes: 0

Related Questions