Вложенные словари или кортежи для ключа?
Предположим, что существует такая структура:
{'key1' : { 'key2' : { .... { 'keyn' : 'value' } ... } } }
Используя python, я пытаюсь определить преимущества/недостатки двух разных подходов:
{'key1' : { 'key2' : { .... { 'keyn' : 'value' } ... } } } # A. nested dictionary
{('key1', 'key2', ...., 'keyn') : 'value'} # B. a dictionary with a tuple used like key
Затем мне интересно узнать, что является лучшим (A или B) в терминах:
- Использование памяти
- Сложность во вставке (с учетом алоримов, избегающих столкновений и т.д.)
- Сложность в поиске
Ответы
Ответ 1
Не вдаваясь в подробности (которые в значительной степени зависят от реализации и могут быть признаны недействительными следующим гением, чтобы прийти и настроить реализацию словаря):
- Накладные расходы на память: у каждого объекта есть некоторые накладные расходы (например, refcount и type; пустой объект - 8 байтов, а пустой кортеж - 28 байт), но хэш-таблицы должны хранить хэш, ключ и значение и обычно использовать больше ковшей, чем в настоящее время необходимо избегать столкновения. Кортежи с другой стороны не могут быть изменены и не имеют коллизий, т.е. N-кортеж может просто выделить N указателей на содержащиеся объекты и сделать. Это приводит к заметным различиям в потреблении памяти.
- Для сложностей поиска и вставки (эти два являются идентичными в этом отношении): будь то строка или кортеж, столкновения вряд ли будут реализованы в реализации CPython dict и будут решены очень эффективно. Больше клавиш (потому что вы сглаживаете пространство клавиш путем комбинирования ключей в кортежах), возможно, увеличивает вероятность столкновений, больше клавиш также приводит к увеличению количества ковшей (AFAIK, текущая реализация пытается сохранить коэффициент загрузки между 2/3), что в свою очередь, делает вероятность столкновения менее вероятной. Кроме того, вам не нужно больше хэширования (ну, еще один вызов функции и некоторый X-уровень для хеширования кортежа, но это неясно), чтобы получить значение.
Понимаете, не должно быть заметной разницы в производительности, хотя есть разница в памяти. Я думаю, последнее не будет заметным. Одноэлементный dict - 140 байт, десятиэлементный кортеж - 140 байт (в соответствии с Python 3.2 sys.getsizeof
). Таким образом, даже с (уже нереалистичным, говорит мое ощущение кишки) десятиуровневым гнездом, у вас будет чуть больше одной КБ разницы - возможно, меньше, если вложенные dicts имеют несколько элементов (зависит от точного коэффициента нагрузки). Это слишком много для приложения хруста для данных, которое имеет сотни таких структур данных в памяти, но большинство объектов не создается так часто.
Вы должны просто спросить себя, какая модель более подходит для вашей проблемы. Учтите, что второй способ требует, чтобы у вас были все ключи для значения, доступные одновременно, а второе позволяет получать их пошагово.
Ответ 2
Если вам нужно использовать целую комбинацию key1
to keyn
, чтобы получить value
, вы можете перевернуть dict, как я предложил ниже для O (nk * nv) (количество ключей * количество значений) или используйте метод tuple
выше.
Предполагая, что вам нужно построить tuple
при вставке и снова, когда вам нужно получить значение, оба будут O (nk), где nk
- количество ключей.
Вложенная версия dict
может быть более эффективной с точки зрения пространства, если вы достаточно глубоко вложены (существует множество значений, которые разделяют частичный упорядоченный список ключей), и получение значения по-прежнему будет O (nk), но вероятно, медленнее, чем версия кортежа.
Однако вставка будет медленнее, хотя я не могу определить ее скорость. Вам нужно будет построить по крайней мере один слой dict
для каждой вставки и проверить существование
dict
на предыдущих уровнях.
Есть много рецепты для рекурсивного defaultdict
, что упростит вставку с точки зрения кодирования, но на самом деле это не ускорит процесс.
Метод tuple
является более простым и быстрым для вставки, но может занять больше памяти в зависимости от вашего гнездования.
Оригинальный ответ, прежде чем я узнал о требованиях
Почему бы не
{'key1' : 'value', 'key2' : 'value', .... 'keyn' : 'value' }
Он просто хранит ссылку на value
в каждом месте, а не value
, поэтому использование памяти будет меньше, чем вложенная версия dict
и не намного больше версии tuple
, если только вы имеют чрезвычайно большое число value
s.
Для временной сложности операций типа стандартного типа Python см. вики Python.
В принципе, вставка или получение одного элемента в среднем - O (1).
Получение всех ключей для значения в среднем будет O (n):
[key for key in mydict if mydict[key] == value]
Однако, если добавлять ключи или искать все ключи, это обычная операция, ваш dict
перевернут. Вы хотите:
{'value': [key1, key2, ... keyn]}
Таким образом вы можете добавлять ключи только с помощью mydict[value].append(newkey)
и получать все ключи только с mydict[value]
, и оба они будут в среднем O (1).
Ответ 3
Тестирование потребления памяти
Я написал небольшой script, чтобы проверить его. Он имеет некоторые ограничения, хотя ключи сделаны из целых чисел, линейно распределенных (т.е. range(N)
), мои выводы заключаются в следующем.
С 3-уровневым вложением, т.е. dict[a][b][c]
vs dict[a,b,c]
, где каждый подиндекс переходит от 0 до 99, я нахожу следующее:
При больших значениях (list(x for x in range(100)
)):
> memory.py nested
Memory usage: 1049.0 MB
> memory.py flat
Memory usage: 1149.7 MB
и с небольшими значениями ([]
):
> memory.py nested
Memory usage: 134.1 MB
> memory.py flat
Memory usage: 234.8 MB
Открытые вопросы
- Почему это происходит?
- Будет ли это изменяться с разными показателями, например. не последовательные?
Script
#!/usr/bin/env python3
import resource
import random
import itertools
import sys
import copy
from os.path import basename
from collections import defaultdict
# constants
index_levels = [100, 100, 100]
value_size = 100 # try values like 0
def memory_usage():
return resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
_object_mold = list(x for x in range(value_size)) # performance hack
def create_object():
return copy.copy(_object_mold)
# automatically create nested dict
# http://code.activestate.com/recipes/578057-recursive-defaultdict/
f = lambda: defaultdict(f)
my_dict = defaultdict(f)
# options & usage
try:
dict_mode = sys.argv[1]
if dict_mode not in ['flat', 'nested']: # ugly hack
raise Error()
except:
print("Usage: {} [nested | flat]".format(basename(sys.argv[0])))
exit()
index_generator = [range(level) for level in index_levels]
if dict_mode == "flat":
for index in itertools.product(*index_generator):
my_dict[index] = create_object()
elif dict_mode == "nested":
for index in itertools.product(*index_generator):
sub_dict = my_dict
for sub_index in index[:-1]: # iterate into lowest dict
sub_dict = sub_dict[sub_index]
sub_dict[index[-1]] = create_object() # finally assign value
print("Memory usage: {:.1f} MB".format(memory_usage() / 1024**2))