Блог

Для класса, в котором я нахожусь, нас просят написать метод грубой силы для поиска 2 элементов в списках S1, S2, которые добавляют к указанному значению x. До сих пор у меня это было записано как таковое:

 @timing
def brute_force_nested(x, s1 : list, s2 : list) -> bool:
    for a in s2:
        for b in s1:
            if a   b == x:
                return True
    return False

@timing
def brute_force_inline(x, s1 : list, s2 : list) -> bool:
    return bool([ (a,b) for a in s2 for b in s1 if a   b == x ])
 

Но когда я запускаю их в терминале, я получаю очень большую разницу во времени:

 >>> brute_force_nested(5123, S1, S2):

func:brute_force_nested took: 0.007085800170898438 sec and gave: True

>>>func:brute_force_inline(5123, S1, S2)

func:brute_force took: 3.0208868980407715 sec and gave: True
 

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

Циклы действительно равны, но не условие для его разрыва. В первом вложенном цикле код останавливается при достижении первого равенства. Во втором все тесты вычисляются до тех пор, пока не будут исчерпаны все комбинации.

Эквивалентом первого цикла с синтаксисом понимания было бы использование генератора и any , который остановится при достижении первого истинного значения

 return any((a b==x for a in s2 for b in s1))
 

Это потому, что вы только перебираете списки в первом fuinction и возвращаетесь к первому значению. Во-вторых, вы создаете список, а затем оцениваете истинное значение этого списка. Чтобы они были сопоставимы, вам необходимо использовать any и понимание генератора.

 def brute_force_inline(x, s1 : list, s2 : list) -> bool:
    return any(a   b == x for a in s2 for b in s1)
 

P.S Технически оба ваших подхода представляют собой вложенные циклы, один из которых просто выполняется с использованием понимания.

Это также можно сделать более эффективно, используя itertools.product :

 from itertools import product

def brute_force_inline(x, s1 : list, s2 : list) -> bool:
    return any(sum(ab) == x for ab in product(s2, s1))