Кортежи Python как ключи медленные?

Question

Я пытаюсь реализовать быстрый поиск отсортированных кортежей в словаре;что-то, что отвечает на вопрос «Имеет ли кортеж (3,8) ассоциированное значение, и если да, то что это?».Пусть целые числа в кортежах будут связаны снизу 0 и сверху max_int.

Я пошел дальше и использовал диктант Python, но обнаружил, что он довольно медленный.Другим подходом к этой проблеме было бы создание списка T с max_int (в основном пустыми) диктовками, и для каждого кортежа (3,8) положить T [3] [8] = значение.Я думаю, что это именно тот подход, который Python использует с помощью dicts, но последний здесь примерно в 30 раз (!) Быстрее.

Кроме того, хотя и уродливо (тем более что я сейчасреализовать 3-кортежа), поэтому я очень признателен за некоторые подсказки.

Для справки. Вот код, который я использовал для получения времени:

import numpy as np
import time

# create a bunch of sorted tuples
num_tuples = 10
max_int = 100
a = np.random.rand(num_tuples,2) * max_int
a = a.astype(int)
for k in xrange(len(a)):
    a[k] = np.sort(a[k])

# create dictionary with tuples as keys
d = {}
for t in a:
    d[tuple(t)] = 42

print d

# do some lookups
m = 100000
start_time = time.time()
for k in xrange(m):
    (3,8) in d.keys()
elapsed = time.time() - start_time
print elapsed

# now create the bucket-list structure mentioned above
t = [{} for k in xrange(max_int)]
for k in xrange(len(a)):
    t[a[k][0]][a[k][1]] = 42

print t

# do some lookups
m = 10000
start_time = time.time()
for k in xrange(m):
    8 in t[3].keys()
elapsed = time.time() - start_time
print elapsed

Answer 1

Вот точные временные результаты с Python 2.7:

>>> %timeit (3, 8) in d.keys()  # Slow, indeed
100000 loops, best of 3: 9.58 us per loop

>>> %timeit 8 in t[3].keys()  # Faster
1000000 loops, best of 3: 246 ns per loop

>>> %timeit (3, 8) in d  # Even faster!
10000000 loops, best of 3: 117 ns per loop

>>> %timeit 8 in t[3]  # Slightly slower
10000000 loops, best of 3: 127 ns per loop

Они показывают, что стандартный (3, 8) in d (без .keys() построения списка) на самом деле чуть быстрее (менее общего) подхода 8 in t[3], и в два раза быстрее по сравнению с относительно быстрым 8 in t[3].keys() вопроса. Это .keys / no .keys отличие связано с тем, что (3, 8) in d.keys() создает список (в Python 2) ключей, а затем ищет в этом списке (3, 8), что намного медленнее, чем поиск (3, 8) в хеш-таблице словаря d.

Как отмечается в комментариях, результаты синхронизации отличаются в Python 3: keys() в Python 3 имеет быстрый in тест, поскольку вместо keys() возвращается представление о ключах, так что оператор in может используйте хеш-таблицу соответствующего словаря.

Разница в скорости в исходном вопросе проистекает из того факта, что d.keys() создает относительно длинный список по сравнению с t[3].keys().

PS: функция %timeit обеспечивается превосходной оболочкой IPython . Оригинальная программа может быть выполнена через IPython с %run prog.py.

Answer 2

Вы тестируете на разные значения.В словарной версии есть поиск на 100 000 ключей, тогда как в структуре списков ведется поиск только на 10 000 ключей.

Кроме того, этот фрагмент кода замедляет работу: (3,8) in d.keys()если вы только что написали (3,8) in d, то время поиска в обеих версиях было бы весьма схожим, а разница незначительной.Попробуйте этот измененный тест и убедитесь сами:

import numpy as np
import time

# create a bunch of sorted tuples
num_tuples = 10
max_int = 100
a = np.random.rand(num_tuples,2) * max_int
a = a.astype(int)
for k in xrange(len(a)):
    a[k] = np.sort(a[k])

# create dictionary with tuples as keys
d = {}
for t in a:
    d[tuple(t)] = 42

# do some lookups
m = 100000
start_time = time.time()
for k in xrange(m):
    if (3,8) in d:
        pass

elapsed = time.time() - start_time
print elapsed

# now create the bucket-list structure mentioned above
t = [{} for k in xrange(max_int)]
for k in xrange(len(a)):
    t[a[k][0]][a[k][1]] = 42

# do some lookups
m = 100000
start_time = time.time()
for k in xrange(m):
    if 8 in t[3]:
        pass

elapsed = time.time() - start_time
print elapsed

Причиной наблюдаемого поведения является то, что и (3,8) in d.keys(), и 8 in t[3].keys() каждый раз создают новый временный список ключей, но вторая версия создаетболее короткие списки.Если бы вы просто использовали идиому key in dictionary, временные списки больше не создаются, и производительность начинает выглядеть одинаково для обоих подходов.

Я бы пошел с первой версией, гораздо проще, легче для чтенияи понимать, идиоматично - и при правильном использовании работает так же хорошо, как и вторая версия.

Answer 3

Немного странно сравнивать скорость от (a, b) in d до b in t[a], поскольку последняя предполагает, что a должно присутствовать.

В любом случае первый путь всегда должен быть быстрее. Обе версии имеют как a , так и b . Первый имеет дополнительные накладные расходы на выделение кортежа и его хеширование. Однако второй способ выполняет два отдельных поиска в словаре.