8

Does using Higher Order Functions & Lambdas make running time & memory efficiency better or worse? For example, to multiply all numbers in a list :

nums = [1,2,3,4,5]
prod = 1
for n in nums:
    prod*=n

vs

prod2 = reduce(lambda x,y:x*y , nums)

Does the HOF version have any advantage over the loop version other than it's lesser lines of code/uses a functional approach?

EDIT:

I am not able to add this as an answer as I don't have the required reputation. I tied to profile the loop & HOF approach using timeit as suggested by @DSM

def test1():         
    s= """
    nums = [a for a in range(1,1001)] 
    prod = 1 
    for n in nums:
        prod*=n
    """            
    t = timeit.Timer(stmt=s)
    return t.repeat(repeat=10,number=100)    

def test2():
    s="""
    nums = [a for a in range(1,1001)]     
    prod2 = reduce(lambda x,y:x*y , nums)
    """
    t = timeit.Timer(stmt=s)
    return t.repeat(repeat=10,number=100)

And this is my result:

Loop:
[0.08340786340144211, 0.07211491653462579, 0.07162720686361926, 0.06593182661083438, 0.06399049758613146, 0.06605228229559557, 0.06419744588664211, 0.0671893658461038, 0.06477527090075941, 0.06418023793167627]
test1 average: 0.0644778902685
HOF:
[0.0759414223099324, 0.07616920129277016, 0.07570730355421262, 0.07604965128984942, 0.07547092059389193, 0.07544737286604364, 0.075532959799953, 0.0755039779810629, 0.07567424616704144, 0.07542563650187661]
test2 average: 0.0754917512762

On an average loop approach seems to be faster than using HOFs.

Bharat
  • 2,960
  • 2
  • 38
  • 57
  • 2
    Are you familiar with the timeit module? You can test the performance yourself. – DSM Jan 28 '12 at 01:28
  • No, I am not familiar it. I will google for timeit. I guess that a profiling tool. But still I'd like to know the advantage of HOFs from a theoretical perspective. – Bharat Jan 28 '12 at 01:30
  • @RBK The problem is that the theoretical perspective won't answer your question (running time & memory efficiency). – Icarus Jan 28 '12 at 01:36
  • 2
    See [Alex Martelli's answer](http://stackoverflow.com/a/952952/78845) to [Making a flat list out of list of lists in Python](http://stackoverflow.com/q/952914/78845) for a nice way to compare. – johnsyweb Jan 28 '12 at 01:43
  • @DSM, I've tried out profiling with timeit. I am not able to answer my own question as I am 1 reputation point short of being allowed to answer my own question. I shall post my findings as an answer soon. – Bharat Jan 28 '12 at 02:06
  • @RBK: Actually I believe that instead of `prod2 = reduce(lambda x,y:x*y , nums)` you should test something that does exactly the same, but more efficiently (uses existing method, does not create new lambda): `prod2 = reduce(int.__mul__, nums)`. – Tadeck Jan 28 '12 at 02:14
  • @Tadeck, when I try that I am getting an error `TypeError: descriptor '__mul__' requires a 'int' object but received a 'long'` and when I change it to `long.__mul__` I get `descriptor '__mul__' requires a 'long' object but received a 'int'`. nums is just a list of 1 to 1000. – Bharat Jan 28 '12 at 02:22
  • @RBK: In your `[1,2,3,4,5]` I did not see `long`, nor within the result of `reduce(int.__mul__, xrange(1, 6))` :) So in your case (given in the question), you still could use `int.__mul__`. – Tadeck Jan 28 '12 at 03:08
  • @Tadeck, yes for `[1,2,3,4,5]` it works. I made a list of 1000 numbers as I had mentioned in the previous comment numbers & that caused the error. – Bharat Jan 28 '12 at 05:08
  • When I check the timings for 5 numbers with 50 repetitions, both are almost the same... – Bharat Jan 28 '12 at 05:12
  • @RBK: To employ similar solution for bigger numbers, you can convert them first to `long`. For making it efficient enough, you would need to import `imap` from `itertools`. The whole solution working also for bigger numbers looks like this: `from itertools import imap; reduce(long.__mul__, imap(long, xrange(1, 1000)))` (the example is for numbers 1-999). – Tadeck Jan 29 '12 at 00:02

2 Answers2

7

Higher-order functions can be very fast.

For example, map(ord, somebigstring) is much faster than the equivalent list comprehension [ord(c) for c in somebigstring]. The former wins for three reasons:

  • map() pre-sizes the result string to the length of somebigstring. In contrast, the list-comprehension must make many calls to realloc() as it grows.

  • map() only has to do one lookup for ord, first checking globals, then checking and finding it in builtins. The list comprehension has to repeat this work on every iteration.

  • The inner loop for map runs at C speed. The loop body for the list comprehension is a series of pure Python steps that each need to be dispatched or handled by the eval-loop.

Here are some timings to confirm the prediction:

>>> from timeit import Timer
>>> print min(Timer('map(ord, s)', 's="x"*10000').repeat(7, 1000))
0.808364152908
>>> print min(Timer('[ord(c) for c in s]', 's="x"*10000').repeat(7, 1000))
1.2946639061
Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485
  • Oh, I see that map() does many things more efficiently than other ways. I guess the speed would depend on what we are trying to accomplish. The discussions for [Making a flat list out of list of lists in Python](http://stackoverflow.com/q/952914/78845) seems to suggest HOFs aren't the fastest. – Bharat Jan 28 '12 at 02:34
  • The use HOF is incidental to that discussion. The timings there are dominated by other factors such as function call overhead. – Raymond Hettinger Jan 28 '12 at 03:52
  • Yes, map seems to be faster. I tried your profiling code and got the same results. I am going to do some more profiling to convince myself :) – Bharat Jan 28 '12 at 05:17
1

from my experience loops can do things very fast , provided they are not nested too deeply , and with complex higher math operations , for simple operations and a Single layer of loops it can be as fast as any other way , maybe faster , so long as only integers are used as the index to the loop or loops, it would actually depend on what you are doing too

Also it might very well be that the higher order function will produce just as many loops as the loop program version and might even be a little slower , you would have to time them both...just to be sure.

John Einem
  • 51
  • 3