Разница в быстродействии между плоским и вложенным словарем

Question

Я разработал программу на Python, упорядочивающую данные в выровненных словарях.По мере увеличения размера dict программа замедляется из-за интенсивного поиска ключей.Глядя на структуру вложенных словарей, мне кажется, что «иерархический» подход может ускорить поиск ключей.Я не прав?

Является ли вложенный dict:

nested_dict = { 'dictA': {'key_1': 'value_1', 'key_2': 'value_2'},
                'dictB': {'key_3': 'value_3', 'key_4': 'value_4', 'key_5': 'value_5'},
                ...
                'dictZ': {'key_m': 'value_m', 'key_n': 'value_n'}}

быстрее сплющенного dict:

dictionary = {'key_1': 'value_1',
              'key_2': 'value_2',
              ...
              'key_n': 'value_n'}

Редактировать: Добавлено несколько примеров кода

Ниже кусок кода, который я обычно используюПрограмма довольно большая, поэтому нет конкретного кода для оценки

Назначение:

dictionary['key_1'] = dictionary2['key_a']
dictionary['key_3'] = dictionary2['key_a']*dictionary['key_4']

Условное выражение:

if( (0 == dictionary['key_1']) and
    (dictionary2['key_b'] >= dictionary['key_3']) ):

Answer 1

Глядя на структуру вложенных словарей, мне кажется, что «иерархический» подход может ускорить поиск ключей.Я не прав?

Да: -)

Плоское пространство для диктовок имеет O (1) поиск независимо от размера.Это то, что делает хеш-таблицы такими привлекательными, как структура данных.

Добавление иерархии просто добавляет дополнительные этапы хеширования и этапы поиска.

В некоторых контекстах контейнеры получают некоторые преимущества локальности кэша, будучи маленькими, но в Python контейнеры имеют ссылки на объекты, которые разбросаны по всей памяти, поэтому компактность мало помогает.

Кроме того, Python является интерпретируемым языком, поэтому добавление дополнительного уровня поиска также влечет за собой большеоценки кода операции.Это затопило бы любые возможные преимущества для компактности.

Answer 2

Плоские словари работают быстрее, чем вложенные словари. Чтобы дополнить этот ответ, вот как я строю свои плоские словари.

Если ваши данные структурированы таким образом, что вы можете идентифицировать одно значение по комбинации клавиш (составной ключ), используйте кортежи в качестве ключей словаря.

companies = {}
companies[('Canada', 'ABC')] = 'Association des Bucherons du Canada'
companies[('Usa', 'ABC')] = 'American Broadcasting Company'
companies[('Usa', 'AAPL')] = 'Apple'

>>> companies.keys()
dict_keys([('Canada', 'ABC'), ('Usa', 'ABC'), ('Usa', 'AAPL')])

Ваш словарь будет плоским и быстрым.