problem: ein array mit gut 300 doubles immer wieder neu sortieren,
benötigt werden nur die besten 1% (5%, 10%) zahlen.
wie ist das am besten in Java realisierbar, wenn das Sortieren so
SCHNELL WIE MÖGLICH erfolgen soll?
Benachrichtigungen
Alles löschen
Small Talk
11
Beiträge
8
Benutzer
0
Reactions
3,526
Ansichten
10 Antworten
wenn nur die oberen paar % gefragt sind, ist häufig ein heap schneller, weil der eben nicht alles sortiert.
genaue werte müsste man aber etwas austesten
Da wäre ich mir nicht so sicher. Hier sind ja einige spezielle Fälle (aka extrem wenige Elemente, nur top x%).
introsort hat komplett eine fast lineare komplexität und ist eine kombination von quicksort und heapsort, falls ich mich richtig erinnere. einfach nach googeln.
bei dir ist es aber ein spezielles problem ... hast du irgendwelche weiteren annahmen über deine zahlen. vielleicht kann man so noch an der performance drehen.
btw. ist es vielleicht moeglich die zahlen in eine andere datenstruktur einzufuegen, wo es dann leichter ist die top 10 % rauszulesen?
es wird wohl unsinnig sein einen sortieralgorithmus zu nehmen der immer den kompletten array sortiert.
Original von soltana
... hast du irgendwelche weiteren annahmen über deine zahlen.
eigentlich nur, dass sie einigermaßen gaußglockenförmig verteilt sind,
habe bei der beschreibung aber übersehen, dass die zahlen auch negativ
sein können, also von ]-1.0; bis +1.0[
der mittelwert liegt aber nicht bei null, sondern meistens knapp darüber.
introsort klingt gut.. mus nur nocheine gute implementation für java finden...
Original von Sphageus
wenn nur die oberen paar % gefragt sind, ist häufig ein heap schneller, weil der eben nicht alles sortiert.
genaue werte müsste man aber etwas austesten
Richtig der Heap is konstanter der Quick kann im Worst Case länger laufen, sonst ist er allerdings schneller ^^
Wie oft willst du das Array denn sortieren?
Bei 300 Einträgen ist es doch fast irrelevant, welchen Algo man verwendet...
Eventuell kommt noch Bucketsort mit O(n) in Frage. Ansonsten kann ich nur Heapsort empfehlen, besonders wenn du nur die obersten % haben willst. Lässt sich auch leichter implementieren und bei 300 Werten fällt auch O(n*log n) kaum ins Gewicht.