Как эффективно хранить пары чисел в наборе?

Question

В моей программе мне нужно хранить пары чисел в диапазоне [1, 10**5) в наборе и просматривать их много раз. Я могу добавить их в набор как кортежи:

seen = set()
seen.add((x, y))
(x, y) in seen  # True

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

Answer 1

Похоже, что объединение чисел - самый быстрый метод (примерно в 2 раза быстрее, чем использование кортежей в моем тесте):

seen = set()
seen.add(x*10**5+y)
x*10**5+y in seen  # True

PS, чтобы проверить это, я использовал %timeit в ipython для этих двух функций:

def f1():
    seen = set()
    for x in range(1000):
        for y in range(1000):
            seen.add((x, y))
            assert (x, y) in seen    

def f2():
    seen = set()
    for x in range(1000):
        for y in range(1000):
            seen.add(x*10**5+y)
            assert x*10**5+y in seen

Результаты:

In [2]: %timeit f1()
466 ms ± 1.08 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [3]: %timeit f2()
254 ms ± 1.63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 2

Хотя объединение чисел (x * 10 ** 5 + y) дает лучшую производительность, отладку проблем в вашем наборе может быть сложнее.Альтернатива, которая быстрее, чем наборы кортежей, но немного медленнее, чем числовые комбинации, заключалась бы в использовании словаря наборов:

def f3():
    seen = dict()
    for x in range(1000):
        for y in range(1000):
            seen.setdefault(x,set()).add(y)   # insert a new pair
            assert x in seen and y in seen[x] # check if pair in dictionary

Эта функция f3 () умножается на 0,284 с против f2 () на 0,248 (такне огромная потеря производительности).Это также дает вам дополнительное преимущество, заключающееся в возможности простого перечисления значений y для любого заданного значения x.

EDIT

Использование defaultdict действительно ускоряет его.Это даже быстрее, чем числовые комбинации (0,126) и в 4 раза быстрее, чем набор кортежей.

from collections import defaultdict
def f4():
    seen = defaultdict(set)
    for x in range(1000):
        for y in range(1000):
            seen[x].add(y)        # insert a new pair
            assert y in seen[x]   # check if pair in dictionary

Answer 3

Способ AFAIK OP в значительной степени самый эффективный. Устанавливает хэширование их содержимого, и это делает поиски постоянной сложности, в то время как кортеж, так как внутренняя структура маленькая и быстрая, нет ничего страшного в том, чтобы использовать frozenset (который можно хэшировать и, следовательно, может быть элементом набора) только для пары ценности. Поэтому, если у вас нет проблем с тем, что кортежи находятся в порядке (а не в порядке), вы хороши.