Rekursion vs. Iteration, Mathematische vs. Listen-Operationen

[donp]

Hallo Tim,

Vielleicht möchte jemand anderes noch weiter experimentieren.

Ja, das hab ich gemacht, und zwar mit einer noch anderen Variante, die auch mit Stringumwandlung arbeitet, aber sehr sparsam damit ist:

Die übergebene Zahl wird nur einmalig in einen String gewandelt, und dann wird jede Ziffer wieder einmalig mit parseInt() als Zahl in ein Array geschrieben.

Alle weiteren Schritte arbeiten mit den numerischen Werten des Arrays und es braucht auch keine Rekursion oder Schleife, die ein Zwischenergebnis erneut behandeln müsste, sondern man kommt mit nur z Additionen für eine z-Stellige Zahl aus. So gesehen sollte es eigentlich schneller gehen, als rekursiv oder iterativ mit ständiger Umwandlung in Strings.

Die genaue Arbeitsweise ist hier nebensächlich (ergibt sich aus zahlentheoretischen Überlegungen). Hier also die Funktion zum Beweis, dass relativ wenig Stringoperationen benutzt werden:

  
var qs1 = function (n,r) {             // n = querzusummierende Zahl, r = Radix des Zahlensystems  
  
 r = r||10;                         // Default-Radix ist 10 (Dezimalsystem)  
  
    var a = [],                        // Array für einzelne Ziffern  
        q = 0;                         // einstellige Quersumme  
  
    n = n.toString(r);                 // Zahl als String im enstsprechenden Zahlensystem  
  
    for ( var d=0; d<n.length; d++ ){  // Mit allen Ziffern:  
  
        a[d] = parseInt(n[d],r);       //  Array mit numerischen Ziffern füllen  
    }  
  
    r -= 1;                            // Größte Ziffer im Zahlensystem (Radix-1)  
  
    for ( d=0; d<a.length; d++ ) {     // Mit allen Ziffern:  
  
        if ( q + a[d] > r ){           //  Quersumme würde zweistellig:  
  
            q -= r-a[d];               //    Um größte Ziffer minus aktuelle Ziffer verkleinern  
  
        }else{                         //  Quersumme bleibt einstellig:  
  
            q += a[d];                 //    Um aktuelle Ziffer vergrößern.  
        }  
    }  
  
    return q;                          // Quersumme zurückgeben.  
}  

Dagegen braucht eine normale rekursive Funktion mit ständiger Umwandlung in Strings mehrere toString(), split() und parseInt():

  
var qsSR = function (number) {  
 var digits = number.toString().split("");  
 var sum = 0;  
 for (var i=0; i < digits.length; i++) {  
  sum += parseInt(digits[i]);  
 }  
 return (sum > 9) ? qsSR(sum) : sum;  
}  

Wider Erwarten ist diese rekursive Variante mehr String-Operationen aber doppelt so schnell meine vermeintlich optimierte Version!

Fazit: Performancemäßig viel teurer als Stringumwandlungen sind widerholte Zugriffe auf Array-Elemente. Arrays scheinen wirklich lahme Esel in JacaScript zu sein.

Gruß, Don P