Вопрос:

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

python list optimization set

1170 просмотра

2 ответа

762 Репутация автора

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

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набор вместо списка. Есть ли другие способы значительно ускорить эту линию?

Автор: Paul Terwilliger Источник Размещён: 22.08.2016 09:17

Ответы (2)


2 плюса

1753 Репутация автора

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

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

Это не имеет большого смысла для списка длиной 30, хотя.

Автор: Dmitry Torba Размещён: 22.08.2016 09:20

0 плюса

867 Репутация автора

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

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

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

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

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

Автор: dgg32 Размещён: 22.08.2016 09:41
Вопросы из категории :
32x32