Ответ 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))