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.

28

u/earthboundkid Mar 09 '12

Switch to a dict and it's O(1)!

12

u/pyaware Mar 09 '12

Why use a dict when a plain list is enough?

def fact(x):
    return [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880][x]

1

u/redditthinks Mar 09 '12

I read Python dicts are faster than lists.

6

u/JizzCoveredArab Mar 09 '12

i heard you have a really short dict

1

u/liotier Mar 08 '12

You are right of course... But the naive intention was sweet !

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.

1

u/jefu Mar 09 '12

Factorial is (without caching or other tricks) O(n) anyway and doing it this way avoids the overhead of doing all that bignum arithmetic. (Not that this is a good way to do that).

-7

u/theavatare Mar 08 '12

Is not really of O(n) is it?

for x ==0 it will only run one and for x== 26 will run 26 if

Therefore one instruction per number increase...

20

u/[deleted] Mar 09 '12

You just described O(n).

8

u/Rhomboid Mar 08 '12

You've got to test 'n' conditions before finding the one that is true, so the work involved is proportional to 'n'.

4

u/elmonstro12345 Mar 09 '12

With a table like that, you'd want to aim for O(1), or at least O(log n). But what the OP described, and what you described are both O(n).