Python: более быстрые альтернативы поиску, если элемент находится в списке

Question

У меня есть список ~ 30 поплавков. Я хочу посмотреть, есть ли в моем списке определенный float. Например:

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 

Узкие в моем коде является строкой 3. Я поиск, если элемент находится в моем списке много раз, и я требую более быстрой альтернативы. Это узкое место занимает более 99% моего времени.

Я был в состоянии ускорить мой код, сделав list_a набор вместо списка. Есть ли другие способы значительно ускорить эту линию?

Answer 1

Лучшее время, чтобы проверить, есть ли элемент в списке, если список не отсортирован, - это O (n), потому что элемент может быть где угодно, и вам нужно посмотреть на каждый элемент и проверить, является ли оно тем, что вы ищете для

Если массив был отсортирован, вы могли бы использовать двоичный поиск, чтобы иметь O (log n) время поиска. Вы также можете использовать хэш-карты, чтобы иметь среднее время поиска O (1) (или вы можете использовать встроенный набор, который в основном является словарем, который выполняет ту же задачу).

Это не имеет особого смысла для списка длины 30.

Answer 2

По моему опыту, Python действительно замедляется, когда мы ищем что-то в длинном списке.

В дополнение к предложению выше мое предложение будет подмножеством списка, конечно, только если список может быть подмножеством, и запрос может быть легко назначен правильному подмножеству.

Пример поиска слова в английском словаре, сначала подгоняя словарь в 26 разделов «ABCD» на основе инициалов каждого слова. Если запрос «яблоко», вам нужно только выполнить поиск в разделе «А». Преимущество этого заключается в том, что вы значительно ограничили пространство поиска и, следовательно, ускоряли скорость.

Для численного списка либо подмножество его основано на диапазоне, либо на первой цифре.

Надеюсь, это поможет.