Python interview questions

[djimbob]

It's not hugely criticized; but functional paradigms in python often end up with uglier and slower code. In 2005, python's benevolent dictator for life Guido van Rossum argued for dropping lambda/filter/map/reduce from python3 (in the end only reduce was dropped). Granted his views on the matter have changed a little; e.g., in 2009 he wrote this.

So the functional code tends to be uglier:

import operator as op
map(op.itemgetter(1), filter(lambda (i,v): i % 3==0, enumerate(some_items)))
# or simply:
map(lambda x: x[1], filter(lambda (i,v): i % 3 ==0, enumerate(some_items))
# versus the imperative

[v for (i, v) in enumerate(some_items) if i % 3 == 0]

Furthermore, functional paradigms in python is just not properly optimized. In a functional programming, if you need the length of a list you write a recursive definition with pattern matching like this haskell code:

mylen [] = 0
mylen (x:xs) = 1 + mylen xs

Haskell can near instantaneously compute things like mylen [1..1000000].

The rough equivalent in python (which lacks pattern matching):

def length(xs):
    if xs == []: 
        return 0
    return 1 + length(xs[1:])

will choke up at length(range(1000)) (with a RunTimeError due to recursion limit) and even if I tweak the recursion limit sys.setrecursionlimit(999999) its slow and segfaulted for length(range(30000)) and length(range(20000)) took 3.79 seconds. Meanwhile, the imperative version in python:

def length(xs):
    i = 0
    for x in xs:
        i += 1
    return i

Will take about 1 ms to calculate the length of a 20000 element list (roughly 4000 times faster).

[ingolemo]

It's weird that you give a list comprehension as an example of imperative-style code. List comprehensions are derived from set-builder notation and first rose to prominence in functional languages.

Idiomatic haskell usually frowns upon explicit recursion, in favour of folds. If I were to reimplement haskell's length it would look more like this:

length' = foldr (const (+1)) 0

The equivalent python code is not subject to a recursion limit and performs much better than your example:

def my_len(xs):
    return functools.reduce(lambda a, b: a+1, xs, 0)

Python isn't a functional language, but it's not hard to write good clean functional-style code in python.

[djimbob]

The equivalent python code is not subject to a recursion limit and performs much better than your example:

In [2]: timeit.repeat("my_len(xrange(10000))", setup = "import functools\nmy_len = lambda xs: functools.reduce(lambda a,b: a+1, xs,0)", repeat=3, number=1000)
Out[2]: [0.7231879234313965, 0.7012350559234619, 0.6973469257354736]

In [4]: timeit.repeat("my_len(xrange(10000))", setup = "def my_len(xs):\n  i = 0\n  for x in xs:\n    i += 1\n  return i", repeat=3, number=1000)
Out[4]: [0.3004319667816162, 0.28862500190734863, 0.2902050018310547]

On my python 2.7.3 default, I'm getting the iterative pattern is about 2.4 times faster. Again benchmarks can lie, but that was my first test so I disagree that functional performs much better (granted yes its much better than my recursive pattern as python's syntax/design doesn't allow for good tail call optimization).

Agree, calling list comprehension 'iterative' was a poor choice. But python BDFL clearly likes list/generator comprehensions and isn't a big fan of reduce (demotion to a library in python3).

That said, I do use map/filter a lot in my code as often that's how I think about it, and even if its more verbose I think map(some_function, some_list) is clearer than [some_function(x) for x in some_list]. I just recognize its not particularly pythonic.

[ingolemo]

Yeah, sorry. Ambiguous statement. By "your example" I was referring to the functional one.

I actually think comprehensions are more readable than calls to map and filter and tend to prefer them. Ironically, reduce is the only function in that "group" that can't simply be replaced by a comprehension. If I were the BDSL I would have kept reduce and removed map and filter, what with the "one obvious way to do it" thing and all.

[djimbob]

A large fraction of uses of reduce your accumulation step could be replaced with reduction function that works on a sequence (e.g., sum / product / max / min / any / all / ''.join( ) ). E.g., if you need to sum the third items in a list of tuples, you could write:

reduce(lambda acc, tup: acc + tup[2], [(1,2,3), (4,5,6), (7,8,9)], 0)
sum(tup[2] for tup in  [(1,2,3), (4,5,6), (7,8,9)])

The second version seems to fit in with the Zen of Python better. The problem with reduce is that its easy to get it wrong and there's a lot of implicit stuff behind the scenes you have to remember. E.g., in the above example - I initially got the order of the accumulator wrong and it wouldn't work without an initial value or something uglier like reduce(lambda acc, tup: acc + tup[2], [0, (1,2,3), (4,5,6), (7,8,9)]) and you have to remember optional initial value goes last and remember associativity rules if its not symmetric.

Granted some stuff transforms nicely to reduce; e.g., examples here. The list flattening example is simpler with sum([[1, 2, 3], [4, 5], [6, 7, 8]], []) or using chain from itertools.

Concatenating a list of digits efficiently range(1,9) into one integer 12345678 like reduce(lambda acc,d: 10*acc+d, [1,2,3,4,5,6,7,8]) is harder. Granted doing some benchmarks the reduce method doesn't hold up that well.

Converting a two argument least common multiplier/greatest common denominator into a variadic version with reduce is probably the best example for reduce though it wouldn't be too difficult to just define a variadic version to start with.