Timing functions

Question

Warning, this is a bit recursive ;)

I answered this question: Python:How can i get all the elements in a list before the longest element?

And after I submitted there where another answer that should be faster (the author thought, and so did I). I tried to time the different solutions but the solution that should be slower was actually faster. This made me think there is something wrong with my code. Or is it?

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)

Update

Before anyone mentions why I put this is as a new question. The question is more about me learning how to measure execution time...

Answer 1

The lambda is costing dearer in the second solution.

I profiled both the codes and by the profile data, it looks, the first solution is faster

As the wiki would say function call is costly and in the second solution, the lambda and the len function calls are making it run slower

Please note, I have trimmed down the list to a length of 1000 elements

>>> 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 2

It seems first version is making many less calls than the second one.

btw, This is probably another example of how idiomatic, simple code is often also the faster one in 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 3

The timing looks ok.

solution1 can be faster, because it doesn't use lambdas, so it doesn't need to call Python code in the loop. It does iterate the list twice, but it's not a big deal.