Должен ли я хранить вычисления в переменной, если они будут часто использоваться?

Question

Если у меня есть функция, например, проверить, является ли list1 подсписком list2, какой вариант лучше:

Вариант 1:

def isSublist1(list1,list2):
  "This fuction checks if list1 is a sublist of list2."
  for i in range(len(list2)):
    part=list2[i:] # part is a list with all the elements from i to the end of list2
    if len(part)<len(list1):
      return False
    if list1==part[:len(list1)]: # if list1 is in the beginning of part 
      return True
  return False

или вариант 2:

def isSublist2(list1,list2):
  "This fuction checks if list1 is a sublist of list."
  for i in range(len(list2)):
    if len(list2[i:])<len(list1):
      return False
    if list1==list2[i:][:len(list1)]: # if list1 is in the beginning of list2[i:] (part)
      return True
  return False

В варианте 1 я использую переменную с именем part для хранения раздела list2, однако, в варианте 2 part не является переменной, раздел list2 вычисляется, когда это необходимо. Вариант 1 быстрее? Это тратит больше места?

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

Я хотел бы знать, какой из методов является лучшим в цикле: использовать переменную, чтобы избежать вычисления нескольких раз одинаковых вещей или нет. Зависит ли ответ от сложности и частоты расчета?

Answer 1

В дополнение к отличному ответу Патрика , давайте попробуем timeit с вашим реальным кодом:

>>> def isSublist1(list1,list2):                                                                                                                                                                                                                              
...   for i in range(len(list2)):                                                                                                                                                                                                                             
...     part=list2[i:]                                                                                                                                                                                                                                        
...     if len(part)<len(list1):                                                                                                                                                                                                                              
...       return False                                                                                                                                                                                                                                        
...     if list1==part[:len(list1)]:
...       return True                                                                                                                                                                                                                                         
...   return False                                                                                                                                                                                                                                            
... 
>>> def isSublist2(list1,list2):
...   for i in range(len(list2)):
...     if len(list2[i:])<len(list1):
...       return False
...     if list1==list2[i:][:len(list1)]:
...       return True
...   return False
... 
>>> list1=list(range(10000))
>>> list2=list(range(4000,4020))
>>> import timeit
>>> timeit.timeit('isSublist1(list2,list1)', globals=globals(),number=100)
6.420147094002459
>>> timeit.timeit('isSublist2(list2,list1)', globals=globals(),number=100)
12.455138996010646

Так что в моей системе количество времени, необходимое для вашей временной переменной, составляет примерно половинувремя, необходимое без него.

Я не знаю природу ваших списков и подсписков;Вы можете захотеть изменить то, что list1 и list2 должны быть хорошим отражением того, как будет использоваться ваш код, но, по крайней мере, с моей стороны, похоже, что сохранение этой временной переменной - очень хорошая идея.

КстатиДавайте сделаем еще один интересный эксперимент:

>>> def isSublist3(list1,list2):
...   ln = len(list1)
...   for i in range(len(list2)):
...     part=list2[i:]
...     if len(part)<ln:
...       return False
...     if list1==part[:ln]:
...       return True
...   return False
... 
>>> timeit.timeit('isSublist1(list2,list1)',globals=globals(),number=100); timeit.timeit('isSublist3(list2,list1)',globals=globals(),number=100)
6.549526696035173
6.481004184985068

Я запустил его еще несколько раз, чтобы посмотреть, что я получу:

6.470875242026523 6.463623657007702

6.151073662971612 5.787795798969455

5.685607994964812 5.655005165026523

6.439315696014091 6.372227535001002

Обратите внимание, что каждый раз длина в кеше занимает меньше времени, чем длина в не кешированном виде, хотя вы почти не получаете улучшения производительности, которое вы имеликэширование среза.

Обратите также внимание на то, что важно не делать слишком много выводов за один раз.Есть много других переменных, влияющих на время (в моем случае, совершенно очевидно, что-то случилось, что оно упало с 6,4 до 5,7 - в середине одного теста!), Так что если вы хотите придумать хорошее правилоВы можете рассчитывать на тестирование несколько раз, чтобы убедиться, что вы получите последовательные результаты.

Answer 2

Хранение локального лучше, потому что поиск, который делает Python, быстрее.Это даже окупается, чтобы хранить функции локально.

На вопросы производительности лучше всего отвечать по времени - вы можете измерить это, используя timeit :

import timeit

def noTempFunc():
    for _ in range(200):
        max([1,4,5,6])

def tempFunc():
    m = max
    for _ in range(200):
        m([1,4,5,6])


print(timeit.timeit(noTempFunc, number=1000))   #  0.055301458000030834
print(timeit.timeit(tempFunc, number=1000))     #  0.049811941999905684 : 11% faster

В этом случае max() глобального контекста имеет толькодля поиска один раз, и дальнейший поиск выполняется локально, что на ~ 11% быстрее на основе этих чисел.

Это окупается, если вы используете локальный m() несколько раз.

---

В вашем случае было бы разумно кэшировать len_list1 = len(list1) - так как он используется много времени и не меняется.

Чтобы сделать его более читабельным, вы можете рассмотреть:

def isSublist(list1, list2):
    """Checks if list2 is a sublist of list1"""
    len_part = len(list2)  # reused inside the list comp, only "calulated" once
    return any( x == list2 for x in (list1[i:i+len_part] 
                                     for i in range(len(list1)-len_part+1) ))


print(isSublist([1,2,3,4],[1]))
print(isSublist([1,2,3,4],[2,3]))
print(isSublist([1,2,3,4],[1,2,4]))
print(isSublist([1,2,3,4],[1,2,3,4]))

Вывод:

True
True
False
True

Поиски:

• any () && Как работает функция python any ()?
• Разделить список python на другие «подсписки», то есть меньшие списки

---

Ваша более быстрая версия с кэшированной длиной (на основе Скотт Мермельштейн ответ):

def isSublist1a(list1,list2): # cached length as well
    l1 = len(list1)
    for i in range(len(list2)):
        part=list2[i:]
        if len(part)<l1:
            return False
        if list1==part[:l1]:
            return True
    return False

list1=list(range(1000))
list2=list(range(400,420))
import timeit
print(timeit.timeit('isSublist1(list2,list1)', globals=globals(),number=1000))
print(timeit.timeit('isSublist1a(list2,list1)', globals=globals(),number=1000))
print(timeit.timeit('isSublist2(list2,list1)', globals=globals(),number=1000))

поставляет (2 исполнения):

0.08652938600062043  # cached part
0.08017484299944044  # cached part + cached list1 lenght - slightly faster
0.15090413599955355  # non-cached version

0.8882850420004615   # cached part
0.8294611960000111   # cached part + cached list1 lenght - slightly faster
1.5524438030006422   # non-cached version