Are list-comprehensions and functional functions faster than for loops

Question

In terms of performance in Python  is a list-comprehension  or functions like map    filter   and reduce   faster than a for loop  Why  technically  they run in a C speed  while the for loop runs in the python virtual machine speed    Suppose that in a game that I m developing I need to draw complex and huge maps using for loops  This question would be definitely relevant  for if a list-comprehension  for example  is indeed faster  it would be a much better option in order to avoid lags  Despite the visual complexity of the code

User · Answer

You ask specifically about map    filter   and reduce    but I assume you want to know about functional programming in general  Having tested this myself on the problem of computing distances between all points within a set of points  functional programming  using the starmap function from the built-in itertools module  turned out to be slightly slower than for-loops  taking 1 25 times as long  in fact   Here is the sample code I used   import itertools  time  math  random  class Point      def   init   self x y           self x  self y   x  y  point set    Point 0  0   Point 0  1   Point 0  2   Point 0  3   n points   100 pick val   lambda   10   random random   - 5 large set    Point pick val    pick val    for   in range n points         the distance function f dist   lambda x0  x1  y0  y1  math sqrt  x0 - x1     2    y0 - y1     2        go through each point  get its distance from all remaining points  f pos   lambda p1  p2   p1 x  p2 x  p1 y  p2 y   extract dists   lambda x  itertools starmap f dist                             itertools starmap f pos                             itertools combinations x  2     print  Distances    list extract dists point set     t0 f   time time   list extract dists large set   dt f   time time   - t0 f   Is the functional version faster than the procedural version   def extract dists procedural pts       n pts   len pts      l              for k p1 in range n pts - 1           for k p2 in range k p1  n pts               l append  pts k p1  x - pts k p2  x     2                         pts k p1  y - pts k p2  y     2      return l  t0 p   time time   list extract dists procedural large set          using list   on the assumption that       it eats up as much time as in the functional version  dt p   time time   - t0 p  f vs p   dt p   dt f if f vs p  gt   1 0      print  Time benefit of functional progamming    f vs p              times as fast for   n points   points   else      print  Time penalty of functional programming    1   f vs p              times as slow for   n points   points

User · Answer

I have managed to modify some of  alpiii s code and discovered that List comprehension is a little faster than for loop  It might be caused by int    it is not fair between list comprehension and for loop   from functools import reduce import datetime  def time it func  numbers   args       start t   datetime datetime now       for i in range numbers           func args 0       print  datetime datetime now  -start t   def square sum1 numbers       return reduce lambda sum  next  sum next next  numbers  0   def square sum2 numbers       a          for i in numbers          a append i 2      a   sum a      return a  def square sum3 numbers       sqrt   lambda x  x x     return sum map sqrt  numbers    def square sum4 numbers       return sum  i i for i in numbers     time it square sum1  100000   1  2  5  3  1  2  5  3   time it square sum2  100000   1  2  5  3  1  2  5  3   time it square sum3  100000   1  2  5  3  1  2  5  3   time it square sum4  100000   1  2  5  3  1  2  5  3     0 00 00 101122  Reduce  0 00 00 089216  For loop  0 00 00 101532  Map  0 00 00 068916  List comprehension

User · Answer

I wrote a simple script that test the speed and this is what I found out  Actually for loop was fastest in my case  That really suprised me  check out bellow  was calculating sum of squares    from functools import reduce import datetime   def time it func  numbers   args       start t   datetime datetime now       for i in range numbers           func args 0       print  datetime datetime now  -start t   def square sum1 numbers       return reduce lambda sum  next  sum next  2  numbers  0    def square sum2 numbers       a   0     for i in numbers          i   i  2         a    i     return a  def square sum3 numbers       sqrt   lambda x  x  2     return sum map sqrt  numbers    def square sum4 numbers       return sum  int i   2 for i in numbers      time it square sum1  100000   1  2  5  3  1  2  5  3   time it square sum2  100000   1  2  5  3  1  2  5  3   time it square sum3  100000   1  2  5  3  1  2  5  3   time it square sum4  100000   1  2  5  3  1  2  5  3     0 00 00 302000  Reduce 0 00 00 144000  For loop 0 00 00 318000  Map 0 00 00 390000  List comprehension

User · Answer

The following are rough guidelines and educated guesses based on experience  You should timeit or profile your concrete use case to get hard numbers  and those numbers may occasionally disagree with the below   A list comprehension is usually a tiny bit faster than the precisely equivalent for loop  that actually builds a list   most likely because it doesn t have to look up the list and its append method on every iteration  However  a list comprehension still does a bytecode-level loop    gt  gt  gt  dis dis  lt the code object for   x for x in range 10    gt    1           0 BUILD LIST               0              3 LOAD FAST                0   0          gt  gt     6 FOR ITER                12  to 21               9 STORE FAST               1  x              12 LOAD FAST                1  x              15 LIST APPEND              2             18 JUMP ABSOLUTE            6         gt  gt    21 RETURN VALUE   Using a list comprehension in place of a loop that doesn t build a list  nonsensically accumulating a list of meaningless values and then throwing the list away  is often slower because of the overhead of creating and extending the list  List comprehensions aren t magic that is inherently faster than a good old loop   As for functional list processing functions  While these are written in C and probably outperform equivalent functions written in Python  they are not necessarily the fastest option  Some speed up is expected if the function is written in C too  But most cases using a lambda  or other Python function   the overhead of repeatedly setting up Python stack frames etc  eats up any savings  Simply doing the same work in-line  without function calls  e g  a list comprehension instead of map or filter  is often slightly faster      Suppose that in a game that I m developing I need to draw complex and huge maps using for loops  This question would be definitely relevant  for if a list-comprehension  for example  is indeed faster  it would be a much better option in order to avoid lags  Despite the visual complexity of the code     Chances are  if code like this isn t already fast enough when written in good non- optimized  Python  no amount of Python level micro optimization is going to make it fast enough and you should start thinking about dropping to C  While extensive micro optimizations can often speed up Python code considerably  there is a low  in absolute terms  limit to this  Moreover  even before you hit that ceiling  it becomes simply more cost efficient  15  speedup vs  300  speed up with the same effort  to bite the bullet and write some C

User · Answer

I modified  Alisa s code and used cProfile to show why list comprehension is faster   from functools import reduce import datetime  def reduce  numbers       return reduce lambda sum  next  sum   next   next  numbers  0   def for loop numbers       a          for i in numbers          a append i 2      a   sum a      return a  def map  numbers       sqrt   lambda x  x x     return sum map sqrt  numbers    def list comp numbers       return sum  i i for i in numbers     funcs             reduce           for loop          map           list comp            if   name         main            1  2  5  3  1  2  5  3      import cProfile     for f in funcs          print       25          print  Profiling    f   name            print       25          pr   cProfile Profile           for i in range 10  6               pr runcall f   1  2  5  3  1  2  5  3           pr create stats           pr print stats     Here s the results                             Profiling  reduce                                     11000000 function calls in 1 501 seconds     Ordered by  standard name     ncalls  tottime  percall  cumtime  percall filename lineno function    1000000    0 162    0 000    1 473    0 000 profiling py 4 reduce     8000000    0 461    0 000    0 461    0 000 profiling py 5  lt lambda gt     1000000    0 850    0 000    1 311    0 000  built-in method  functools reduce    1000000    0 028    0 000    0 028    0 000  method  disable  of   lsprof Profiler  objects                              Profiling  for loop                                    11000000 function calls in 1 372 seconds     Ordered by  standard name     ncalls  tottime  percall  cumtime  percall filename lineno function    1000000    0 879    0 000    1 344    0 000 profiling py 7 for loop    1000000    0 145    0 000    0 145    0 000  built-in method builtins sum    8000000    0 320    0 000    0 320    0 000  method  append  of  list  objects    1000000    0 027    0 000    0 027    0 000  method  disable  of   lsprof Profiler  objects                              Profiling  map                                     11000000 function calls in 1 470 seconds     Ordered by  standard name     ncalls  tottime  percall  cumtime  percall filename lineno function    1000000    0 264    0 000    1 442    0 000 profiling py 14 map     8000000    0 387    0 000    0 387    0 000 profiling py 15  lt lambda gt     1000000    0 791    0 000    1 178    0 000  built-in method builtins sum    1000000    0 028    0 000    0 028    0 000  method  disable  of   lsprof Profiler  objects                              Profiling  list comp                                    4000000 function calls in 0 737 seconds     Ordered by  standard name     ncalls  tottime  percall  cumtime  percall filename lineno function    1000000    0 318    0 000    0 709    0 000 profiling py 18 list comp    1000000    0 261    0 000    0 261    0 000 profiling py 19  lt listcomp gt     1000000    0 131    0 000    0 131    0 000  built-in method builtins sum    1000000    0 027    0 000    0 027    0 000  method  disable  of   lsprof Profiler  objects     IMHO    reduce and map are in general pretty slow  Not only that  using sum on the iterators that map returned is slow  compared to suming a list for loop uses append  which is of course slow to some extent list-comprehension not only spent the least time building the list  it also makes sum much quicker  in contrast to map

User · Answer

Adding a twist to Alphii answer  actually the for loop would be second best and about 6 times slower than map  from functools import reduce import datetime   def time it func  numbers   args       start t   datetime datetime now       for i in range numbers           func args 0       print  datetime datetime now  -start t   def square sum1 numbers       return reduce lambda sum  next  sum next  2  numbers  0    def square sum2 numbers       a   0     for i in numbers          a    i  2     return a  def square sum3 numbers       a   0     map lambda x  a x  2  numbers      return a  def square sum4 numbers       a   0     return  a i  2 for i in numbers   time it square sum1  100000   1  2  5  3  1  2  5  3   time it square sum2  100000   1  2  5  3  1  2  5  3   time it square sum3  100000   1  2  5  3  1  2  5  3   time it square sum4  100000   1  2  5  3  1  2  5  3     Main changes have been to eliminate the slow sum calls  as well as the probably unnecessary int   in the last case  Putting the for loop and map in the same terms makes it quite fact  actually  Remember that lambdas are functional concepts and theoretically shouldn t have side effects  but  well  they can have side effects like adding to a  Results in this case with Python 3 6 1  Ubuntu 14 04  Intel R  Core TM  i7-4770 CPU   3 40GHz  0 00 00 257703  Reduce 0 00 00 184898  For loop 0 00 00 031718  Map 0 00 00 212699  List comprehension

User · Answer

If you check the info on python org  you can see this summary   Version Time  seconds  Basic loop 3 47 Eliminate dots 2 45 Local variable  amp  no dots 1 79 Using map function 0 54   But you really should read the above article in details to understand the cause of the performance difference   I also strongly suggest you should time your code by using timeit   At the end of the day  there can be a situation where  for example  you may need to break out of for loop when a condition is met  It could potentially be faster than finding out the result by calling map

[python] Are list-comprehensions and functional functions faster than "for loops"?

Examples related to python

Examples related to performance

Examples related to for-loop

Examples related to list-comprehension

Examples related to map-function