Is this a memoïze function?

Question

Is this a memoïze function?
Secondly,
is it an efficient one?

function memoïze(func) {
  var array = [];

  return (value) => {
    var index = array.findIndex((item) => item.lastValue == value);
    if (index >= 0) {
      return array[index].lastResult;
    } else {
      var result = func(value);
      var obj = {
        lastValue: value,
        lastResult: result,
      };
      array.push(obj);
      return obj.lastResult;
    }
  };
}

I do not like that am storing two things for each call!

Answer 1

as it is a concept of programming which I did not know, I made some personal tests on this type of coding.

Here is the result of these tests: a universal memoïze function?

const square  = n => Math.pow(n, 2)
  ,   cube    = n => Math.pow(n, 3)
  ,   multply = (a,b) => a * b
  ;
function memoïze(func)
  {
  let cache = {}
  return (...vals) => {
    let ref = JSON.stringify(vals)
    if(ref in cache) return cache[ref]
   // console.log('no cache for', ref)
    let res = func(...vals)
    cache[ref] = res
    return res
  }
}

let m_square  = memoïze( square )
let m_cube    = memoïze( cube )
let m_multply = memoïze( multply )

console.log( m_square(8))  // 64
console.log( m_cube(5) )   // 125
console.log( m_multply(3,7) )  // 21

console.log( '-- result with cache: --' )  

console.log( m_square(8))      // 64
console.log( m_cube(5) )       // 125
console.log( m_multply(3,7) )  // 21

.as-console-wrapper { max-height: 100% !important; top: 0; }

the same with Alnitak method (with map)

function memoïze(func)
  {
  let cache = new Map()
  return (...vals)=>
    {
    let key = JSON.stringify(vals)
    if (!cache.has(key)) cache.set(key, func(...vals))
    return cache.get(key)
  } }

Answer 2

What you have here is a closure.

Your array doesnt get garbage collected because it still has an reference to your inner function.

You have a memoization, but it can be improved.

To make it more efficient i would go with an object witch has an access time of O(1) while you have an access time of O(n):

function memorise(func) {
  var cache = {};
  return (value) => {
    if(value in cache) return cache[value];
    var result = func(value);
    cache[value] = result;
    return result;
  }
};

Example witch object:

function memorise() {
  var cache = {};
  return (value) => {
    if(value in cache) return cache[value];
    cache[value] = value;
    return value;
  }
};

let mem = memorise();

console.time('chrono 1');
for(let i = 0; i < 10000; i++) {
   mem(i);
}
console.timeEnd('chrono 1');

console.time('chrono 2');

for(let i = 0; i < 10000; i++) {
   mem(i);
}
console.timeEnd('chrono 2');

Example with array:

function memorise() {
  var array = [];
  return (value) => {
    var index = array.findIndex((item) => item.lastValue == value);
    if (index >= 0) {
      return array[index].lastResult;
    } else {
      var obj = {
        lastValue: value,
        lastResult: "someval",
      };
      array.push(obj);
      return obj.lastResult;
    }
  };
}

let mem = memorise();

for(let i = 0; i < 100000; i++) {
   mem(i);
}

console.time();
for(let i = 0; i < 100000; i++) {
   mem(i);
}
console.timeEnd();

Answer 3

Yes, it is a memoization function, but it's not an efficient one, because is uses an O(n) lookup into an array instead of using an O(1) Map lookup.

Here's a more modern efficient version:

function memoize(factory, ctx) {
    const cache = new Map();
    return function(key) {
        if (!cache.has(key)) {
            cache.set(key, factory.call(ctx, key));
        }
        return cache.get(key);
    }
}

with sample usage:

var fib = memoize(n => n < 2 ? 1 : fib(n - 1) + fib(n - 2));

where the usage of the cache improves the performance of the algorithm from O(1.6 ^ n) to O(n) for new values, and O(1) for previously calculated values, while still preserving the recursive nature of the algorithm.

NB: for fib(50) this takes under 200µS on my laptop whereas the non-memoized version takes over three minutes.