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

Question

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

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}} 

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

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

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]} 

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

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

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

Answer 1

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

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

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) 

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

Answer 2

Это действительно зависит от того, что вы хотите делать со значениями в ваших внутренних списках/словарях. Если при добавлении новой записи вы хотите, чтобы внутренний список имел только уникальные значения, тогда реализация списка будет много медленнее для больших списков. Он масштабируется примерно на 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 3

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

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

И как для слияния: merged_set = bigger_set.union(smaller_set)