Проверка на существование в Словаре против множества в питоне

Question

Кажется, что проверка Dict ключей как набор несколько быстрее:

import random 
import string 
import timeit 

repeat = 3 
numbers = 1000 

def time(statement, _setup=None): 
    print min(
     timeit.Timer(statement, setup=_setup or setup).repeat(
      repeat, numbers)) 

random.seed('slartibartfast') 

# Integers 
length = 100000 
d = {} 
for _ in range(length): 
    d[random.randint(0, 10000000)] = 0 
s = set(d) 

setup = """from __main__ import s, d, length 
""" 

time('for i in xrange(length): check = i in d') 
time('for i in xrange(length): check = i in s') 

# Strings 
d = {} 
for _ in range(length): 
    d[''.join(random.choice(string.ascii_uppercase) for __ in range(16))] = 0 
s = set(d) 

test_strings= [] 
for _ in range(length): 
    test_strings.append(random.choice(string.ascii_uppercase) for __ in range(16)) 

setup = """from __main__ import s, d, length, test_strings 
""" 

time('for i in test_strings: check = i in d') 
time('for i in test_strings: check = i in s') 

печатает что-то вроде:

10.1242966769 
9.73939713014 
10.5156763102 
10.2767765061 

Это следует ожидать или случайный артефакт?

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

Редактировать: мои измерения действительно заставляют меня задуматься о базовой реализации, я не пытаюсь сохранить микросекунды, мне просто интересно - и да, если окажется, что базовая реализация действительно благоприятствует наборам, я мог бы создать набор этих ключей dict - или нет (я фактически исправляю старый код).

Answer 1

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

In [1]: import numpy as np 

In [2]: d = {i: True for i in np.random.random(1000)} 

In [3]: s = {i for i in np.random.random(1000)} 

In [4]: checks = d.keys()[:500] + list(s)[:500] 

In [5]: %timeit [k in d for k in checks] 
10000 loops, best of 3: 83 µs per loop 

In [6]: %timeit [k in s for k in checks] 
10000 loops, best of 3: 88.4 µs per loop 

In [7]: d = {i: True for i in np.random.random(100000)} 

In [8]: s = {i for i in np.random.random(100000)} 

In [9]: checks = d.keys()[:5000] + list(s)[:5000] 

In [10]: %timeit [k in d for k in checks] 
1000 loops, best of 3: 865 µs per loop 

In [11]: %timeit [k in s for k in checks] 
1000 loops, best of 3: 929 µs per loop 

Answer 2

Честно это сильно зависит от аппаратного обеспечения, операционной системы и объема данных/ограничений. В целом производительность будет почти одинаковой, пока вы не получите действительно большие размеры данных. Обратите внимание на несколько пробегов здесь, где dict делает немного лучше. При больших размерах данных данные внутренней реализации начинают преобладать над различиями, а на моей машине set имеет тенденцию к значительному улучшению.

Реальность в большинстве ситуаций дельта не имеет значения. Если вы действительно хотите улучшить производительность поиска, перейдите на операции уровня C с помощью cython или ctypes или воспользуйтесь библиотечными реализациями, предназначенными для больших размеров данных. Базовые типы Python не предназначены для производительности при достижении нескольких миллионов элементов.

>>> # With empty dict as setup in question 
>>> time('for i in xrange(length): check = i in d') 
2.83035111427 
>>> time('for i in xrange(length): check = i in s') 
2.87069892883 
>>> d = { random.random(): None for _ in xrange(100000) } 
>>> s = set(d) 
>>> time('for i in xrange(length): check = i in d') 
3.84766697884 
>>> time('for i in xrange(length): check = i in s') 
3.97955989838 
>>> d = { random.randint(0, 1000000000): None for _ in xrange(100000) } 
>>> s = set(d) 
>>> time('for i in xrange(length): check = i in d') 
3.96871709824 
>>> time('for i in xrange(length): check = i in s') 
3.62110710144 
>>> d = { random.randint(0, 1000000000): None for _ in xrange(10000000) } 
>>> s = set(d) 
>>> time('for i in xrange(length): check = i in d') 
10.6934559345 
>>> time('for i in xrange(length): check = i in s') 
5.7491569519