Comment voulez-vous étrangler une fonction récursive?

Question

Supposons que je veuille exécuter une fonction récursive qui prendra des semaines, des mois ou même des années. Il renvoie toutes les permutations possibles d'une chaîne en fonction des paramètres spécifiés. Pendant qu'il est en cours d'exécution, je veux être en mesure de voir jusqu'à quel point il progresse - p. combien de permutations il a généré jusqu'à présent. En un mot, je veux exécuter une fonction récursive de très longue durée sans bloquer mon interface utilisateur.

En outre, je voudrais faire cela avec Vanilla ES5, pas en mode strict, et sans WebWorkers. Il devrait être capable de fonctionner dans IE9. Ce que j'ai fonctionne bien tel quel, mais quand je lève numspaces à 10, par exemple, le navigateur se bloque. Donc je suis en supposant que je travaille juste le navigateur trop dur, et "étranglant" la quantité de travail qu'il doit faire aiderait à résoudre ce problème. J'ai essayé d'augmenter les délais de setTimeout de 1 à 250 et même 1000, mais le navigateur est toujours bloqué.

Je suis intéressé par cela simplement parce que j'ai essayé de le faire, et je ne pouvais pas. En outre, je sais pertinemment que ce code est terriblement inefficace et qu'il existe de bien meilleures façons de faire ce que je cherche à accomplir. Alors recommande les!

var inputString = "abcdefghijklmnopqrstuvwxyz"; 
 

 
function allPossibleCombinations(input, length, curstr, callback) { 
 
    if (curstr.length === length) return callback(curstr); 
 
    
 
    (function(n) { 
 
    setTimeout(allPossibleCombinations.bind(n, input, length, curstr + input[n], callback), 1); 
 

 
    n++; 
 
    
 
    if (n < input.length) setTimeout(arguments.callee.bind(n,n), 1); 
 
    })(0); 
 
} 
 

 
var totalResults = 0, 
 
    numDigits = inputString.length, 
 
    numSpaces = 2, 
 
    maxResults = Math.pow(numDigits, numSpaces), 
 
    consoleElement = document.getElementById('console'), 
 
    startTime = +new Date(); 
 

 
console.log("Starting.. expecting", maxResults, "total results..."); 
 

 
allPossibleCombinations(inputString.split(""), numSpaces, "", function(result) { 
 
    totalResults++; 
 

 
    if (totalResults === maxResults) { 
 
    var elapsed = +new Date() - startTime; 
 
    
 
    consoleElement.innerText = "Done."; 
 
    console.log("Completed in", elapsed, "ms!"); 
 
    } else { 
 
    // Do something with this permutation... 
 
    //... 
 
    
 
    // Show progress... 
 
    var progress = ((totalResults/maxResults) * 100).toFixed(2) * 1; 
 
    consoleElement.innerText = progress + "%"; 
 
    } 
 
});

<div id="console"></div>

Answer 1

Vous obtenez près avec le setTimeout, mais la mise en œuvre actuelle des files d'attente toutes les minuteries pour un préfixe donné à la fois, ce qui entraîne un nombre exponentiel de minuteries et épuisement de la mémoire rapide. Un petit changement serait de créer un autre rappel pour indiquer l'achèvement et l'utiliser pour attendre les appels récursifs, ne tenant plus d'une minuterie à la fois:

var inputString = "abcdefghijklmnopqrstuvwxyz"; 
 

 
function allPossibleCombinations(input, length, curstr, resultCallback, doneCallback) { 
 
    if (curstr.length === length) { 
 
    resultCallback(curstr); 
 
    doneCallback(); 
 
    return; 
 
    } 
 
    
 
    var n = 0; 
 
    
 
    (function next() { 
 
    if (n === input.length) { 
 
     doneCallback(); 
 
     return; 
 
    } 
 
    
 
    allPossibleCombinations(
 
     input, length, curstr + input[n], 
 
     resultCallback, 
 
     function() { 
 
     n++; 
 
     setTimeout(next, 0); 
 
     }); 
 
    })(); 
 
} 
 

 
var totalResults = 0, 
 
    numDigits = inputString.length, 
 
    numSpaces = 4, 
 
    maxResults = Math.pow(numDigits, numSpaces), 
 
    consoleElement = document.getElementById('console'), 
 
    startTime = +new Date(); 
 

 
console.log("Starting.. expecting", maxResults, "total results..."); 
 

 
allPossibleCombinations(
 
    inputString.split(""), numSpaces, "", 
 
    function (result) { 
 
    totalResults++; 
 

 
    // Do something with this permutation... 
 
    //... 
 

 
    // Show progress... 
 
    var progress = ((totalResults/maxResults) * 100).toFixed(2) * 1; 
 
    consoleElement.innerText = progress + "%"; 
 
    }, 
 
    function() { 
 
    var elapsed = +new Date() - startTime; 
 

 
    consoleElement.innerText = "Done."; 
 
    console.log("Completed in", elapsed, "ms!"); 
 
    });

<div id="console"></div>

qui est vraiment lent, cependant. Penser la façon dont vous pouvez écrire cela comme un générateur:

function* strings(input, length, current) { 
    if (current.length === length) { 
     yield current; 
     return; 
    } 

    for (let i = 0; i < input.length; i++) { 
     yield* strings(input, length, current + input[i]); 
    } 
} 

et traduire que dans un système où le rappel est responsable de la reprise de génération:

function strings(input, length, current, yield_, continue_) { 
    if (current.length === length) { 
     yield_(current, continue_); 
     return; 
    } 

    var i = 0; 

    (function next() { 
     if (i === input.length) { 
      continue_(); 
      return; 
     } 

     strings(input, length, current + input[i++], yield_, next); 
    })(); 
} 

vous pouvez avoir la flexibilité de fixer une minuterie rarement comme vous le souhaitez pour la performance.

"use strict"; 
 

 
function countSequences(n, k) { 
 
    var result = 1; 
 

 
    for (var i = 0; i < k; i++) { 
 
     result *= n--; 
 
    } 
 

 
    return result; 
 
} 
 

 
function strings(input, length, current, yield_, continue_) { 
 
    if (current.length === length) { 
 
     yield_(current, continue_); 
 
     return; 
 
    } 
 

 
    var i = 0; 
 

 
    (function next() { 
 
     if (i === input.length) { 
 
      continue_(); 
 
      return; 
 
     } 
 

 
     var c = input[i++]; 
 
     strings(input.replace(c, ''), length, current + c, yield_, next); 
 
    })(); 
 
} 
 

 
var inputString = "abcdefghijklmnopqrstuvwxyz"; 
 
var totalResults = 0; 
 
var numDigits = inputString.length; 
 
var numSpaces = 5; 
 
var maxResults = countSequences(numDigits, numSpaces); 
 
var consoleElement = document.getElementById('console'); 
 
var startTime = +new Date(); 
 

 
console.log("Starting… expecting", maxResults, "total results."); 
 

 
strings(
 
    inputString, numSpaces, "", 
 
    function (result, continue_) { 
 
     if (totalResults++ % 1000 === 0) { 
 
      var progress = (totalResults/maxResults * 100).toFixed(2); 
 
      consoleElement.innerText = progress + "% (" + result + ")"; 
 
      setTimeout(continue_, 0); 
 
     } else { 
 
      continue_(); 
 
     } 
 
    }, 
 
    function() { 
 
     var elapsed = +new Date() - startTime; 
 

 
     consoleElement.innerText = "Done."; 
 
     console.log("Completed in", elapsed, "ms!"); 
 
    });

<div id="console"></div>

(Ce style est toujours non-optimale, mais il ne sera jamais fini 26 peu importe la façon dont les opérations individuelles sont rapides.)