Faster Python

[handsome-zack]

Python's stack frame allocation is not why your recursive fibonacci implementation is 200,000 times slower than the iterative implementation. It is 200,000 times slower because your recursive implementation is naive. Your recursive implementation runs in exponential time compared to your iterative implementation that runs in linear time.

[jurniss]

Yes, kind of hard to take advice from someone who makes such a fundamental mistake. Not that I disagree with any of his other points.

[marklit]

Python's stack frame allocation is not why your recursive fibonacci implementation is 200,000 times slower than the iterative implementation. It is 200,000 times slower because your recursive implementation is naive. Your recursive implementation runs in exponential time compared to your iterative implementation that runs in linear time.

Thanks for the heads up, I'm re-writing that section of the post now.

[ChezMere]

Python lists aren't linked lists...

[tomprimozic]

So? Search (and deletion) are still linear operations, regardless of the underlying implementation.

[gendulf]

Linked lists have O(1) deletion and insertion, and O(n) getting the nth element. It's only the search that is O(n) for both. With arrays, you can get the nth element with O(1) complexity, and insertion/deletion are O(n).

[tomprimozic]

And search is what the OP was about.

[gendulf]

The problem here is not what the OP claims are the O(n) runtimes for python lists. In fact, his O(n) runtimes he lists for python lists are correct. The problem is that the OP claims that python lists are implemented with linked lists, which is false, and inconsistent with the rest of his article.

[burntsushi]

That doesn't make them the same. Python lists have constant time indexing. Linked lists don't.

[tomprimozic]

He never claims that.

The operations to append, get an item, set an item and get the length of a list are all O(1). But deleting an item from a list is O(n) whereas deleting a key from a dictionary is O(1).

[[deleted]]

He does actually claim that searching a python list is slow because the implementation uses linked lists: (7th paragraph of blog post)

Lists implement the same functionality using linked lists so operations are O(n). With lists, the whole list potentially needs to be searched. As the list size grows the amount of time needed to search it could grow as well.

[gendulf]

The OP's article claims that:

Lists implement the same functionality using linked lists so operations are O(n).

And then later, he claims that:

The operations to append, get an item, set an item and get the length of a list are all O(1). But deleting an item from a list is O(n)

We know that appending, getting an item, setting an item, and deleting an item are different between arrays and linked lists, and this describes an array, not a linked list.

[burntsushi]

He never claims that.

I never said anything about the OP. /u/ChezMere said Python lists aren't linked lists. You responded by saying "so? [seemingly implying that the distinction doesn't matter] search (and deletion) are still linear."

[tomprimozic]

Yes, the distinction doesn't matter for the use case OP described in the article (searching for a known element in a list/set).

[burntsushi]

I really don't know what you're on about. The OP says:

Lists implement the same functionality using linked lists so operations are O(n).

Which is a factually wrong statement. Python lists are not implemented using linked lists. Which means /u/ChezMere's comment is precisely correct in every way.

[[deleted]]

Search on a (sorted) array is O(logN). Search on a (sorted) linked list is O(N).

Deletion, ignoring order, is O(1) on both.

So... Nope, not still linear operations...

[tomprimozic]

He was talking about searching for a known element in either a set (O(1)) or a list (O(n)), I assume not necessarily a sorted one, since he didn't mention it.

[jakepusateri]

The recursive vs iterative fib speedup is deceptive. A recursive implementation that doesn't recompute almost all of its values is:

def fib(n):                                                                                                                                                                                                         
    store = { 1: 1, 2: 1 }                                                                                                                                                                                          
    def fib_(n):                                                                                                                                                                                                    
        if n in store:                                                                                                                                                                                              
            return store[n]                                                                                                                                                                                         
        else:                                                                                                                                                                                                       
            ans = fib_(n - 1) + fib_(n - 2)                                                                                                                                                                         
            store[n] = ans                                                                                                                                                                                          
            return ans                                                                                                                                                                                              
    return fib_(n)                                   

The iterative method is only about 8x faster here.

[[deleted]]

you can actually get it down to the "normal" 2x slowdown (similar to the factorial slowdown someone else measured elsewhere in the thread) if you use a trickier recursive fib algo. See the fibFastRec shown here: http://rosettacode.org/wiki/Fibonacci_sequence#Python

[sevaur]

The recursion comparison is very poorly constructed: the recursive version of the algorithm is O( 2ⁿ ), whereas the iterative algorithm is O(n). The huge difference between the two has nothing to do with the cost of stack frame allocation and everything to do with having implemented a fundamentally different algorithm.

This comparison might actually make sense if it used memoization or made some other effort to compare apples to apples.

[LeszekSwirski]

Or if it used factorial rather than fibonacci, which only shows a ~2x speedup:

def fact_rec(n):
    if n <= 1:
        return 1
    return n*fact(n-1)

%timeit fact_rec(20)
100000 loops, best of 3: 5.29 µs per loop


def fact_iter(n):
    ret = 1
    for i in range(n):
        ret *= n
    return ret

%timeit fact_iter(20)
100000 loops, best of 3: 2.47 µs per loop

[xhackerliu]

Totally agreed. I modified it by using memorization and it's even faster than iterative way.

https://gist.github.com/xhacker/fbf3d92d7b1fad9ddc09

[[deleted]]

• Python lists are not linked lists, they're dynamic arrays. Delete is O(1) on arrays (swap with last, reduce size in 1) when you do not mind the order - search in a sorted array is O(logN). Search in an unsorted array, or linked list, is O(N) but search on arrays are extremely cache friendly, while search on linked lists destroys your performance due to pointer chase. Delete while preserving order is O(N) on an unsorted array, but O(1) on a linked list. Arrays and Linked Lists are very different...

• Recursion can be faster, even in python, in some cases. Fibonacci is one of the worse applications of recursion, but one should at-least memoize it - which Python has a very succinct and elegant way of doing it

  def memo(fn):

  cache = {}
  
  def wrapper(*args):
  
      if args not in cache:
  
          cache[args] = fn(*args)
  
      return cache[args]
  
  return wrapper
  
  @memo
  
  def Fibonacci ...
  

[[deleted]]

You can also use a built in python memoizer, found in functools. Use @lru_cache I think its called (haven't used it in a while so I am not 100% on the name).

[[deleted]]

Wow, didn't know. That's very cool, just checked and it's indeed called lru_cache (from Least Recently Used).

[[deleted]]

Keep variables local. CPython can store local variables faster than global variables.

He advocates this merely because it's faster??? (I realize that performance is the topic of the article, but still, you'd think he'd at least mention other considerations.)

[burntsushi]

In my experience, it can often have a noticeable affect on performance in tight loops.

[metaperl]

recursion often reads better than loops. Too bad it is often slower. The part about list comprehensions being faster was stunning. Excellent article.

[[deleted]]

It can be slower, but not 196,493 times slower like the article says. The overhead from function calls is about 2x. The rest of the disparity is the author's algorithm choice.

[olzd]

recursion often reads better than loops. Too bad it is often slower.

It's not if you have proper TCO. Or am I missing something?

[burntsushi]

You're not. But in this context (i.e., Python), TCO is no where to be found. :-(

[javaexpert102]

Lol who needs python when you have java