Самый быстрый способ обновить словарь в python

Question

У меня есть словарь A и возможная запись foo. Я знаю, что A [foo] должен быть равен x, но я не знаю, было ли A [foo] уже определено. В любом случае, если A [foo] был определен, это означает, что оно уже имеет правильное значение.

Это быстрее выполнить:

if foo not in A.keys(): 
    A[foo]=x 

или просто обновить

A[foo]=x 

потому что к тому времени, когда компьютер нашел запись Foo, он может и обновить его. Хотя, если нет, мне нужно будет дважды вызвать хеш-таблицу?

Спасибо.

Answer 1

Просто добавьте элементы в словарь, не проверяя их существование. Я добавил 100 000 предметов в словарь, используя 3 разных метода, и приурочил его к модулю timeit.

1. if k not in d: d[k] = v
2. d.setdefault(k, v)
3. d[k] = v

Вариант 3 был самым быстрым, но не намного.

[На самом деле, я также пробовал if k not in d.keys(): d[k] = v, но это было медленнее в 300 раз (каждая итерация построила список ключей и выполнила линейный поиск). Это сделало мои тесты настолько медленными, что я оставил их здесь.]

Вот мой код:

import timeit 

setup = """ 
import random 
random.seed(0) 
item_count = 100000 
# divide key range by 5 to ensure lots of duplicates 
items = [(random.randint(0, item_count/5), 0) for i in xrange(item_count)] 
""" 
in_dict = """ 
d = {} 
for k, v in items: 
    if k not in d: 
     d[k] = v 
""" 
set_default = """ 
d = {} 
for k, v in items: 
    d.setdefault(k, v) 
""" 
straight_add = """ 
d = {} 
for k, v in items: 
    d[k] = v 
""" 
print 'in_dict  ', timeit.Timer(in_dict, setup).timeit(1000) 
print 'set_default ', timeit.Timer(set_default, setup).timeit(1000) 
print 'straight_add ', timeit.Timer(straight_add, setup).timeit(1000) 

И результаты:

in_dict  13.090878085 
set_default 21.1309413091 
straight_add 11.4781760635 

Примечание: Это все довольно бессмысленно. Мы ежедневно получаем много вопросов о том, какой самый быстрый способ выполнить x или y в Python. В большинстве случаев ясно, что вопрос задавался до того, как возникли проблемы с производительностью. Мой совет? Сосредоточьтесь на написании самой четкой программы, которую вы можете написать, и если она слишком медленная, профилируйте ее и оптимизируйте там, где это необходимо. По моему опыту, я почти никогда не занимаюсь профилем и оптимизацией шага. Из описания проблемы кажется, что хранилище словарей не будет основной бутылочной горловиной в вашей программе.

Answer 2

if foo not in A.keys(): 
    A[foo] = x 

очень медленно, потому что A.keys() создает список, который должен быть проанализирован в O (N).

if foo not in A: 
    A[foo] = x 

быстрее, потому что это занимает O (1), чтобы проверить, существует ли foo в A.

A[foo] = x 

еще лучше, потому что у вас уже есть объект x и вы просто добавить (если он уже не существует) указатель на него в A.

Answer 3

A.setdefault(foo, x) но я не уверен, что это быстрее, чем if not A.has_key(foo): A[foo] = x. Должны быть проверены.

Answer 4

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

Answer 5

foo not in A.keys() 

будет в Python 2 создать новый список с помощью клавиш, а затем выполнить линейный поиск на нем. Это гарантированно будет медленнее (хотя я в основном возражаю против него, потому что есть альтернативы, которые быстрее и более элегантные/идиоматические).

A[foo] = x 

и

if foo not in A: 
    A[foo] = x 

различны, если A[foo] уже существует, но is not x. Но так как ваше «знать» A[foo] будет x, не имеет значения семантически. Во всяком случае, оба будут хорошими по производительности (трудно сказать без бенчмаркинга, хотя я бы сказал, что if занимает гораздо больше времени, чем копирование указателя).

Так что ответ в любом случае ясен: выберите тот, который много более короткий код и так же ясно (первый).

Answer 6

Если вы «знаете», что A [Foo] «должно быть» равным х, то я бы просто сделать:

assert(A[foo]==x) 

, который сообщит вам, если ваше предположение неверно!

Answer 7

Использование встроенной функции update() еще быстрее. Я немного подкрепил пример Стивена Румбальского, и он показывает, как update() является самым быстрым. Существует как минимум два способа его использования (со списком кортежей или с другим словарем). Первый (показан ниже как update_method1) является самым быстрым. Обратите внимание, что я также изменил еще пару вещей о примере Стивена Румбальского. Мои словари будут иметь ровно 100 000 ключей, но новые значения имеют 10% -ный шанс не нуждаться в обновлении. Эта вероятность избыточности будет зависеть от характера данных, которые вы обновляете в своем словаре. Во всех случаях на моей машине мой update_method1 был самым быстрым.

import timeit 

setup = """ 
import random 
random.seed(0) 
item_count = 100000 
existing_dict = dict([(str(i), random.randint(1, 10)) for i in xrange(item_count)]) 
items = [(str(i), random.randint(1, 10)) for i in xrange(item_count)] 
items_dict = dict(items) 
""" 
in_dict = """ 
for k, v in items: 
    if k not in existing_dict: 
     existing_dict[k] = v 
""" 
set_default = """ 
for k, v in items: 
    existing_dict.setdefault(k, v) 
""" 
straight_add = """ 
for k, v in items: 
    existing_dict[k] = v 
""" 
update_method1 = """ 
existing_dict.update(items) 
""" 
update_method2 = """ 
existing_dict.update(items_dict) 
""" 
print 'in_dict  ', timeit.Timer(in_dict, setup).timeit(1000) 
print 'set_default ', timeit.Timer(set_default, setup).timeit(1000) 
print 'straight_add ', timeit.Timer(straight_add, setup).timeit(1000) 
print 'update_method1 ', timeit.Timer(update_method1, setup).timeit(1000) 
print 'update_method2 ', timeit.Timer(update_method2, setup).timeit(1000) 

Этот код привел к следующим результатам:

in_dict   10.6597309113 
set_default  19.3389420509 
straight_add 11.5891621113 
update_method1 7.52693581581 
update_method2 9.10132408142