Automatic Recursive Memoization / Philippe Rigovanov

Philippe Rigovanov

math & informatics teacher

Workspace

Public

Informatics

Edited

Dec 30, 2022

Fork of Automatic Recursive Memoization

1 star

Informatics

ЕГЭ по Информатике. Вариант №01092023, 2023г. Составил Евгений Джобс.ЕГЭ по Информатике. Вариант №16012023, 2023г. Составил Марат Ишимов.Оптимизация перебора Dynamic Programming Notes

Automatic Recursive Memoization

function fib(n) {

return n <= 1 ? 1 : fib(n - 1) + fib(n - 2);

}

memfib = memrec(fib)

a = perf(fib, 35)

b = perf(memfib, 35)

function fibbish(a, b) {

return a*b + ((a >= 1 && b >= 1) ? fibbish(a-1, b-2) + fibbish(a-2, b-1) : 0);

}

memfibbish = memrec(fibbish)

c = perf(fibbish, 39,39)

d = perf(memfibbish, 39, 39)

function squared(n){ return n*n; }

memsquared = {

const cache = {};

return function memsquared(n){

if (!cache.hasOwnProperty(n)) {

cache[n] = squared(n);

}

return cache[n];

}

function fiblog(n, log = []) {

// keep track of each time fiblog is called

log.push(`fiblog(${n}, log)`);

const val = n <= 1 ? 1 : fiblog(n - 1, log).val + fiblog(n - 2, log).val;

return {val, log};

}

fiblog(1)

fiblog(2)

fiblog(3)

fiblog(10)

fiblog(30)

memfibdumb = {

const cache = {};

return function memfibdumb(n, log = []){

if (!cache.hasOwnProperty(n)) {

cache[n] = fiblog(n, log);

}

return cache[n];

};

}

memfibdumb(1)

memfibdumb(2)

memfibdumb(10)

memfibdumb(30)

// I'm creating a new memoized function each time to

// demonstrate how the cache is built up - otherwise

// subsequent calls to the same function would

// benefit from the memoization of previous calls!

function memfibmanual(){

const cache = {};

return function memfibmanual(n, log = []){

// keep track of each time fiblog is called

log.push(`memfibmanual(${n}, log)`);

if (n <= 1) return {val: 1, log};

if(!cache.hasOwnProperty(n)) {

cache[n] = memfibmanual(n-1, log).val + memfibmanual(n-2, log).val;

}

return {val: cache[n], log};

};

}

memfibmanual()(1)

memfibmanual()(2)

memfibmanual()(3)

memfibmanual()(10)

memfibmanual()(30)

// To be used in combination with memrec below.

// To memoize functions with multiple parameters, a simple key => value map won't do.

// Instead we want a kind of map that takes a list of parameters as the key for its

// get and set methods. That is what this class does.

// (If you only pass JSON-serializable objects to a function, you could get away

// with using one map and applying JSON.stringify to the arguments instead)

// TODO: make it possible to only remember the last N results

class ParamCache {

constructor() {

this.cache = new Map();

}

// walk through our cache tree - if our params are not present,

// create the needed maps to initiate the tree.

walkparams(params) {

let {cache} = this;

// Note that the first param is always the recursive function itself,

// so we can skip that. We stop just before the last parameter, as

// that is the one we use to determine if the tree has already

// cached a previous result or not.

for(let i = 1; i < params.length-1; i++) {

let nextcache = cache.get(params[i]);

if (nextcache === undefined) {

for (let j = i; j < params.length-1; j++) {

nextcache = new Map();

cache.set(params[j], nextcache);

cache = nextcache;

}

break;

} else {

cache = nextcache

}

return cache;

}

get(params) {

const cache = this.walkparams(params);

// a function may return `undefined` as a return value,

// which we should cache. To indicate this we return an

// array. If the get was successful, it has one entry.

// If not, it's empty.

let value = []

if (cache.has(params[params.length-1])) value.push(cache.get(params[params.length-1]))

return value;

}

set(params, value) {

const cache = this.walkparams(params);

cache.set(params[params.length-1], value);

}

function memrec(fn) {

const name = fn.name;

const src = fn.toString();

// We want to avoid naming collisions with original source code,

// so we use a long string of random chars for our function name.

// 32**64 means there's a chance of roughly one in 10 ** 96 of

// a naming collision.

// I think we're good.

let hash = ""

for(let i = 0; i < 64;i++) { hash += (Math.random()*32|0).toString(32); }

let fn_name = "fn_" + hash;

// this is a terrible way to detect where the parameters start and end.

// Basically, if someone uses a default value with a string that has a

// ")" in it, or has a lambda as a default value, or anything else

// with an early closing parenthesis in it, this breaks.

let i = src.indexOf("(");

let j = src.indexOf(")", i);

// A pure function that takes no parameters is easy to memoize.

// (but why would anyone be memoizing this?)

if (i+1 === j) {

const v = fn();

return () => v;

}

// First we convert recursive function into one that has the recursive calls

// to itself replaced with calls to a function that has to be passed explicitly.

// For example, from:

// function fib(n) {

// return n <= 1 ? 1 : fib(n - 1) + fib(n - 2);

// }

// to

// const newfn = function(cb, n) {

// return n <= 1 ? 1 : cb(cb, n - 1) + cb(cb, n - 2);

// };

// That might seem a bit silly at first, but this allows us to make a memoized

// version of it later.

// Count number of parameters.

// Maybe slightly less fragile in the face of default values with strings with commas

// Does not handle every case, breaks when we start embedding strings in strings with

// single quotes, double quotes and backticks, not to mention escape codes for example.

// Split string by commas, but ignore commas inside quotes

// https://stackoverflow.com/questions/23582276/split-string-by-comma-but-ignore-commas-inside-quotes#comment71514557_23582323

const paramRegex = /,(?=(?:(?:[^'"]*(?:'|")){2})*[^'"]*$)/;

let params = src.substring(i+1, j).split(paramRegex);

// we're going to assume that the first time we see "{" in our source

// after the parameters it will be the start of the function body, and

// that the last "}" ends it.

const src_body = src.substring(src.indexOf("{", j) + 1, src.lastIndexOf("}"))

// find and replace all recursive calls with the new function name, and insert the new function as

// the first parameter.

const fnRegexp = new RegExp(`([;:{\\s])${name}(\\s*\\()`, 'g');

const rec_body = src_body.replace(fnRegexp, `$1${fn_name}(${fn_name}, `);

// create a new function

params.unshift(fn_name);

params.push(rec_body);

const newfn = new Function(...params);

// Now we're ready to create a memoized version. The trick is to create a memoized

// wrapper cachefn that calls newfn, while passing itself instead of newfn as the

// function to be called to newfn.

// What this means is that newfn will call cachefn when doing recursion. If the

// new parameters have a result that is memoized, cachefn will return it. If not,

// it will call newfn with the changed parameters. This is a form of mutual

// recursion that results in the cache lookup being interjected in the function

// call at the right position.

const cache = new ParamCache();

const cachefn = (...args) => {

let v = cache.get(args);

if (!v.length) {

v[0] = newfn(...args);

cache.set(args, v[0]);

}

return v[0];

}

// we don't want to expose all this weirdness of mutual-recursive-self-passing,

// so we create a final wrapper that accepts the original arguments and return it

return (...args) => {

return cachefn(cachefn, ...args);

};

}

perf = (fn, ...args) => {

var t0 = performance.now();

var result = fn(...args);

var time = performance.now() - t0;

return { result, time };

}

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.

Learn more