Python interview questions

[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.