Many functions are most easily defined, and coded, using recursion. The downside is often that many of the same calculations will be performed over and over again, in different branches of a recursive tree structure. Memoizing is a technique to register which values have already been calculated, such that these are simply recalled and all of the underlying recursion will be avoided.
As a first step I rewrote the original memoizer (for functions with 1 input) so as to take advantage of Snap!’s recently added (very fast) non-numeric item selection feature:
(I used the single input (x) as memoïzation key of course, prefixed with “#” - as x might be a number and would otherwise be handled by in an unwanted fashion).
So far, so good. E.g. the 1,000-th Fibonacci number - see the aforementioned post - is calculated recursively within 0.1 sec (iPad Pro-2, Turbo mode).
But what if the function to be memoized has multiple inputs?
One way to handle this situation is: somehow transform the inputs into a single string (or similar), and use that as memoïzation key - it may be called “serializing”. Even though that’s quite doable it also has a downside: performance (at least when many different values of each input are in play, and the total number of combinations explodes to, like, tens or hundreds of thousands). So I have been working on a solution with multi-level lists:
a list whose elements are identified by values of the first input;
for each item in the first list: a list whose elements are identified by values of the second input;
Somehow this script won’t work. An error message says: “expecting a list but getting a number”.
I suspect the root of the issue to be that I haven’t figured out how to feed a (variadic) input list into a ringified script.
I don't understand the purpose of SET PATH TO VALUE at the bottom of the FOR EACH loop. And the next time through the loop, you ask for ITEM (...) OF PATH, which sure enough isn't a list, hence the error message. The variadic CALL looks fine to me.
If the number of inputs = 1, memory is a list (more precisely; a lookup table) each of whose items contain an index and a value.
If the number of inputs = 2, memory is still a lookup table (level 1), but each of its items’ second item is another lookup table (level 2). Level 2 lookup tables’ items contain an index and a value.
If the number of inputs > 2, both memory’s and the level 2 (and further, up to and including the one-below-deepest level) lookup tables’ items’ second items are again lookup tables.
This is like a path trough a tree structure, hence the “path” variable name (I may change it to “lookup table” for clarity). Whatever the variable’s name, for all except the deepest level “value” (for lack of a better name) is actually a list (lookup table), passed to the next level as the new path.
That’s nice to know - at least I’m trying - or should I say: trieing? - something sensible (?) people did before, and even thought up a name for .
As for the input list, it so appears that I need to indicate a single input parameter (e.g. “input list”) at the grey ring, to be interpreted as an input list by the script within; and when calling the variable the script within the grey ring was assigned to I need to use “WITH INPUTS:” with the input list in a single slot (so avoid “INPUT LIST:” when calling).
Still, weird and unexplained stuff is happening when I run the script - I already installed breakpoints, logs and what not, but I’m still in the dark. I may return to ask for more help.
Thanks for now! (@ego-lay_atman-bay)
[EDIT: Un- …] Surprisingly, the version below does NOT work. The only difference in code is that the “lookup table” variable is declared outside the grey ring; why this would be crucial I don’t fathom. [EDIT: it’s actually quite understandable; see the next 2 posts]
I tested MULTIVAR-MEMOIZE against ordinary MEMOIZE using a recursive function with two inputs, which I dubbed CHANGE-OPTIONS (= in how many different ways can one pay an amount, given a set of coin denominations?). I was a tad disappointed by MULTIVAR-MEMOIZE‘s performance; apparently the overhead of the multilevel operation is considerable; only if the number of intermediate results to be reused is really large (10,000+ or so) will MULTIVAR-MEMOIZE beat ordinary MEMOIZE (of course the memoized function needs to be redefined with a single input, being a list of two or more variables).
A variable declared in the SCRIPT VARIABLES outside the ring is shared by every call to the ringed function. But inside the ring is a FOR EACH loop that uses LOOKUP TABLE as a temporary variable that ends up with a tiny piece of the actual table as its value. The first version declares MEMORY as a persistent variable shared by every invocation, and LOOKUP TABLE as a temporary variable local to each particular invocation.
It took me several more hours of debugging to finally understand what your remark implied, but I get it now: “lookup table” must be a local variable in order for the memoizing code to support re-entrancy; if not, its integrity will be compromized. In retrospect it’s hard to imagine I overlooked this!
BTW “value” should be a local variable, too (in case of threads).
Now the reader may notice that the codes encapsulated in either ring are very much alike … which raises the question whether the common elements could be coded only once. I haven’t succeeded in achieving a working solution based on this (yet).