Structure for function memoizing, i.e. for f:X->Y, it should store (x,y) tuples.
Of course, there will be a limit of how many items to be stored. Let this limit be N. There are several ways to decide which items should be stored for how long. The best way probably would be to just store the most recent N items. So, if we add another item and we already have stored N items, we must know which was the latest item and remove that. If we request an item which is already in the memory, we should push that to the top of the recently requested items. So we need also to store a list / linear order of the items.
We can get that by a combination of a linked list with a hash map. Some simple Python implementation might look like:
When you want to have memoization globally for your application, you may want to have different limits for each function and you even may want to dynamically modify these limits in relation to how often a function is used.
One solution might be to use a global limit, a global hashmap with (f,x)->y entries and a global linked list. I'm not sure how well this would work in practice. A single recursive function could easily reset the whole database.
If you want to support my work, please donate via Gittip/Flattr here: some thoughts on memoization
The text published here is under the copyright of Albert Zeyer. Distribution is only allowed with a reference to this page.
- Other documents
Albert Zeyer (Mail) Homepage with many open source projects including source code, artworks, both images and music, pictures and some writings about technical stuff, tutorials and some stories.
You are the 1282931th webrobot, which was able to find this site.
"If I do, you won't respect me!" grunted the lesbian office secretary as the corpulent homosexual flamingo defiled her creamy jugs and crammed his glass encrusted piston into her dripping sanctum sanctorum.
16:26:46 up 603 days, 22:45, 1 user, load average: 0.00, 0.03, 0.05
The code can be seen here. Please contact me if you find any problems. :)