nicht angemeldet
Hallo Struppi*,
Aber irgendwie funktioniert die Funktion auch nicht richtig oder ich hab nicht verstanden was der Parameter b sein soll, welche Basis? Die Quersumme ist die Summe aller Ziffern. Aber bei
alert( quersumme(1234, 10));kommt eine Endlosschleife.
Daniel hat da einen Flüchtigkeitsfehler gemacht und vergessen, die Summe pro Iteration wieder auf Null zu setzen. Konsequenterweise wird mit einer immer größer werdenden Summe gerechnet. So funktioniert es:
~~~javascript
function quersumme(x, b) {
while (x >= b) {
var sum = 0;
while (x > 0) {
sum += x % b;
x = Math.floor(x / b);
};
x = sum;
};
return sum;
};
> Naja. ... du hast zwei Schleifen ... zwei Mathematische Funktionen. Das halte ich für uneleganter und mit Sicherheit auch langsamer.
Wieso das denn? Computer sind auf Berechung ausgelegt, mathematische Funktionen lassen sich da wunderbar in wenig Maschinencode übersetzten und sind da also schneller als ständiges Stringsplitting, Listenmanipuliation und Typumwandlung.
Auch Rekursion ist oft ineffizienter als eine Schleife – bei Rekursion muss ein neuer Kontext für jeden Funktionsaufruf angelegt werden, von denen es ja nicht gerade wenig gibt. Eleganter ist Rekursion aber, ja.
Ich konnte mich nicht zurückhalten, und mal alle Permutationen von Rekursion vs. Iteration und Mathematische Lösung vs. Array/String-lösung konkret auf die wiederholte Ablaufgeschwindigkeit zu testen:
~~~javascript
#!/usr/bin/env js
var ITERATIONS = 1000000;
// Helfermethödchen
Number.prototype.times = function (func) {
for (var i = 1; i < this +1 ; i++) {
func(i)
};
};
// Alle Lösungen praktisch in einem Array
var solutions = [
{ desc : "a) Iterativ (klassische for-Schleife), mit ständiger Umwandlung in Strings",
func : function (number) {
var digits = number.toString().split('');
while (digits.length > 1) {
var sum = 0;
for (var i=0; i < digits.length; i++) {
sum += parseInt(digits[i]);
};
digits = sum.toString().split('');
};
return digits[0];
}
},
{ desc : "b) Iterativ (JS 1.6 Array.forEach), mit ständiger Umwandlung in Strings",
func : function (number) {
var digits = number.toString().split('');
while (digits.length > 1) {
var sum = 0;
digits.forEach(function (d) {
sum += parseInt(d);
});
digits = sum.toString().split('');
};
return digits[0];
}
},
{ desc : "c) Rekursiv, mit ständiger Umwandlung in Strings",
func : function (number) {
var self = solutions[2].func
var digits = number.toString().split("");
var sum = 0;
for (var i=0; i < digits.length; i++) {
sum += parseInt(digits[i]);
};
return (sum > 9) ? self(sum) : sum;
}
},
{ desc : "d) Iterativ, mit mathematischen Funktionen",
func : function (number) {
while (number > 9) {
var sum = 0;
var x = number;
while (x > 0) {
sum += x % 10;
x = Math.floor(x / 10);
};
number = sum
};
return number;
}
},
{ desc : "e) Rekursiv, mit mathematischen Funktionen",
func : function (number) {
var self = solutions[4].func;
if (number > 9) {
var lastDigit = number % 10;
number = Math.floor(number / 10);
return self(self(number) + lastDigit);
} else {
return number;
};
}
}
];
var tests = [
{ number : 9631,
digitsum : 1 },
{ number : 12345,
digitsum : 6 },
{ number : 11,
digitsum : 2 },
{ number : 23,
digitsum : 5 },
{ number : 123,
digitsum : 6 },
{ number : 9,
digitsum : 9 }
];
// Sanity-Checking
solutions.forEach( function (sol) {
if(!(tests.every(function (test) {
return sol.func(test.number) == test.digitsum;
}))) {
throw 'Fehler in der Lösung "' + sol.desc + '"';
};
});
// Und nun das konkrete Testen
function timeIt (sol) {
print(sol.desc);
var start = new Date();
(3).times(function (i) {
print("Iteration " + i);
ITERATIONS.times(sol.func);
});
var end = new Date();
// Messfehlerverringerung
return Math.floor((end -start) / 3);
};
var results = solutions.map(function (sol) {
return [sol.desc, timeIt(sol)];
});
results.sort(function (a, b) { return a[1] - b[1]; });
(2).times(function () {print()});
print("Für " + ITERATIONS + " Iterationen brauchen die diversen Lösungen sortiert:");
results.forEach(function (result) {
print(result[0] + " : " + result[1] + "ms (im Durchschnitt: " + (result[1]/ITERATIONS) + "ms)");
});
Da ich etwas viel Spaß mit Mozillas Array-Methoden aus JS 1.6 hatte (Sorry ;), hab ich noch Variante b) dazugemischt, um den Vergleich on Array.forEach zu einer normalen For-Schleife zu haben. Und bei Variante e) hab ich die Rekursion eventuell etwas übertrieben.
Gerne hätte ich noch eine Lösung mit Array.reduce gebastelt, aber in meinem Spidermonkey hatte ich nur JS 1.6 zur Verfügung.
Die Resultate:
Für 1000000 Iterationen brauchen die diversen Lösungen sortiert:
d) Iterativ, mit mathematischen Funktionen : 7191ms (im Durchschnitt: 0.007191ms)
e) Rekursiv, mit mathematischen Funktionen : 14124ms (im Durchschnitt: 0.014124ms)
c) Rekursiv, mit ständiger Umwandlung in Strings : 35606ms (im Durchschnitt: 0.035606ms)
a) Iterativ (klassische for-Schleife), mit ständiger Umwandlung in Strings : 41591ms (im Durchschnitt: 0.041591ms)
b) Iterativ (JS 1.6 Array.forEach), mit ständiger Umwandlung in Strings : 69194ms (im Durchschnitt: 0.069194ms)
Klarer Gewinner: Iterativ & Mathematisch.
Ich war zuerst überrascht, dass die rekursiven Varianten doch so gut sind. Mit einer zweiten Überlegung liegt das aber wohl daran, dass ich als Berechnungszahlen nur Zahlen mit 6 Stellen angegeben haben – da sind einfach nicht so viele Ziffern, die größere Rekursionstiefen erfordern würden. Allerdings hatte ich bei einigen Versuchen mit größeren Zahlen schon exponential-basierte Rundungsfehler ab 17 Ziffern – bei Quersummen ist das nicht so sonderlich toll.
Was mich dann doch etwas aus den Socken gehauen hatte, war das schlechte Abschneiden der iterativen Lösung mit Array.forEach. Klar, durch den iterativen Ansatz könnte es nicht parallel arbeiten (falls in Spidermonkey Unterstützung dafür vorhanden ist); aber ich hätte schon gedacht, dass der native Code einen Hauch schneller bei der Abarbeitung wäre, als der durch die for-Schleife erzeugte Syntaxtree/Bytecode/Whatever.
Vielleicht möchte jemand anderes noch weiter experimentieren.
Tim*
* Es fehlt ein Haddock. Eindeutig.
Der Martin
Struppi