Эффективный доступ к элементам словаря по позициям в Python 3.6+ - PullRequest
Новая
       19

Эффективный доступ к элементам словаря по позициям в Python 3.6+

0 голосов
/ 26 сентября 2018

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

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

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

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

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

Ответы [ 2 ]

0 голосов
/ 26 сентября 2018

Согласно ответу @ 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.Например, дубликаты ключей не предотвращаются и будут вызывать проблемы, если ряд используется в основном как отображение.Однако, если данные хранятся в непрерывном блоке памяти, как в примере выше, вы можете увидеть значительные улучшения производительности.

См. Также:

  1. Каковы преимуществаNumPy над обычными списками Python? .
  2. Какое влияние на производительность оказывают неуникальные индексы в пандах?
  3. Pandas DataFrame - линейный поисквремя или постоянное время?
0 голосов
/ 26 сентября 2018

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

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

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

...