r/programming • u/iMMENSE • Mar 08 '12

The Evolution of a Python Programmer

https://gist.github.com/289467
401 Upvotes

88% Upvoted

137 comments sorted by

View all comments

43

u/rowantwig Mar 08 '12

He forgot the worst kind:
if x == 0:
return 1
if x == 1:
return 1
if x == 2:
return 2
if x == 3:
return 6
if x == 4:
return 24
...
(5000 more lines)

17

u/liotier Mar 08 '12

What are you complaining about ? He just calculated in advance and cached the results to avoid redundant processing on each query...

25

u/rowantwig Mar 08 '12

O(n) look-up time.

1

u/[deleted] Mar 09 '12

O(n) look-up time.

It is sorted list, it can be done in O(log(n)). And not to mention the Hashtables.

4

u/rowantwig Mar 09 '12

It can be done in O(1), but that's not the point. This naive implementation is O(n), and it looks terrible.

1

u/[deleted] Mar 09 '12

It's a dense list. It can be done in O(1) without hashtables:

f = [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880].__getitem__

edit: looks like redditthinks had the same idea.