2009-02-18, 10:34 PM
As I'm working with some memoization-macro in LISP, I turned on a performance-issue I've not really worked much with:
To make a general macro for memoization, I'm using hash-tables. If the value's already calculated before, it would be found in the hash-table. If it's not found, it will calculate the value and add this into the hash-table afterwards. Great stuff for recursive functions.
So, here's the thing: For multiple values in a memoization-function, would it be more handy to make hash-tables like this:
function (a, b, c):
Or like this?
I would assume the first one would be the fastest. However, the thing here is that this is no 3d-array, this is a hash-tree. If I e.g. test out a new value here, say:
function (4, 1, 2);
To gather the information if existing, it will look if there's a key in the hash-table for A = 4. If this returns a hash-table, it will look if there's a hash-table for B = 1. If there is a hash-table for this value, it will then look for a result for C = 2. If there is, returns that value. If not, do the following:
Create a new hash-input in the first hash-table. Now, it has to create a new hash-table, and then a new hash-input in this new hash-table. Finally, it has to create a new hash-table and a new hash-input in this table, which will hold the answer when computed.
The other way would be to check if there's a hash-key 4 1 2 in the hash-table. If not, makes this hash-key and computes value for the function.
Now, what would be the fastest? Creating the hash-tables would take some time, but then again, looking up a value in a bigger hash-table would also take some time. What would take the most time?
To make a general macro for memoization, I'm using hash-tables. If the value's already calculated before, it would be found in the hash-table. If it's not found, it will calculate the value and add this into the hash-table afterwards. Great stuff for recursive functions.
So, here's the thing: For multiple values in a memoization-function, would it be more handy to make hash-tables like this:
function (a, b, c):
Hash-Table
Or like this?
Hash-Table
I would assume the first one would be the fastest. However, the thing here is that this is no 3d-array, this is a hash-tree. If I e.g. test out a new value here, say:
function (4, 1, 2);
To gather the information if existing, it will look if there's a key in the hash-table for A = 4. If this returns a hash-table, it will look if there's a hash-table for B = 1. If there is a hash-table for this value, it will then look for a result for C = 2. If there is, returns that value. If not, do the following:
Create a new hash-input in the first hash-table. Now, it has to create a new hash-table, and then a new hash-input in this new hash-table. Finally, it has to create a new hash-table and a new hash-input in this table, which will hold the answer when computed.
The other way would be to check if there's a hash-key 4 1 2 in the hash-table. If not, makes this hash-key and computes value for the function.
Now, what would be the fastest? Creating the hash-tables would take some time, but then again, looking up a value in a bigger hash-table would also take some time. What would take the most time?