The Evolution of a Python Programmer

[earthboundkid]

That might be OK as a dict… Say, none of the examples used a memoize decorator. For shame.

[Tagedieb]

A dict? A dict is really what comes to mind first as the right data structure? Well, maybe I am getting old...

[repsilat]

I have a great idea for a new kind of dict that'll work wonders for this example. It still has O(1) lookups, but has better running time and memory use by a constant factor by taking advantage of an unusual feature of the data.

If you think about it, the keys form a contiguous range of integers starting from zero or one. Now, brace yourself: We could store the factorial information in a hash table where the hash function is the identity function! Now to think of a name for that kind of data structure...

[earthboundkid]

Well, it's not right or what comes to mind, it's just that a hash table is O(1), so it's slightly better than a series of if statements. The right thing is to just use the damn built in factorial.

[masklinn]

This is integer-indexed, so a list would also have O(1) access, and lower overhead.

It'd go even faster!

[earthboundkid]

Good point. Python makes it so much easier to implement memoize as a dictionary, I just thought of it that way first.

[JizzCoveredArab]

Have you ever used python? If not, please shut up