Самый быстрый способ обновить словарь в 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

Использование встроенной функции 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

Answer 4

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

assert(A[foo]==x)

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

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

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

Answer 7

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