J'ai cette fonction récursive sum qui calcule la somme de tous les nombres qui lui ont été transmis.

function sum(num1, num2, ...nums) {
  if (nums.length === 0) { return num1 + num2; }
  return sum(num1 + num2, ...nums);
}

let xs = [];
for (let i = 0; i < 100; i++) { xs.push(i); }
console.log(sum(...xs));

xs = [];
for (let i = 0; i < 10000; i++) { xs.push(i); }
console.log(sum(...xs));

Cela fonctionne très bien si seuls 'quelques' nombres lui sont transmis mais déborde call stack sinon. J'ai donc essayé de le modifier un peu et d'utiliser trampoline pour qu'il puisse accepter plus d'arguments.

function _sum(num1, num2, ...nums) {
  if (nums.length === 0) { return num1 + num2; }
  return () => _sum(num1 + num2, ...nums);
}

const trampoline = fn => (...args) => {
  let res = fn(...args);
  while (typeof res === 'function') { res = res(); }
  return res;
}

const sum = trampoline(_sum);

let xs = [];
for (let i = 0; i < 10000; i++) { xs.push(i); }
console.log(sum(...xs));

xs = [];
for (let i = 0; i < 100000; i++) { xs.push(i); }
console.log(sum(...xs));

Alors que la première version n'est pas en mesure de gérer 10 000 numéros, la seconde l'est. Mais si je passe 100 000 numéros à la deuxième version, j'obtiens à nouveau une erreur call stack overflow.

Je dirais que 100000 n'est pas vraiment grand (peut-être faux ici) et je ne vois aucune fermeture incontrôlée qui aurait pu causer la fuite de mémoire.

Quelqu'un sait-il ce qui ne va pas?

1
Matus Dubrava 23 mai 2018 à 17:00

3 réponses

Meilleure réponse

Les navigateurs ont des limites pratiques sur le nombre d'arguments qu'une fonction peut prendre

Vous pouvez modifier la signature sum pour accepter un tableau plutôt qu'un nombre variable d'arguments, et utiliser la déstructuration pour garder la syntaxe / lisibilité similaire à ce que vous avez. Cela "corrige" l'erreur de stackoverflow, mais est incroyablement lent: D

function _sum([num1, num2, ...nums]) { /* ... */ }

C'est-à-dire: si vous rencontrez des problèmes avec le nombre maximum d'arguments, votre approche récursive / trampoline va probablement être trop lente pour fonctionner avec ...

2
user3297291 23 mai 2018 à 14:18

L'autre réponse a déjà expliqué le problème avec votre code. Cette réponse démontre que les trampolines sont suffisamment rapides pour la plupart des calculs basés sur des tableaux et offrent un niveau d'abstraction plus élevé:

// trampoline

const loop = f => {
  let acc = f();

  while (acc && acc.type === recur)
    acc = f(...acc.args);

  return acc;
};


const recur = (...args) =>
  ({type: recur, args});


// sum

const sum = xs => {
  const len = xs.length;

  return loop(
    (acc = 0, i = 0) =>
      i === len
        ? acc
        : recur(acc + xs[i], i + 1));
};


// and run...

const xs = Array(1e5)
  .fill(0)
  .map((x, i) => i);


console.log(sum(xs));

Si un calcul basé sur un trampoline cause des problèmes de performances, vous pouvez toujours le remplacer par une boucle nue.

2
user6445533user6445533 23 mai 2018 à 15:10

L'autre réponse souligne la limitation du nombre d'arguments de fonction, mais je voulais faire une remarque sur votre implémentation de trampoline. Le long calcul que nous exécutons peut vouloir retourner une fonction. Si vous utilisez typeof res === 'function', il n'est plus possible de calculer une fonction comme valeur de retour!

Au lieu de cela, encodez vos variantes de trampoline avec une sorte d'identifiants uniques

const bounce = (f, ...args) =>
  ({ tag: bounce, f: f, args: args })

const done = (value) =>
  ({ tag: done, value: value })

const trampoline = t =>
{ while (t && t.tag === bounce)
    t = t.f (...t.args)
  if (t && t.tag === done)
    return t.value
  else
    throw Error (`unsupported trampoline type: ${t.tag}`)
}

Avant de continuer, obtenons d'abord un exemple de fonction à corriger

const none =
  Symbol ()

const badsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    : badsum ([ n1 + n2, ...rest ])

Nous y jetterons range de chiffres pour le voir fonctionner

const range = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

console.log (range (10))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

console.log (badsum (range (10)))
// 55

Mais peut-il gérer les grandes ligues?

console.log (badsum (range (1000)))
// 500500

console.log (badsum (range (20000)))
// RangeError: Maximum call stack size exceeded

Voir les résultats dans votre navigateur jusqu'à présent

const none =
  Symbol ()

const badsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    : badsum ([ n1 + n2, ...rest ])

const range = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

console.log (range (10))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

console.log (badsum (range (1000)))
// 500500

console.log (badsum (range (20000)))
// RangeError: Maximum call stack size exceeded

Quelque part entre 10000 et 20000, notre fonction badsum provoque sans surprise un débordement de pile.

En plus de renommer la fonction en goodsum, nous n'avons qu'à encoder les types de retour en utilisant les variantes de notre trampoline

const goodsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    ? done (n1)
    : goodsum ([ n1 + n2, ...rest ])
    : bounce (goodsum, [ n1 + n2, ...rest ])

console.log (trampoline (goodsum (range (1000))))
// 500500

console.log (trampoline (goodsum (range (20000))))
// 200010000
// No more stack overflow!

Vous pouvez voir les résultats de ce programme dans votre navigateur ici. Maintenant, nous pouvons voir que ni la récursivité ni le trampoline ne sont en faute pour que ce programme soit lent. Ne vous inquiétez pas, nous le corrigerons plus tard.

const bounce = (f, ...args) =>
  ({ tag: bounce, f: f, args: args })
  
const done = (value) =>
  ({ tag: done, value: value })
  
const trampoline = t =>
{ while (t && t.tag === bounce)
    t = t.f (...t.args)
  if (t && t.tag === done)
    return t.value
  else
    throw Error (`unsupported trampoline type: ${t.tag}`)
}

const none =
  Symbol ()

const range = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

const goodsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? done (n1)
    : bounce (goodsum, [ n1 + n2, ...rest ])

console.log (trampoline (goodsum (range (1000))))
// 500500

console.log (trampoline (goodsum (range (20000))))
// 200010000
// No more stack overflow!

L'appel supplémentaire à trampoline peut devenir ennuyeux, et quand on regarde goodsum seul, on ne voit pas immédiatement ce que done et bounce font là, à moins que ce ne soit peut-être un convention très courante dans plusieurs de vos programmes.

Nous pouvons mieux coder nos intentions de bouclage avec une fonction générique loop. Une boucle reçoit une fonction qui est rappelée chaque fois que la fonction appelle recur. Cela ressemble à un appel récursif, mais vraiment recur construit une valeur que loop gère de manière sûre.

La fonction que nous donnons à loop peut avoir n'importe quel nombre de paramètres, et avec des valeurs par défaut. Ceci est également pratique car nous pouvons désormais éviter la ... déstructuration et la propagation coûteuses en utilisant simplement un paramètre d'index i initialisé à 0. L'appelant de la fonction n'a pas la possibilité d'accéder à ces variables en dehors de l'appel de boucle

Le dernier avantage ici est que le lecteur de goodsum peut voir clairement l'encodage de boucle et la balise explicite done n'est plus nécessaire. L'utilisateur de la fonction n'a pas non plus à se soucier d'appeler trampoline car elle est déjà prise en charge pour nous dans loop

const goodsum = (ns = []) =>
  loop ((sum = 0, i = 0) =>
    i >= ns.length
      ? sum
      : recur (sum + ns[i], i + 1))

console.log (goodsum (range (1000)))
// 500500

console.log (goodsum (range (20000)))
// 200010000

console.log (goodsum (range (999999)))
// 499999500000

Voici notre paire loop et recur maintenant. Cette fois, nous développons notre convention { tag: ... } à l'aide d'un module de balisage

const recur = (...values) =>
  tag (recur, { values })

const loop = f =>
{ let acc = f ()
  while (is (recur, acc))
    acc = f (...acc.values)
  return acc
}

const T =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [T]: t })

const is = (t, x) =>
  t && x[T] === t

Exécutez-le dans votre navigateur pour vérifier les résultats

const T =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [T]: t })

const is = (t, x) =>
  t && x[T] === t

const recur = (...values) =>
  tag (recur, { values })

const loop = f =>
{ let acc = f ()
  while (is (recur, acc))
    acc = f (...acc.values)
  return acc
}

const range = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

const goodsum = (ns = []) =>
  loop ((sum = 0, i = 0) =>
    i >= ns.length
      ? sum
      : recur (sum + ns[i], i + 1))

console.log (goodsum (range (1000)))
// 500500

console.log (goodsum (range (20000)))
// 200010000

console.log (goodsum (range (999999)))
// 499999500000

extra

Mon cerveau est bloqué dans l'équipement d'anamorphisme depuis quelques mois et j'étais curieux de savoir s'il était possible d'implémenter une pile unfold en utilisant la fonction loop présentée ci-dessus

Ci-dessous, nous examinons un exemple de programme qui génère la séquence complète des sommes jusqu'à n. Considérez-le comme montrant le travail pour arriver à la réponse pour le programme goodsum ci-dessus. La somme totale jusqu'à n est le dernier élément du tableau.

C'est un bon cas d'utilisation pour unfold. Nous pourrions écrire ceci en utilisant loop directement, mais le but était d'étirer les limites de unfold alors voici

const sumseq = (n = 0) =>
  unfold
    ( (loop, done, [ m, sum ]) =>
        m > n
          ? done ()
          : loop (sum, [ m + 1, sum + m ])
    , [ 1, 0 ]
    )

console.log (sumseq (10))
// [ 0,   1,   3,   6,   10,  15,  21,  28,  36, 45 ]
//   +1 ↗ +2 ↗ +3 ↗ +4 ↗ +5 ↗ +6 ↗ +7 ↗ +8 ↗ +9 ↗  ...

Si nous utilisions une implémentation unfold non sûre, nous pourrions faire exploser la pile

// direct recursion, stack-unsafe!
const unfold = (f, initState) =>
  f ( (x, nextState) => [ x, ...unfold (f, nextState) ]
    , () => []
    , initState
    )

console.log (sumseq (20000))
// RangeError: Maximum call stack size exceeded

Après avoir joué un peu avec, il est en effet possible d'encoder unfold en utilisant notre stack-safe loop. Le nettoyage de la ... syntaxe de diffusion à l'aide d'un effet push accélère également les choses

const push = (xs, x) =>
  (xs .push (x), xs)

const unfold = (f, init) =>
  loop ((acc = [], state = init) =>
    f ( (x, nextState) => recur (push (acc, x), nextState)
      , () => acc
      , state
      ))

Avec une pile unfold empilable, notre fonction sumseq fonctionne maintenant comme un régal

console.time ('sumseq')
const result = sumseq (20000)
console.timeEnd ('sumseq')

console.log (result)
// sumseq: 23 ms
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., 199990000 ]

Vérifiez le résultat dans votre navigateur ci-dessous

const recur = (...values) =>
  tag (recur, { values })

const loop = f =>
{ let acc = f ()
  while (is (recur, acc))
    acc = f (...acc.values)
  return acc
}

const T =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [T]: t })

const is = (t, x) =>
  t && x[T] === t

const push = (xs, x) =>
  (xs .push (x), xs)

const unfold = (f, init) =>
  loop ((acc = [], state = init) =>
    f ( (x, nextState) => recur (push (acc, x), nextState)
      , () => acc
      , state
      ))

const sumseq = (n = 0) =>
  unfold
    ( (loop, done, [ m, sum ]) =>
        m > n
          ? done ()
          : loop (sum, [ m + 1, sum + m ])
    , [ 1, 0 ]
    )

console.time ('sumseq')
const result = sumseq (20000)
console.timeEnd ('sumseq')

console.log (result)
// sumseq: 23 ms
// [ 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ..., 199990000 ]
3
Thank you 24 mai 2018 à 14:54