Классы словаря Python. "В" сложности

Быстрый вопрос, чтобы в основном удовлетворить мое любопытство по этой теме.

Я пишу несколько крупных программ на основе python с бэкэнд базы данных SQlite и буду иметь дело с большим количеством записей в будущем, поэтому мне нужно как можно больше оптимизировать.

Для нескольких функций я просматриваю ключи в словаре. Я использовал ключевое слово "in" для прототипирования и планировал вернуться и оптимизировать эти поисковые запросы позже, так как я знаю, что ключевое слово "in", как правило, O (n) (поскольку это просто переводит на python, итерацию по всему списку и сравнение каждый элемент). Но, поскольку питон python в основном представляет собой только хэш-карту, интерпретатор python достаточно умен, чтобы интерпретировать:

if(key in dict.keys()):
    ...code...

if(dict[key] != None):
    ...code...

Это в основном одна и та же операция, но верхняя часть будет O (n), а нижняя - O (1).

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

Ответ 1

Во-первых, key in d.keys() гарантированно даст вам то же значение, что и key in d для любого dict d.

И операция in на объекте dict или dict_keys, который вы возвращаете из вызова keys() на нем (в 3.x), не является O (N), это O (1).

Там нет реальной "оптимизации"; это просто, что использование хэша является очевидным способом реализации __contains__ в хеш-таблице, так же как это очевидный способ реализовать __getitem__.

Вы можете спросить, где это гарантировано.

Ну, это не так. Типы сопоставления определяет dict как, в основном, реализацию хеш-таблицы collections.abc.Mapping. Ничто не мешает кому-либо создавать хеш-таблицу реализации Mapping, но все же обеспечивает поиск O (N). Но это была бы дополнительная работа, чтобы сделать такую плохую реализацию, так почему они?

Если вам действительно нужно это доказать самому себе, вы можете протестировать каждую свою реализацию (с профилировщиком или с помощью какого-то типа с пользовательскими __hash__ и __eq__, которые регистрируют вызовы или...), или прочитайте источник.

В 2.x вы не хотите вызывать keys, потому что он генерирует list ключей, а не KeysView. Вы можете использовать iterkeys, но это может генерировать итератор или что-то еще, что не O (1). Поэтому просто используйте сам dict как последовательность.

Даже в 3.x вы не хотите вызывать keys, потому что нет необходимости. Итерируя a dict, проверяя его __contains__ и, вообще говоря, рассматривая его как последовательность, всегда эквивалентно тому, чтобы делать то же самое с его ключами, так зачем беспокоиться? (И, конечно, построение тривиального KeyView и доступ через него собираются добавить несколько наносекунд к вашему времени работы и несколько нажатий клавиш к вашей программе.)

(Не совсем ясно, что использование операций последовательности эквивалентно для d.keys()/d.iterkeys() и d в 2.x. Помимо проблем с производительностью, они эквивалентны в каждой реализации CPython, Jython, IronPython и PyPy, но он, кажется, нигде не указывается, как это делается в 3.x. И это не имеет значения, просто используйте key in d.)

Пока мы на нем, обратите внимание, что это:

if(dict[key] != None):

... не будет работать. Если key не находится в dict, это приведет к повышению KeyError, а не к возврату None.

Кроме того, вы не должны проверять None на == или !=; всегда используйте is.

Вы можете сделать это с помощью try -или, проще говоря, сделать if dict.get(key, None) is not None. Но опять же, нет причин для этого. Кроме того, это не будет обрабатывать случаи, когда None является вполне допустимым элементом. Если это так, вам нужно сделать что-то вроде sentinel = object(); if dict.get(key, sentinel) is not sentinel:.

Итак, правильно писать:

if key in d:

В более общем плане это неверно:

Я знаю, что ключевое слово "in", как правило, O (n) (поскольку это просто переводит на python, итерацию по всему списку и сравнение каждого элемента

Оператор in, как и большинство других операторов, является просто вызовом метода __contains__ (или эквивалентом для встроенного C/Java/.NET/RPython). list реализует его, итерируя список и сравнивая каждый элемент; dict реализует его путем хэширования значения и поиска хэша; blist.blist реализует его, прогуливаясь по дереву B +; и т.д. Таким образом, это могут быть O (n), O (1), O (log n) или что-то совершенно другое.

Ответ 2

В Python 2 dict.keys() сначала создается весь список ключей, почему это операция O(N), а key in dict - операция O(1).

if(dict[key] != None) будет поднимать KeyError, если ключ не найден в dict, поэтому он не эквивалентен первому коду.

Результаты Python 2:

>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 170 ns per loop
>>> %timeit 10000 in dic.keys()
100 loops, best of 3: 4.98 ms per loop
>>> %timeit 10000 in dic.iterkeys()
1000 loops, best of 3: 402 us per loop
>>> %timeit 10000 in dic.viewkeys()
1000000 loops, best of 3: 457 ns per loop

В Python 3 dict.keys() возвращает объект вида, который намного быстрее, чем Python 2 keys(), но все еще медленнее обычного обычного key in dict:

Результаты Python 3:

>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 295 ns per loop
>>> %timeit 10000 in dic.keys()
1000000 loops, best of 3: 475 ns per loop

Используйте только:

if key in dict:
   #code

Ответ 3

Правильный способ сделать это:

if key in dict:
    do stuff

Оператор в - это O (1) для словарей и наборов в python.

Ответ 4

Оператор in для dict имеет среднюю временную сложность O (1). Для получения подробной информации о временной сложности других методов dict() см. Ссылку .