ключ в s против ключа не в скорости s - PullRequest
Новая
       19

ключ в s против ключа не в скорости s

0 голосов
/ 03 мая 2018

У меня есть этот код: 

s = set([5,6,7,8])

if key in s:
    return True

if key not in s:
    return False

Мне кажется, что теоретически оно не должно отличаться по времени, но я могу что-то упустить под капотом.

Есть ли какая-либо причина отдавать предпочтение одному другому по времени обработки или удобочитаемости?

Возможно, это пример:

«Преждевременная оптимизация - корень всего зла»?

Краткий ответ: Нет, без разницы. Да, возможно, преждевременная оптимизация.

ОК, я выполнил этот тест: 

import random
s = set([5,6,7,8])
for _ in range(5000000):
    s.add(random.randint(-100000,100000000))

def test_in():
    count = 0
    for _ in range(50000):
        if random.randint(-100000,100000000) in s:
            count += 1
    print(count)

def test_not_in():
    count = 0
    for _ in range(50000):
        if random.randint(-100000,100000000) not in s:
            count += 1
    print(count)

Когда я рассчитываю выходы: 

%timeit test_in()
10 loops, best of 3: 83.4 ms per loop

%timeit test_not_in()
10 loops, best of 3: 78.7 ms per loop

НО, эта небольшая разница, кажется, является признаком подсчета компонентов. В среднем 47500 «не входов», а только 2500 «входов». Если я изменю оба теста на прохождение, например ::1010* 

def test_in():
    for _ in range(50000):
        if random.randint(-100000,100000000) in s:
            pass

Результаты почти идентичны 

%timeit test_in()
10 loops, best of 3: 77.4 ms per loop

%timeit test_not_in()
10 loops, best of 3: 78.7 ms per loop

В этом случае моя интуиция подвела меня. Я думал, что высказывание it is not in the set могло бы добавить дополнительное время обработки. Когда я в дальнейшем расскажу о том, что делает hashmap, кажется очевидным, что это не может иметь место.

Ответы [ 2 ]

0 голосов
/ 03 мая 2018

Выполнение простого теста производительности в сеансе ipython с timeit подтверждает утверждение g.d.d.c. 

def one(k, s):
    if k in s:
        return True     

def two(k, s):
    if k not in s:
        return False     

s = set(range(1, 100))

%timeit -r7 -n 10000000 one(50, s)
## 83.7 ns ± 0.874 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

%timeit -r7 -n 10000000 two(50, s)
## 86.1 ns ± 1.11 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

Подобные оптимизации не принесут вам большой пользы, и, как было отмечено в комментариях, фактически уменьшат скорость, с которой вы будете выдавать исправления / улучшения / ... из-за плохой читабельности , Для такого типа низкоуровневого прироста производительности я бы рекомендовал изучить Cython или Numba .

0 голосов
/ 03 мая 2018

Разницы не должно быть. Время поиска в наборе постоянно. Вы хешируете запись, затем ищите ее в хэш-карте. Все ключи проверяются в одно и то же время и должны быть сопоставимы.

...