Улучшение сравнения Python и операций существования

Question

Я довольно новичок в Python и надеялся получить какой-нибудь совет, прежде чем двигаться дальше.У меня есть группа целых чисел, и я хочу проверить, содержится ли данный элемент в этой группе как можно быстрее (скорость имеет значение здесь).

В Python я должен смотреть на пользовательские структуры данныхадаптированные для этих операций (BST и т. д.), хитрости Python, такие как перенос с использованием any (), или есть какие-либо хорошо известные библиотеки Python / C, которые являются стандартными для такого рода вещей.Я не хочу изобретать колесо здесь, поэтому мне интересно услышать общий способ приблизиться к этому в Python.

Немного больше фона, все элементы вставлены в группу впереди, и ни одинпроизойдет после этого, поэтому время вставки не имеет значения.Кажется, это подразумевает, что поддержание отсортированной группы и выполнение чего-то вроде бинарного поиска будет лучшим подходом, но я уверен, что это уже реализовано гораздо более эффективно, чем я мог бы реализовать, и доступно в библиотеке Python / C.Интересно услышать, что вы, ребята, думаете.

Спасибо!

Answer 1

Как говорит DMS в комментарии, есть встроенный set (и неизменяемый вариант frozenset, который очень полезен, вам не нужно мутировать, и он может приспособить генерацию значений в одингенератор выражений).Это основано на хэше и поэтому жертвует порядком для проверенного членства O (1).Он написан на С, и на его создание ушло больше времени, чем вы могли бы на него разумно потратить.Если память работает правильно, она основана на реализации словаря, которая, вероятно, входит в число существующих хеш-таблиц быстрых (для общего использования).

Обратите внимание, что часть "хеш" также будет O (1)целые числа хеш для себя.Алгоритмы адаптированы для обработки «неслучайных» (например, несколько последовательных) хэшей очень хорошо.

Answer 2

Самый питонский способ - не хранить их в отсортированном контейнере, а использовать set (или неизменный вариант frozenset).Это контейнеры на основе хеша, поэтому поиск - O (1).Что еще более важно, алгоритм хеширования является одной из основных операций в Python (используется для словарей и поиска атрибутов), поэтому он написан на C и записан как fast .

И этокак правило, в случае с Python.Использование стандартных контейнеров будет быстрее, чем использование собственных контейнеров на уровне Python, поэтому старайтесь использовать их как можно чаще.

Если вы хотите сохранить их в отсортированном списке, посмотрите на bisect модуль в стандартной библиотеке.Он имеет стандартные функции для бинарного поиска.(Ну, на самом деле нет. На самом деле я возвращаю индекс того, где будет искомый элемент. Вам нужно будет выполнить окончательное сравнение самостоятельно.) И он может реализовать их в C (в зависимости от вашей конфигурации), так что этобудь быстрее того, что пишешь сам.