Набор работает как словарь без значений?

Question

Это вопрос версии Python: Существует ли коллекция, которая работает как словарь без значений?

Мне нужна структура данных, в которой есть список английских слов., но не их определения.

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

Будет set() или frozenset() будет правильным выбором?

Я знаю, что мог бы использовать словарь, в котором значение каждого ключа равно None, но это похоже на пустую трата памяти.

Answer 1

Да, set - правильный инструмент для этой работы.Вы можете узнать, есть ли слово в наборе с помощью in, который работает за время O (1).Добавление слов выполняется с помощью члена add, который занимает амортизированное O (1) время.Он также имеет все обычные операции с конечным множеством: объединение, пересечение, разность и т. Д.:

>>> A = set(["foo", "bar", "baz"])
>>> B = set(["foo", "ham", "spam"])
>>> "foo" in A
True
>>> "bar" in B
False
>>> A | B
set(['bar', 'ham', 'spam', 'foo', 'baz'])
>>> A & B
set(['foo'])
>>> A - B
set(['bar', 'baz'])
>>> B - A
set(['ham', 'spam'])

Answer 2

Да. Поиск набора - O (1) в среднем случае , к моему большому удивлению, к моему большому удивлению. Реализация должна быть близка к тому, что вы описываете (словарь с фиктивными значениями). См. Также этот связанный вопрос .

Для получения дополнительной информации о временных сложностях см .:

http://wiki.python.org/moin/TimeComplexity

Он не встроен и не включен ни в один из известных мне модулей, но, возможно, вам следует взглянуть на структуру данных Trie на случай, если вам понадобятся некоторые ее свойства в будущем.

Answer 3

Я не знаю о Big-O, но вот что говорит Python Language References о типах наборов :

Обычное использование для наборов - быстрое членствотестирование , удаление дубликатов из последовательности и вычисление математических операций, таких как пересечение, объединение, разность и симметричная разность.

Answer 4

Наборы имеют O (1) членские тесты в среднем и приятный интерфейс.