Доступ к элементам словаря по позиции в Python 3. 6+ эффективно

Я понимаю, что словари - это вставка, упорядоченная в Python 3. 6+, как деталь реализации в 3.6 и официальная в 3. 7+.

Учитывая, что они упорядочены, кажется странным, что нет методов для извлечения i- ^го элемента словаря по порядку вставки. Доступны только доступные решения: O (n) сложность:

Преобразуйте в список через O (n) процесс, а затем используйте list.__getitem__.
enumerate словарные позиции в цикле и вернуть значение, когда достигнут желаемый индекс. Опять же, с O (n) временной сложностью.

Поскольку получение элемента из list имеет сложность O (1), существует ли способ достижения такой же сложности со словарями? Либо с обычным dict или collections.OrderedDict будет работать.

Если это невозможно, существует ли структурная причина, препятствующая такому методу, или это просто функция, которая еще не была рассмотрена/реализована?

Ответ 1

Для OrderedDict он неотъемлемо O(n) потому что упорядочение записывается в связанном списке.

Для встроенного dict существует вектор (смежный массив), а не связанный список, но в значительной степени то же самое в конце: вектор содержит несколько видов "манекенов", специальные внутренние значения, которые означают "no key" сохраненный здесь "или" ключ, который был сохранен здесь, но не более ". Это делает, например, удаление ключа чрезвычайно дешевым (просто перезапишите ключ с фиктивным значением).

Но без добавления дополнительных структур данных поверх этого нет возможности пропустить манекены, не перемещаясь по ним по одному. Поскольку Python использует форму открытой адресации для разрешения конфликтов и сохраняет коэффициент загрузки менее 2/3, по крайней мере, треть векторных записей являются манекенами. the_vector[i] можно получить доступ в O(1) раз, но на самом деле не имеет предсказуемого отношения к i-ой не-фиктивной записи.

Ответ 2

Согласно ответу @TimPeters, существуют структурные причины, по которым вы не можете получить доступ к элементам словаря по позиции за O (1) времени.

Стоит рассмотреть альтернативы, если вы ищете O (1) поиск по ключу или позиции. Существуют сторонние библиотеки, такие как NumPy/Pandas, которые предлагают такую функциональность, эффективную, особенно для числовых массивов, где указатели не требуются.

С Pandas вы можете создать "словарный" ряд с уникальными метками, предлагающими O (1) поиск по "метке" или позиции. Вы жертвуете производительностью при удалении метки, что влечет за собой затраты O (n), как и list.

import pandas as pd

s = pd.Series(list(range(n)))

# O(n) item deletion
del s[i]
s.drop(i)
s.pop(i)

# O(1) lookup by label
s.loc[i]
s.at[i]
s.get(i)
s[i]

# O(1) lookup by position
s.iloc[i]
s.iat[i]

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

Смотрите также: