Как запомнить рекурсивную функцию сопоставления с элементами, возвращаемыми в массиве?

У меня есть функция мемоизации, которая запоминает рекурсивные функции, возвращающие сумму, например Number, но не с моей функцией collatz, которая возвращает массив. Моя карта внутри функции мемоизации будет иметь разные ключи, но одно и то же значение, и не запоминать каждый шаг функции. Я стараюсь, чтобы это было возможно компонуемым.

Вход в консоль внутри collatz для проверки того, запущен ли он, приведет к выходу из системы в первый раз, как и ожидалось.

Я тестировал это на экспоненциальной рекурсивной функции с другой функцией клавишного инструмента, которая правильно запоминает.

const memoized = (fn, keymaker = JSON.stringify) => {
    const lookupTable = new Map();
    return function (...args) {
      const key = keymaker.call(this, args);
      return lookupTable[key] || (lookupTable[key] = fn.apply(this, args));
    }
  };

  const ignoreOthers = ([...values])=>{
    return JSON.stringify(values.shift())
  }


  const memCollatz = memoized((n,arr=[]) =>{
    //console.log('ran')
    if (n<=1) return arr.concat(1)
    else if(n %2 === 0) return memCollatz(n / 2,arr.concat(n))
    else return memCollatz((n*3)+1,arr.concat(n))
  },ignoreOthers)

  console.log(memCollatz(5))
  console.log(memCollatz(6))
  console.log(memCollatz(6))

   
/*
   Map {
    '1': [ 5, 16, 8, 4, 2, 1 ],
    '2': [ 5, 16, 8, 4, 2, 1 ],
    '3': [ 5, 16, 8, 4, 2, 1 ],
    '4': [ 5, 16, 8, 4, 2, 1 ],
    '5': [ 5, 16, 8, 4, 2, 1 ],
    '6': [ 5, 16, 8, 4, 2, 1 ],
    '8': [ 5, 16, 8, 4, 2, 1 ],
    '10': [ 5, 16, 8, 4, 2, 1 ],
    '16': [ 5, 16, 8, 4, 2, 1 ] } 
 */

После запуска указанных выше журналов консоли моя карта выглядит так, но должна иметь n в качестве ключа и запоминать каждый шаг.


javascript recursion memoization
person NoleloN    schedule 23.12.2018    source источник
comment
const memCollatz = memoized(const memCollatz здесь const ошибка, это опечатка? Может быть, вы могли бы сделать это исполняемым сниппетом?   -  person Mark    schedule 24.12.2018
comment
Да, это опечатка, извините. Я посмотрю, как это сделать.   -  person NoleloN    schedule 24.12.2018

Ответы (1)


arrow_upward
0
arrow_downward

Из-за того, как вы создаете arr внутри memCollatz, выполнение кода будет выглядеть так:

memCollatz(5) | arr = [] | map is empty
memCollatz(16) | arr = [5] | map is empty
memCollatz(8) | arr = [5, 16] | map is empty
memCollatz(4) | arr = [5, 16, 8] | map is empty
memCollatz(2) | arr = [5, 16, 8, 4] | map is empty
memCollatz(1) | arr = [5, 16, 8, 4, 2] | map is empty

Последний вызов memCollatz (1) действительно возвращает что-то первым, поэтому

{1: [5, 16, 8, 4, 2, 1]}

добавлен в карту поиска

Теперь, поскольку memCollatz (2) просто возвращает то, что было возвращено memCollatz (1), другая запись

{2: [5, 16, 8, 4, 2, 1]}

добавлен на карту

Опять же, поскольку memCollatz (4) просто возвращает то, что возвращено memCollatz (2), другая запись

{4: [5, 16, 8, 4, 2, 1]}

добавлен на карту

... и так далее.

Чтобы обойти это, вам нужно избегать такого «сквозного» поведения, т.е. убедиться, что memCollatz (1) возвращает что-то отличное от memCollatz (2) и т. Д.

Вот пример:

  const memCollatz = memoized((n) =>{
    if (n<=1) return [1];
    else if(n %2 === 0) return [n].concat(memCollatz(n / 2))
    else return [n].concat(memCollatz((n*3)+1))
  },ignoreOthers)
person ack_inc    schedule 24.12.2018