Сроки функции

Question

Внимание, это немного рекурсивно;)

Я ответил на этот вопрос: Python: Как я могу получить все элементы в списке до самого длинного элемента?

И после того, как я представил там, где еще один ответ, который должен быть быстрее (автор думал, и я тоже).Я пытался найти время для разных решений, но решение, которое должно быть медленнее, было на самом деле быстрее.Это заставило меня думать, что с моим кодом что-то не так.Или это так?

import string
import random
import time

def solution1(lst):
  return lst[:lst.index(max(lst, key=len))]

def solution2(lst):
  idx, maxLenStr = max(enumerate(lst), key=lambda x:len(x[1]))
  return lst[:idx]

# Create a 100000 elements long list that contains
# random data and random element length
lst = []
for i in range(100000):
  s = "".join([random.choice(string.letters+string.digits) for x in range(1, random.randint(1,50))])
  lst.append(s)

# Time the first solution
start = time.time()
solution1(lst)
print 'Time for solution1', (time.time() - start)

# Time the second solution
start = time.time()
solution2(lst)
print 'Time for solution2', (time.time() - start)

Обновление

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

Answer 1

Кажется, что первая версия делает намного меньше вызовов, чем вторая.

Кстати, это, вероятно, еще один пример того, как идиоматический, простой код часто также быстрее в Python

>>> dis.dis(solution1)
  2           0 LOAD_FAST                0 (lst)
              3 LOAD_FAST                0 (lst)
              6 LOAD_ATTR                0 (index)
              9 LOAD_GLOBAL              1 (max)
             12 LOAD_FAST                0 (lst)
             15 LOAD_CONST               1 ('key')
             18 LOAD_GLOBAL              2 (len)
             21 CALL_FUNCTION          257
             24 CALL_FUNCTION            1
             27 SLICE+2             
             28 RETURN_VALUE        
>>> dis.dis(solution2)
  2           0 LOAD_GLOBAL              0 (max)
              3 LOAD_GLOBAL              1 (enumerate)
              6 LOAD_FAST                0 (lst)
              9 CALL_FUNCTION            1
             12 LOAD_CONST               1 ('key')
             15 LOAD_CONST               2 (<code object <lambda> at 000000000422BEB8, file "<input>", line 2>)
             18 MAKE_FUNCTION            0
             21 CALL_FUNCTION          257
             24 UNPACK_SEQUENCE          2
             27 STORE_FAST               1 (idx)
             30 STORE_FAST               2 (maxLenStr)

  3          33 LOAD_FAST                0 (lst)
             36 LOAD_FAST                1 (idx)
             39 SLICE+2             
             40 RETURN_VALUE 

Answer 2

Лямбда обходится дороже во втором решении.

Я профилировал и коды, и данные профиля, похоже, первое решение быстрее

Как и вики сказал бы, что вызов функции является дорогостоящим, и во втором решении вызовы функций lambda и len делают его работу медленнее

Обратите внимание, я сократил список до длины 1000 элементов

>>> cProfile.run('solution1(lst)')
         5 function calls in 0.000 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <pyshell#305>:1(solution1)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {max}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'index' of 'list' objects}


>>> cProfile.run('solution2(lst)')
         2004 function calls in 0.012 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.012    0.012 <pyshell#306>:1(solution2)
     1000    0.006    0.000    0.009    0.000 <pyshell#306>:2(<lambda>)
        1    0.000    0.000    0.012    0.012 <string>:1(<module>)
     1000    0.003    0.000    0.003    0.000 {len}
        1    0.003    0.003    0.012    0.012 {max}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Answer 3

Время выглядит хорошо.

solution1 может быть быстрее, потому что он не использует лямбда-выражения, поэтому ему не нужно вызывать код Python в цикле. Он повторяет список дважды, но это не имеет большого значения.