вложенные словари или кортежи для ключа?

Question

Предположим, есть такая структура:

{'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) с точки зрения:

• Занятие памяти
• Сложность при вставке (с учетом избегающих столкновений алгоритмов и т.д ...)1012 *
• Сложность в поиске

Answer 1

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

• Для служебной памяти: каждый объект имеет некоторые служебные данные (например, refcount и тип; пустой объект - 8 байтов, а пустой кортеж - 28 байтов), но хеш-таблицы должны хранить хэш, ключ и значение и обычно используют больше блоков, чем В настоящее время необходимо избегать столкновений. С другой стороны, кортежи не могут быть изменены и не имеют коллизий, то есть N-кортеж может просто назначить N указателей на содержащиеся объекты, и это можно сделать. Это приводит к заметным различиям в потреблении памяти.
• Для сложности поиска и вставки (в этом отношении они идентичны): будь то строка или кортеж, коллизии довольно маловероятны в реализации dict в CPython и разрешаются очень эффективно. Большее количество ключей (поскольку вы выравниваете пространство ключей путем объединения ключей в кортежах) может увеличить вероятность коллизий, большее количество ключей также приведет к увеличению количества сегментов (AFAIK текущая реализация пытается сохранить коэффициент загрузки между 2/3), что в свою очередь, делает столкновение менее вероятным. Кроме того, вам не нужно больше хэширования (ну, еще один вызов функции и некоторая перестановка на уровне C для хэша кортежа, но это невозможно), чтобы получить значение.

Видите ли, не должно быть никаких заметных различий в производительности, хотя некоторые различия в памяти. Последнее не будет заметным, хотя, я думаю. Одноэлементный dict составляет 140 байтов, кортеж из десяти элементов также составляет 140 байтов (согласно Python 3.2 sys.getsizeof). Таким образом, даже при десятиуровневой (уже нереально, как мне кажется, интуиции) разнице вы получите чуть более одного килобайта разницы - возможно, меньше, если во вложенных диктовках есть несколько элементов (зависит от точного коэффициента загрузки). Это слишком много для приложения обработки данных, которое имеет сотни таких структур данных в памяти, но большинство объектов создаются не так часто.

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

Answer 2

Если вам нужно использовать целую комбинацию от key1 до keyn, чтобы получить value, вы можете перевернуть диктовку, как я предложил ниже для O (nk * nv) (количество ключей * количество значений) или используйте метод tuple выше.

Предполагая, что вам нужно построить tuple при вставке, и снова, когда вам нужно получить значение, оба будут O (nk), где nk - количество ключей.

Вложенная версия dict может быть более компактной, если вы вложены достаточно глубоко (есть много значений, которые разделяют частично упорядоченный список ключей), и получение значения все равно будет O (nk), но вероятно, медленнее, чем версия кортежа.

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

Существует много рецептов для рекурсивных defaultdict с, которые упростили бы вставку с точки зрения кодирования, но на самом деле это не ускорило бы.

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

---

Оригинальный ответ, прежде чем я знал требования

Почему бы не

{'key1' : 'value', 'key2' : 'value', .... 'keyn' : 'value' } 

Он просто хранит ссылку на value в каждом месте, а не value, поэтому использование памяти будет на меньше , чем у вложенной версии dict, и не намного больше, чем * Версия 1043 *, если только у вас не слишком большое число value с.

Временную сложность операций стандартного типа 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).

Answer 3

Тестирование производительности

Я выполнил тесты для зацикливания, поиска и вставки для вложенного словаря и словаря с кортежем.Они на глубину одного уровня, 2000.000 значений.Я также делал поиск и вставку для кортежа с уже созданным кортежем.

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

-

keydictinsertion: Mean +- std dev: 615 ms +- 42 ms  
keydictretrieval: Mean +- std dev: 475 ms +- 77 ms  
keydictlooping: Mean +- std dev: 76.2 ms +- 7.4 ms  

nesteddictinsertion: Mean +- std dev: 200 ms +- 7 ms  
nesteddictretrieval: Mean +- std dev: 256 ms +- 32 ms  
nesteddictlooping: Mean +- std dev: 88.5 ms +- 14.4 ms  

Test were the tuple was already created for the keydict  
keydictinsertionprepared: Mean +- std dev: 432 ms +- 26 ms  
keydictretrievalprepared: Mean +- std dev: 267 ms +- 14 ms

-

Как вы можете видеть, nesteddict, если часто быстрее, чем dict с помощью одной клавиши.Даже при непосредственном присвоении ключевому слову кортежа без шага создания кортежа вставка все равно была значительно медленнее.Казалось, что дополнительное создание внутреннего диктата обходится не так дорого.Defaultdict, вероятно, имеет быструю реализацию.Поиск фактически был практически равным, когда не нужно было создавать кортеж, то же самое с циклом.

Тестирование выполняется с помощью perf из командной строки.Скрипты ниже.

>>>>>>> nesteddictinsertion
python -m perf timeit -v -s "
from collections import defaultdict
" " 
d = defaultdict(dict)
for i in range(2000):
    for j in range(1000):
        d[i][j] = 1
"
>>>>>>> nesteddictlooping
python -m perf timeit -v -s "
from collections import defaultdict
d = defaultdict(dict)
for i in range(2000):
    for j in range(1000):
        d[i][j] = 1
" "
for i, inner_dict in d.items():
    for j, val in inner_dict.items():
        i
        j
        val
"
>>>>>>> nesteddictretrieval
python -m perf timeit -v -s "
from collections import defaultdict
d = defaultdict(dict)
for i in range(2000):
    for j in range(1000):
        d[i][j] = 1
" "
for i in range(2000):
    for j in range(1000):
        d[i][j]
"
>>>>>>> keydictinsertion
python -m perf timeit -v -s "
from collections import defaultdict
" " 
d = {}
for i in range(2000):
    for j in range(1000):
        d[i, j] = 1
"
>>>>>>> keydictinsertionprepared
python -m perf timeit -v -s "
from collections import defaultdict
keys = [(i, j) for i in range(2000) for j in range(1000)]
" " 
d = {}
for key in keys:
    d[key] = 1
"
>>>>>>> keydictlooping
python -m perf timeit -v -s "
from collections import defaultdict
d = {}
for i in range(2000):
    for j in range(1000):
        d[i, j] = 1
" "
for key, val in d.items():
    key
    val
"
>>>>>>> keydictretrieval
python -m perf timeit -v -s "
from collections import defaultdict
d = {}
for i in range(2000):
    for j in range(1000):
        d[i, j] = 1
" "
for i in range(2000):
    for j in range(1000):
        d[i, j]
"
>>>>>>> keydictretrievalprepared
python -m perf timeit -v -s "
from collections import defaultdict
d = {}
keys = [(i, j) for i in range(2000) for j in range(1000)]
for key in keys:
    d[key] = 1
" "
for key in keys:
    d[key]
"

Answer 4

Тестирование потребления памяти

Я написал небольшой скрипт для его проверки. Он имеет некоторые ограничения, хотя ключи сделаны из целых чисел, линейно распределенных (т.е. range(N)), мои выводы заключаются в следующем.

При трехуровневой вложенности, т. Е. dict[a][b][c] против 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

Открытые вопросы

• Почему это происходит?
• Будет ли это меняться с другими индексами, например, непоследовательные?

Сценарий

#!/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))