Самый быстрый способ слияния двух: dicts против списков

Question

Я делаю некоторую индексацию, и памяти достаточно, но ЦП нет. Итак, у меня есть один огромный словарь, а затем меньший словарь, который я объединяю в больший:

big_dict = {"the" : {"1" : 1, "2" : 1, "3" : 1, "4" : 1, "5" : 1}}
smaller_dict = {"the" : {"6" : 1, "7" : 1}}
#after merging
resulting_dict = {"the" : {"1" : 1, "2" : 1, "3" : 1, "4" : 1, "5" : 1, "6" : 1, "7" : 1}}

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

Для пояснения, использование списка будет выглядеть так:

big_dict = {"the" : [1, 2, 3, 4, 5]}
smaller_dict = {"the" : [6,7]}
#after merging
resulting_dict = {"the" : [1, 2, 3, 4, 5, 6, 7]}

Примечание: причина, по которой я использую dict, вложенный в dict, а не набор, вложенный в dict, заключается в том, что JSON не позволяет мне делать json.dumps, потому что набор не является парами ключ / значение, (что касается библиотеки JSON) {"a", "series", "of", "keys"}

Кроме того, после выбора между использованием dict к списку, как бы я реализовал наиболее эффективный с точки зрения использования ЦП метод их слияния?

Я ценю помощь.

Answer 1

Это действительно зависит от того, что вы хотите сделать со значениями в ваших внутренних списках / словарях. Если при добавлении новой записи вы хотите, чтобы внутренний список имел только уникальные значения, реализация списка будет для намного медленнее для больших списков. Он масштабируется примерно в O (n), а не O (1) [средний регистр] для словарей.

Если вас не волнуют кратные значения в этих внутренних списках, то это ближе.

Я бы использовал словари, как у вас. Словари Python являются очень эффективными (говоря как кто-то, кто пытался реализовать структуры данных словаря в C для приложений реального времени).

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

big_dict = {"the" : [1, 2, 3, 4, 5]} # imagine we got this from JSON

for key, value in big_dict: 
    big_dict[key] = set(value)

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

В качестве альтернативы вы можете зарегистрировать кодеры и декодеры в JSON, чтобы вы могли выполнять это преобразование автоматически. Однако обычно я не беспокоюсь, когда проблема настолько мала и ограничена.

Итак, в вашем словарном подходе вы можете сделать:

for key, value in smaller_dict.items():
    if key in big_dict: 
        big_dict[key].update(value)
    else:
        big_dict[key] = value

Если вы хотите, чтобы big_dict только копировал словарь, используйте dict(value) вместо value в последней строке. Вы также можете использовать try: и except KeyError в последнем цикле, но if ... else намного быстрее (на моей машине, YMMV).

Answer 2

Хммм. Сначала я бы выбрал подход dict-of-dicts, так как Python имеет одну из наиболее точно настроенных реализаций dict, поэтому я очень сомневаюсь, что с помощью dict-of-lists вы можете добиться большего.

Что касается объединения диктов, этого должно быть достаточно:

for key, value in smaller_dict.iteritems():
    try:
        big_dict[key].update(value)
    except KeyError:
        big_dict[key] = dict(value)

Возможно, я бы также поэкспериментировал с подклассами json.JSONEncoder, чтобы иметь возможность сериализовать типы наборов:

class SetEncoder(json.JSONEncoder):
    def default(self, obj):
        if isinstance(obj, set):
            return dict.fromkeys(obj)
        return json.JSONEncoder.default(self, obj)

Однако этот последний метод может добавить некоторые издержки на стороне сериализации, и вам также потребуется преобразовать эти дикты в наборы при десериализации, либо путем создания подкласса json.JSONDecoder, либо сделав это самостоятельно на дополнительном этапе.

Answer 3

Любой хеш-контейнер будет лучше, чем список для такого рода вещей.

Я бы по-прежнему использовал set вместо dict; если у вас возникли проблемы с json.dumps, вы можете обойти это, преобразовав набор в dict, когда вы собираетесь сериализировать: И для того, чтобы вытащить их: set(the_dict.keys())
Это проще, чем копаться в регистрации поставщиков JSON.

А что касается слияния: merged_set = bigger_set.union(smaller_set)