Geschwindigkeitstest: Java, dann VB und dann C++

SeppJ

Atlan schrieb:

Java benutzt den Quicksort, C++ einen unbekannten Algorithmus mit O(n log n) im Worst Case, während der Quicksort O(n2) im Worstcase hat.
Es ist aber fast sicher, dass C++ nicht den Quicksort verwendet, da O(n log n) als Worstcase gefordert wird und nicht als Durchschnitt. Vielleicht verwendet C++ Introsort.

C++ macht keine spezielle Vorgabe an die Sortieralgorithmen, nur an die Komplexität. Ich weiß aus dem Stand nicht, ob Java einen speziellen Algorithmus verlangt oder auch nur Komplexitätsvorgaben macht, aber Quicksort wird in Java schon lange nicht mehr benutzt. Der Worst-Case ist einfach inakzeptabel.

Aktuelle Implementierungen in Standardbibliotheken benutzen diverse Algorithmen mit O(n*log n) als Worst-Case. Beispiele, die tatsächlich praktisch genutzt werden, sind Timsort (Java, Python, andere) und Introsort (diverse C++-Standardbibliotheken). Die tun sich alle gegenseitig nicht viel. Der Unterschied, den du hier siehst, sind höchstwahrscheinlich die fundamentalen Unterschiede, wie Daten in den verschiedenen Sprachen gehandhabt werden.

hustbaer

Atlan schrieb:

Es ist aber fast sicher, dass C++ nicht den Quicksort verwendet, da O(n log n) als Worstcase gefordert wird und nicht als Durchschnitt. Vielleicht verwendet C++ Introsort.

Wobei Introsort ja auch nur ein Quicksort ist der ab einer bestimmten Verschachtelungstiefe die Reissleine zieht und auf Mergesort umschaltet.
Bei nem sortierten Input kann das also keinen grossen Unterschied machen, da hier Introsort niemals mergen wird. Was bleibt ist lediglich der minimale Aufwand die Verschachtelungstiefe mitzuführen und mit einem Grenzwert zu vergleichen.

Ihr trefft aussagen über Java, die man so nicht stehen lassen kann. Mag auch ein wenig an wenig vertrauenswürdigen Nicks liegen. Eine Art Vorsortierung, modifizierter Quicksort und MergeSort finden dort Anwendung. Sortierte Listen n, alle anderen Fälle n*log_2(n). Wenn man sich nicht gerade etwas konstruiert, was schwer zu konstruieren ist, würde n^2 in der Praxis auch bei Qs nie erreicht. Möchte man testen, muss man schon mit einer zufallszahlengeneratorverteilen Liste testen. C++ wird nicht durch seine Geschwindigkeit langsamer sein.

SeppJ

EinGastredner schrieb:

Wenn man sich nicht gerade etwas konstruiert, was schwer zu konstruieren ist, würde n^2 in der Praxis auch bei Qs nie erreicht.

Das Problem ist aber, dass ein böser Hacker eben genau das tut und damit deinen Server DOSt, wenn du Quicksort benutzt. Daher kannst du in der Praxis kein naives Quicksort einsetzen. Die anderen Algorithmen sind ja auch nicht wirklich schlechter. Viele davon setzen schließlich auf Quicksort auf.

kurze_frage

wie wertlos ein publizierter Benchmarks ist kann man daran sehen um wie viel schneller C als C++ bei einzelnen Tests ist.
Denk ich mir mal, denn entweder muss C++ genauso schnell sein weil ich den gleichen Code verwenden kann der den selben Output erzeugen müsste, oder schneller weil ich an stellen wo C void* nutzt Typen benutzen kann.

benchmarksgame.alioth.debian vergleicht ja auch nicht Sprachen sondern Sprache und Implementierung da die Implementierungen doch sehr unterschiedlich sind.

siehe zB binary tree C und C++ Implementierungen, da bekommt man ja hier im Forum bessere C++ Versionen.

hustbaer schrieb:

EDIT: Findet jemand ne Email Adresse wo man da mal hinschreiben könnte?

Evtl. darüber:

http://benchmarksgame.alioth.debian.org/play.html

@atlan: Mag sein, dass D nicht schlecht ist. Bietet aber nicht dieselbe Sicherheit wie rust und ist außerdem nicht offen.

Atlan

@SeppJ
Ich benutze die Oracle Implementierung der Java Standardbibliothek. Dort wird eine Methode mit DoublePivotQuicksort im Namen aufgerufen. Vielleicht ist das eine Optimierung vom Quicksort oder einfach der Name der Methode.

@Benchmark
Das mag sein. Es ist aber womöglich ausgereifter, weil älter und der Wechsel von C++ ist sehr einfach, weil die Syntax sehr ähnlich ist.

Mechanics

Wär mir neu, dass D ausgereift sein soll.

kurze_frage

Benchmark schrieb:

@atlan: Mag sein, dass D nicht schlecht ist. Bietet aber nicht dieselbe Sicherheit wie rust und ist außerdem nicht offen.

dmd und die Standard-Bibliothek ist unter der boost Lizenz
dann gäbs noch gdc oder ldc als Compiler

Welche Offenheit fehlen dir jetzt genau bei D?

kurze_frage schrieb:

Benchmark schrieb:

@atlan: Mag sein, dass D nicht schlecht ist. Bietet aber nicht dieselbe Sicherheit wie rust und ist außerdem nicht offen.

dmd und die Standard-Bibliothek ist unter der boost Lizenz
dann gäbs noch gdc oder ldc als Compiler

Welche Offenheit fehlen dir jetzt genau bei D?

Der offizielle Backend-Compiler ist nicht Open Source und rust ist unter anderem deswegen so erfolgreich, weil es ein Community-Projekt ist. Bei jedem Release findest du neue Beteiligte in den Release-Notes.

kurze_frage

ShadowClone schrieb:

kurze_frage schrieb:

Benchmark schrieb:

@atlan: Mag sein, dass D nicht schlecht ist. Bietet aber nicht dieselbe Sicherheit wie rust und ist außerdem nicht offen.

dmd und die Standard-Bibliothek ist unter der boost Lizenz
dann gäbs noch gdc oder ldc als Compiler

Welche Offenheit fehlen dir jetzt genau bei D?

Der offizielle Backend-Compiler ist nicht Open Source und rust ist unter anderem deswegen so erfolgreich, weil es ein Community-Projekt ist. Bei jedem Release findest du neue Beteiligte in den Release-Notes.

dmd backend ist ein bisschen Chaos, viele Files sind jedoch schon unter der boost Lizenz, einige nicht oder noch nicht, da ich nicht Teil der existierenden D Community bin welche es sehr wohl gibt bin ich über die weiteren Pläne nicht informiert.
Weiters es gibts noch die anderen Compiler, ldc und gdb, von daher finde ich die Formulierung das D 'nicht offen ist' etwas zu stark gewählt.