| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Critic
oberflächlich
Anmeldungsdatum: 22.07.2003
Beiträge: 16380
Wohnort: Arena of Air
|
 (#1647658) Verfasst am: 10.06.2011, 16:48 Titel: |
 |
|
Meine Quelle fuer die Performance-Geschichte geht buchstaeblich ganz an den Anfang zurueck: naemlich "Thinking in Java", 1st Edition. Dort wird im Prinzip zum ersten Mal erwaehnt, dass die Erzeugung von Objekten sehr viel teurer ist als eine solche mathematische Operation. Aber auch in spaeteren Werken wird die Erzeugung von Objekten immer wieder thematisiert, was Moeglichkeiten zur Laufzeitverringerung angeht. Bruce Eckel gibt fuer eine einfache Zuweisung einen Performance-Index von 1 an, eine Zuweisung eines Array-Elements dauere 2.7-mal solange, die Erzeugung eines Objektes 980-mal solange, eines Array schliesslich 3100-mal solange.
Natuerlich nur ganz quick-and-dirty implementiert, sind auf dem Uraltrechner, an dem ich jetzt gerade sitze, eine Million Multiplikationen von long-Werten im Mittel kaum messbar (maximal 60 Millisekunden, es gibt aber auch viele Iterationen, bei denen nicht einmal eine Millisekunde vergeht, so dass der Durchschnitt an Laufzeitbedarf sehr gering zu sein scheint), wenn ich das aber per Boxing und Unboxing realisiere, also immer schoen Objekte als Wrapper erzeuge, dauert es im Mittel 2000 Millisekunden.
Die Laufzeitordnung ist da ein anderer Aspekt: O(n log n) fuer Multiplikationsalgorithmen scheint eine ziemlich robuste untere Schranke zu sein. Der Begriff der "superschnellen DFT" fand sich in der Definition des Schoenhage-Strassen-Algorithmus, wo (ich habe _das_ noch nicht durchgearbeitet) mit einigen mathematischen Tricks gearbeitet wird, um vielleicht bei grossen Stellenzahlen einen kleinen Laufzeitgewinn zu erzielen.
_________________
"Die Pentagon-Gang wird in der Liste der Terrorgruppen geführt"
Dann bin ich halt bekloppt. 
"Wahrheit läßt sich nicht zeigen, nur erfinden." (Max Frisch)
|
|
| Nach oben |
|
 |
brf
registrierter User
Anmeldungsdatum: 25.05.2010
Beiträge: 366
|
| (#1647706) Verfasst am: 10.06.2011, 20:47 Titel: |
|
|
Ok. Jetzt ist es klar: Das Erzeugen von Objekten ist teurer als eine math Op wie +. Diese betrifft double-Zahlen.
Bei BigInteger ist das umgekehrt. Die kosten je nach Länge (aka Ziffernzahl).
Und O(n*logn) ist keine untere Schranke. Schönhage-Straßen ist schneller (trotz O(n*log(n)*log(log(n)))), weil die Konstante in praktischen Fällen kleiner ist.
siehe How fast can we multiply, Knuth, the art of computer programming.
Es gibt derzeit noch keine bewiesene untere Schranke.
|
|
| Nach oben |
|
|
Critic
oberflächlich
Anmeldungsdatum: 22.07.2003
Beiträge: 16380
Wohnort: Arena of Air
|
| (#1647791) Verfasst am: 10.06.2011, 23:44 Titel: |
|
|
| brf hat folgendes geschrieben: | Ok. Jetzt ist es klar: Das Erzeugen von Objekten ist teurer als eine math Op wie +. Diese betrifft double-Zahlen.
Bei BigInteger ist das umgekehrt. Die kosten je nach Länge (aka Ziffernzahl).
Und O(n*logn) ist keine untere Schranke. Schönhage-Straßen ist schneller (trotz O(n*log(n)*log(log(n)))), weil die Konstante in praktischen Fällen kleiner ist.
siehe How fast can we multiply, Knuth, the art of computer programming.
Es gibt derzeit noch keine bewiesene untere Schranke. |
(Nur noch zur Anmerkung, ehe ich mich blamiere  : Die Konstante hatte ich tatsächlich gar nicht betrachtet . Die Komplexitätsaussage ist natürlich (aus naheliegenden Gründen) auf ein bestimmtes Maschinenmodell bezogen, in dem nicht noch betrachtet wird, wieviele Operationen der Compiler oder die VM aus der Anweisung generiert und wie man den Algorithmus praktischerweise implementieren sollte, deswegen meine Argumentation.
Der Einwand ist auch richtig, daß OO, Rekursion etc. zwar einen gewissen Overhead mit sich bringen, aber eben auch viele Probleme damit effizienter (oder ggf. überhaupt erst) gelöst werden können. Nur zeigt das kleine Beispiel mit der Laufzeit eben auch, daß man, wenn man sich in einer bestimmten Sprache bewegt, auch da immer noch die Möglichkeit hat, den Algorithmus so zu implementieren, daß man Laufzeit einspart und so schneller und speichereffizienter zum Ergebnis kommt.
Die Komplexität der Algorithmen, die FFT verwenden, hängt indessen an der Komplexität der FFT. Zumindest wurde unter gewissen Bedingungen eine \Omega(n log n)-Schranke bewiesen, es ist allerdings nicht klar, ob die Bedingungen allgemeingültig sind. Der beste derzeit bekannte Algorithmus hat eine Laufzeit von 34/9 n log n Multiplikationen und Additionen für eine FFT auf einem Polynom der Stelligkeit n, aber es ist eben nicht bewiesen, daß dies der bestmögliche Algorithmus ist (Link).)
_________________
"Die Pentagon-Gang wird in der Liste der Terrorgruppen geführt"
Dann bin ich halt bekloppt.
"Wahrheit läßt sich nicht zeigen, nur erfinden." (Max Frisch)
|
|
| Nach oben |
|
|
|
FAQ 
Suchen 
Mitgliederliste 
Nutzungsbedingungen 
Benutzergruppen 
Links
Registrieren
Profil 
Einloggen, um private Nachrichten zu lesen 
Login 
