что быстрее: объединение списков или диктов в python?

Question

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

Теперь дело в том, что я могу выбрать любой из них, но мне интересно, будет ли слияние разборов быстрее, поскольку все это в памяти? Или это всегда будет O (n), где n - размер меньшего списка.

Причина, по которой я спрашивал о dicts, а не множествах, заключается в том, что я не могу преобразовать набор в json, потому что это приводит к {key1, key2, key3}, а json нужна пара ключ / значение, поэтому я использую dict поэтому json dumps возвращает {key1: 1, key2: 1, key3: 1}. Да, это расточительно, но если это окажется быстрее, тогда я в порядке.

Редактировать: Мой вопрос заключается в разнице в использовании dict и list для слияния, у меня изначально и по ошибке был dict и set list.

dict1 = {"the": {"1": 1, "3": 1, "10": 1}

dict2 = {"the": {"11": 1, "13": 1}}

после слияния

dict3 = {"the": {"1": 1, "3": 1, "10": 1, "11": 1, "13": 1}

Answer 1

Если вы ищете дубликаты, наборы очень и очень быстрые.

>>> x = set(range(1000000,2000000))
>>> y = set(range(1900000,2900000))

the following happened in ~0.020s  
>>> z = set.intersection(x,y)
>>> len(z)
100000

Что касается вывода в JSON, просто преобразовать в список ...

json_encode(list(z))

Answer 2

Dicts и sets будут такими же быстрыми (и O(N), как вы предполагаете). Списки, которые вы упоминаете только в заголовке своего Q, но не в тексте, могут быть медленнее, в зависимости от того, что вы подразумеваете под «объединением».

Принимая во внимание требования json для нисходящего потока, в общем случае, дикты со значениями, установленными в 1, будут самыми быстрыми - не для объединения, а для сериализации JSON.

Answer 3

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

Answer 4

Как сказал Майкл, вероятно, проще всего использовать модуль timeit и убедиться в этом. Это очень легко сделать:

import timeit
def test():
    # do your thing here
    # including conversion to json
    pass

result = timeit.repeat(test, repeat=10, number=10000)
print '{0:.2}s per 10000 test runs.'.format(min(result))

Надеюсь, это поможет.

Answer 5

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

Моя внутренняя реакция такова: если вы ищете ключи, словарь будет быстрее. Но как вы будете бороться с дублированием?