Could a ringified script be fed a variadic input list?

I’ve been trying to create a universal memoizing script, mostly based on Fibonacci, Factorial, Triangle Numbers - #5 by bh.

What is memoizing and why is it useful?

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 Programming tools SANDBOX script pic 20 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:

  1. a list whose elements are identified by values of the first input;
  2. for each item in the first list: a list whose elements are identified by values of the second input;
  3. for each item in the second-to-last group of lists: a list whose elements are identified by values of the last input, and containing the memoized function’s calculated results as data. (I let myself inspire by Joseph Sikorski: Memoization of Multi-Parametered Functions in JavaScript | by Joseph Sikorski | Medium)

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.

Suggestions, anyone/?

The only way I can think of to put something into an input list, is by putting it directly into the block. I'll show you what I mean.
untitled script pic (26)

In here, you can see it puts the number of inputs I said in the list. In order to add the inputs, just add them to the list.

Or you can append the list to make it easier to understand.

Now, if you're adding it to a block with multiple inputs, you need to add the inputs in the order they appear in

of course, if there's a way to do it with call that I don't know of, then you might want to use that.

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.

@ego-lay_atman-bay Your post is probably a product of deep thought, but I don’t get it (yet). Let me revisit it after I will have made a second attempt. Thanks anyway for thinking along with me.

Oh, I see. I don't know what's wrong, then.

By the way, your data structure is called a trie (pronounced "try").

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 :slight_smile: .
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)

Does this help?
https://snap.berkeley.edu/snap/snap.html#present:Username=snapenilk&ProjectName=multivar-memoize%20debugging

@snapenilk : what you found about input lists corresponds with my recently acquired experience.

I finally got MULTIVAR-MEMOIZE to work:

[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).

If you’re interested, look here:
https://snap.berkeley.edu/snap/snap.html#present:Username=qw23&ProjectName=Memoize

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).

Sorry -- you should have asked for clarification!

No problem.

Meanwhile I constructed a really fast multi-variable (and, correspondingly, muli-level) memoize-function, that is fully recursive itself:

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).

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.