nicht angemeldet
Hallo Længlich,
<offtopic>
Meine Postings fangen (fast) immer mit »Hallo!« an; nur die Sprache wechselt. ;-)
Aha, und "Voghdzuyin!" wäre dann wohl klingonisch ;)
Das Archiv ist überhaupt super: Seit ca. 3 Jahren finde ich so zuverlässig Antworten auf alle meine Fragen, daß ich noch nie einen eigenen Thread starten mußte. :-)
Geht mir ähnlich :)
</offtopic>
Meine Schleife enthält nur einen Vergleich, einen Bitshift und eine Zuweisung. Deine enthält eine Subtraktion, eine Addition, ein bitweises Und, eine Negation, einen Bitshift und zwei Zuweisungen.
Stimmt auffallend.
Beide brauchen, wenn ich das richtig sehe, log₂($n) Durchläufe.
Das nicht. Der Grund, warum ich meine Lösung für schneller gehalten habe, ist gerade, weil sie nicht für jedes n genau log₂ n Schleifendurchläufe braucht:
Für Zweierpotenzen n braucht es gar keine Schleife, und für andere n nur gerade so viele, bis alle gesetzten Bits außer dem hochwertigsten nach rechts "rausgeshiftet" sind. Eine Zahl der Binärform 10...01 z.B. braucht nur einen einzigen Schleifendurchlauf und anschließend eine einzige Shift-Left-Operation. Die maximal nötige Anzahl Durchläufe ist zwar auch log₂ n, aber das tritt nur ein für solche Zahlen n, die die Binärform 11... aufweisen. Ich denke, dass meine Funktion gegenüber deiner umso besser abschneidet, je größer n wird. 1...60000 ist ja eher kleine Zahlen ;-)
Ergebnisse von 5 Script-Aufrufen (in sec):
Also 5 mal von 1...60000, macht insgesamt 300 000 Berechnungen in der angegebenen Gesamtzeit? Oder ist das jeweils der Durchschnitt für 60000 Berechnungen?
Don P: 0.44359087944
Længlich: 0.278346061707
Don P: 0.409577131271
Længlich: 0.289813995361
Don P: 0.392857074738
Længlich: 0.295516967773
Don P: 0.398221969604
Længlich: 0.284239053726
Don P: 0.409832954407
Længlich: 0.280338048935
Wow, pfeilschnell. Das hat mich allerdings überrascht. Muss wohl in Zukunft wirklich mit meinen Schätzungen vorsichtiger sein. Etwas ähnliches ist mir hier nämlich schon einmal passiert. Erst große Töne gespuckt von wegen super Performance meines Codes, und dann eines Besseren belehrt worden, peinlich, peinlich...
Dann habe ich noch versucht, Deine Prüfung (
if (!(($n - 1) & $n)) return $n;) in meine Funktion einzubauen, um gelegentlich die Schleife ganz einzusparen. Davon wurde es interessanterweise aber auch langsamer (lag in der Größenordnung 0.30 bis 0.33).
Das wundert mich inzwischen nicht mehr, denn die wenigen Fälle, wo der Delinquent zufällig eine Zweierpotenz ist und man etwas einsparen kann, fallen wohl kaum ins Gewicht gegenüber der riesigen Mehrheit der Fälle, wo das nicht der Fall ist. Diese zusätzliche Prüfung bremst also meistens nur aus.
Hast Du in Javascript die Zeit gemessen? Sah das da anders aus?
Nein, die Mühe und anschließende Schmach erspare ich mir lieber. Bitweise Operationen sind in JavaScript bekannterweise langsam, weil dabei intern noch Integer-Floatingpoint-Umwandlungen stattfinden müssen. Außerdem ist es unmöglich, Zeitmessungen für länger laufende Scripte in einem Browser zu machen, weil Browser dann zu Abstürzen neigen oder zumindest die Javascript-Ausführung unterbrechen, um den Benutzer zu fragen, ob er das Wahnsinns-Script wirklich weiter laufen lassen will. Vielleicht probiere ich es mal in einer anderen Anwendung, die solches Verhalten nicht zeigt...
Danke jedenfalls für deine ernüchternden Messungen.
Gruß, Don P
Der Martin