Вложенный цикл или «в», что быстрее? - PullRequest
Новая
       7

Вложенный цикл или «в», что быстрее?

0 голосов
/ 05 июня 2018

Я новичок в Python, изучал некоторые основные проблемы кодирования и надеялся, что кто-нибудь сможет объяснить, какой из следующих фрагментов кода будет работать быстрее.Смысл в том, чтобы увидеть, есть ли в списке пары целых чисел, которые суммируют до 100: 

list = [1,2,3,99,5]
for i in list:
    for j in list:
       if i + j == 100:
          return True

или: 

list = [1,2,3,99,5]
for i in list: 
    diff = 100 - i 
    if diff in list:
        return True

1 Ответ

0 голосов
/ 05 июня 2018

Бенчмарк

Этот самодельный рандомизированный тест демонстрирует, что решение, использующее in, значительно быстрее в большинстве случаев.Я не исследовал, но я сталкивался с некоторыми прогонами, когда решение с вложенными циклами for было немного быстрее при работе с размером выборки. 

import time, random

def time_it(f, rep=100000):
    sample = [[random.randint(0, 100) for _ in range(20)] for _ in range(rep // 100)]

    start = time.time()
    for i in range(rep):
        f(sample[i % len(sample)])
    return (time.time() - start)

def nested_for(lst):
    for i in lst:
        for j in lst:
            if i + j == 100:
                return True

def nested_in(lst):
    for i in lst:
        diff = 100 - i
        if diff in lst:
            return True

print('for:', time_it(nested_for))
print('in:', time_it(nested_in))

Вывод 

for: 0.7093353271484375
in: 0.24253296852111816

Удалениеприсваивание j на каждой итерации, вероятно, устраняет большие издержки в решении с in.

Улучшение

Хотя обратите внимание, что оба решения O (n 2 ) .Вы можете достичь O (n) , используя set.Так как set хэширует свои элементы, поиск составляет O (1) . 

def contains_diff(lst):
    elements = set(lst)
    return any(100 - i in elements for i in elements)

print(contains_diff([1, 2, 3, 99])) # True
print(contains_diff([1, 2, 3])) # False

Интересно, что если вы сравните тестирование выше, оно будет в целом медленнее, чем решение in,Это связано с тем, что вероятность in быстрого нахождения суммы 100 в рандомизированном списке относительно высока.Если вы позволите разнице, которую вы хотите найти, нарастать, тогда затраты на построение set быстро компенсируются скоростью set поиска.

Sidenote

Как sidenote, выне следует использовать list в качестве имени переменной, поскольку оно перезаписывает встроенную list.

...