Größte/Kleinste Elemente aus einem Array wählen

    Moin,

    Nachdem ich nicht in der Lage war mich in der SB richtig auszudrücken (Deutsche Sprache schwäre Sprache) hier nochmal. (Danke an Xori für seine Geduld mit Personen die so viel verstehen wie ein Ziegelstein :D)

    Problemstellung:
    Es gibt ein Array mit n Elementen welches Zufallszahlen enthält (oder irgendwelche anderen Zahlen, ist im Prinzip egal).
    Aus diesem Array hätte man gerne in möglichst geringer Zeit eine Liste mit den k größten Einträgen in absteigender Reihenfolge. (Also wie z.B. ArrayMax eine "Liste" mit dem größten Eintrag liefert, möchte man eine Liste mit dem größten, dem 2t größten, ... dem k-t größten)

    Dazu kommt man spontan auf die brilliante Idee: Nimm Quicksort und trenne anschließend den oberen Teil des Arrays ab.
    Richtig, genauso kann man es machen. Und wenn man aus einem n = 100 Array die größten 90 Elemente in einer sortierten Rückgabeliste haben will ist das sicherlich der beste Weg. Falls man aus den 100 Elementen aber nur die 5 größten haben will ist es sinnlos das komplette Array zu sortieren.

    Es gibt schon ein paar Lösungen, die aber bestimmt noch nicht perfekt sind. Gesucht ist die schnellste Methode :)

    Was ist schnell ?
    Das ist eine gute Frage. Da es 2 Parameter gibt (n = Arraygröße, k = Anzahl der gesuchten Elemente) ist es unwahrscheinlich, dass eine einzige Funktion auf dem kompletten Spektrum von n und k überall am schnellsten zum Ziel kommt. Wie oben angedeutet kann man QuickSort nicht einfach schlagen, wenn man z.B. von 100 Elementen 90 haben will. Gebraucht werden also funktionen die für Spezialfälle ein besonderst gutes Ergebnis liefern. (z.B. für kleines n, für großes n, für kleines k, für großes k, für k = Wurzel(n), usw usw). Aus diesen Fällen lässt sich im Endeffekt eine Funktion die an vielen Stellen halbwegs optimal läuft zusammenschustern.

    Anbei 2 kleine Testskripte:

    Edit1: Mars02 ist rausgeflogen, weil die Funtkion in allen Fällen deutlich schlechter als Mars03 ist. Neu hinzugekommen ist Mars04, die in einigen Fällen (vorallem bei mittlerem k) etwas schneller ist.

    Edit2: AspirinJunkie hat eine Funktion beigesteuert die in fast allen Fällen schneller ist, als reines Quicksort. Für die UDF und das Testskript bitte in Post 12 nachschauen.

    Da ich ein Diagrammfan bin gibts hier auch ein paar Bildchen :D (Weniger Millisekunden sind wichtig. Also je niedriger die Kurve ist, desto besser.)
    (Peaks in den Diagrammen kommen daher, dass mein Rechner im Hintergrund am Arbeiten ist)
    unnamed.pngunnamed2.pngunnamed3.png

    lg
    M

    Per PN schon geschrieben, hier in Textform nochmal:
    Ich würde bei dem Problem "größten / kleinsten j Elemente" eine Priority Queue, ferner einen Fibonacci Heap (ich glaube ich schrieb per PN vom Binomialheap, bleibt sich gleich, aber Fib-Heap ist irgendwie witziger) nehmen.
    Damit staucht sich die Zeit auf O(n + k), wobei k die Anzahl der gesuchten Elemente beschreibt.
    €: Irgendwas betrachte ich hier gerade immer noch falsch, vielleicht sollte ich ruhig sein :| , es ergibt sich natürlich für jedes Element aus der langen Liste eine Worst-Case Laufzeit von O(log k), also wäre es O(n*log k + k) oder irgendwie sowas.

    Anhang noch, damit sich keiner fragt wie ich auf das O(k) komme: Priority Queue => Extract-Min dauert O(1), also eine konstante Zeit. Da bei einem Fib-Heap die amortisierten Kosten (also wenn man eine Folge von x-Operationen betrachtet) pro Operation ebenfalls in O(1) liegen, und in dem Fib-Heap lediglich die k-Elemente drinnen liegen, dauert es am Ende also höchsten n-mal ein Extract-Min / Insert (und wir gehen ja nicht zurück) sowie k-mal das Extract-Min, wenn wir alles in einen Array schreiben. => O(n * log k + k) (oder so)

    Folglich also O(1) * O(n) + O(1) * O(k) => O(1 * n + 1 * k) => O(1 * (n + k)) => O(n + k)
    Wenn ich mich nicht vertan habe (und das will ich nicht ausschließen), dann liege ich mit der Annahme richtig, dass es in O(n + k) lösbar ist (nachdem ich, hier danke an Mars, unbedingt auf n * k log k hängen bleiben wollte :D )
    Das "Schöne" an AutoIt ist, dass obwohl wir mit einer doppelt verketteten Liste arbeiten müssen (gibt es in AutoIt die Möglichkeit? Ich hoffe.), wir dennoch schneller als Array Operationen sein sollten, da AutoIt Arrays sowieso nicht cache-friendly arbeiten.


    €: Noch ein Anhang: Irgendwo muss in der Überlegung ein Fehler drinnen stecken, sonst wäre ja ein Sortieren über eine PQ innerhalb von O(n) Elementen möglich, nachweisbar ist es aber mindestens O(n * log n), da wir unterscheiden müssen.
    Ich überdenke das am Montag nochmal ;D

    €2: Das Extract-Min dauert amortisiert immer noch log n. Demnach wäre es aber in O(n*log k) zu schaffen, was immer noch besser als O(n*k) sein sollte.

    Es gibt sehr viele Leute, die glauben. Aber aus Aberglauben.
    - Blaise Pascal

    O(n*log(k)) ist drin. Dann wäre der Grenzfall für k -> n = O(n*log(n)) was zufälligerweise genau mit Quicksort zusammenfällt. (Und auch exakt die gleiche Funktionalität wie QS bietet. Aus einer unsortierten Liste eine absteigend/aufsteigend sortierte Liste machen)

    Mein spontaner Vorschlag: per Quick-Select (nicht Quick-Sort!) das n-größte Element ermitteln. Dieses dann als pivot-Element nutzen und alles was kleiner und größer ist in den entsprechenden Topf werfen. Quick-Select sollte O(n) haben.

    Blöderweise hatte ich schon einmal einen solchen programmiert und auch ziemlich optimiert für eine Funktion welche den Median einer Menge in O(n) findet, aber leider finde ich diese nicht mehr. :(

    Edit: wobei ich mir gerade überlege: als Ergebnis des Quick-Select sollte das Array sowieso schon so aufgeteilt sein, das alle Elemente kleiner n links davon stehen, und alle größer n rechts davon. Nur halt in sich noch unsortiert.

    Zitat von AspirinJunkie

    Edit: wobei ich mir gerade überlege: als Ergebnis des Quick-Select sollte das Array sowieso schon so aufgeteilt sein, das alle Elemente kleiner n links davon stehen, und alle größer n rechts davon. Nur halt in sich noch unsortiert.

    Und genau diese Sortierung führt dann zum O(k Log k) ^^

    Es gibt sehr viele Leute, die glauben. Aber aus Aberglauben.
    - Blaise Pascal

    Willst du am Ende eine Funktion haben welche funktioniert oder nur eine 30-seitige Abhandlung darüber schreiben? ;)

    Bei meinem Vorschlag sollte es O(n + (k*log(k)) sein. Außer natürlich man kann die Elemente per Radix-Sort sortieren. Dann kann man es noch ein bisschen kürzen. Wobei die Maßgabe, dass die Ergebnissmenge der k-Elemente sortiert sein muss gar nicht so in der Aufgabe stand.

    Den Vorschlag unterbreitete ich auch bereits, schon ganz zu Anfang, allerdings kam ich irgendwie davon ab... Natürlich sollte das schneller sein als O(n*k) :D

    Es gibt sehr viele Leute, die glauben. Aber aus Aberglauben.
    - Blaise Pascal

    Nicht wirklich. Du schriebst von Heaps. Und da geht es schon los. Dafür wären dynamische Datenstrukturen nötig oder alternativ entsprechend große Arrays welche am Ende erst verkleinert werden können. Quick-Select hingegen macht nur Tauschoperationen auf einem Array und damit in AutoIt die deutlich bessere Variante.

    Deswegen ja meine Frage ob ihr nur auf der Laufzeitverhaltenanalyse stehen bleiben wollt. Dieses sagt erstmal nix darüber aus welche Methode die schnellere sein wird sondern nur wie diese mit der Anzahl der Elemente skalieren.
    Auch Radix-Sort hat z.B. ein besseres Laufzeitverhalten als z.B. Quick-Sort. Aber in AutoIt wird Quicksort trotzdem immer schneller sein.

    Also stattdessen einfach mal umsetzen und dann schauen was passiert.

    Nein Aspirin, ich schrieb in der SB mit ihm über QuickSort und Selection. Mit eben selbst genannter Laufzeit. Hatte aber einen Denkfehler, also eigentlich nicht, und kam deshalb auf O(n*k log k), was ja falsch ist, weil es + ist, wie du eben nanntest.

    Es gibt sehr viele Leute, die glauben. Aber aus Aberglauben.
    - Blaise Pascal

    Also ich hab nicht nur fleißig geredet, sondern auch schon 2 Methoden zur Lösung gebastelt (Die erste zähle ich mal nicht, denn Quicksort + ReDim ist kein Denkaufwand gewesen^^).

    Xor, du bist am Zug :P

    Na dann ich mal.
    Hab meinen erwähnten Ansatz mal mit Hilfe meiner DynArray-UDF umgesetzt.
    Wenn ich das Testskript von oben richtig verstanden habe müsste ich es dann folgendermaßen in die Platzhalterfunktion einbauen:

    Damit hast du eine Waffe ins Feld geschickt, die so schnell keiner besiegen wird :D
    Villeicht gibt es ja doch eine Funktion die "überall" optimal läuft und nicht nur für bestimmte Fälle.

    Vielen Dank, den Startpost aktualisiere ich gleich.

    Da sieht man mal was alles möglich ist, die Zaubershow ist aber noch nicht vorbei, jetzt wird es erst richtig spannend :D

    lg
    M

    Das habe ich bei mir noch gefunden:

    Auch am Arsch geht ein Weg vorbei...

    ¯\_(ツ)_/¯

    Wenn man das ganze als Spezialfall behandelt kann man noch bisschen was rausholen.
    Z.B. indem man absteigend partitioniert und sortiert damit man einfach per ReDim das Ergebnis bekommt.
    Sieht dann z.B. so aus:

    @UEZ
    Bei der Variante wird das Array sortiert und dann der entsprechende Eintrag zurückgegeben.
    Hier suchen wir jedoch nach einer Variante welche eben ohne Sortierung auskommt und somit schneller arbeiten soll.

    AspirinJunkie:
    Die spezielle Methode ist eine Ecke schneller, aber aus Gründen die ich nicht genau finden konnte tauchen im unteren Bereich ab und zu falsche Zahlen auf. Habe ein (hoffentlich möglichst kleines) Beispielskript dazu gebastelt das die Unterschiede zu Quicksort zeigt. Der Fehler tritt nicht immer auf, daher muss das Beispielskript ggf. mehrfach gestartet werden damit andere Zufallszahlen genutzt werden.

    lg
    M

    Danke für den Hinweis.
    Das Pivot-Elemement lag noch im falschen Bereich. Ein ">" in ein "<" geändert und schon sollte es wieder klappen:


    OT: Super Testskript - da macht debuggen Spaß :)

    Einmal editiert, zuletzt von AspirinJunkie (26. September 2016 um 15:55) aus folgendem Grund: Die Grenze wann das interne Insertion-Sort verwendet werden soll wieder korrigiert. (_ArraySort sollte intern ebenfalls auf InsertionSort ausweichen bei kleinen Elementgrößen - dann aber mit Funktionsoverhead)

    Ich schaffe es einfach nicht deine Methode zu überbieten...
    Hab jetzt folgendes ausprobiert: Das Gesamtarray in Teilarrays (Größe 5) spalten (im Übertragenen Sinn. In Wirklichkeit gibts nur eine Neuanordnung), diese mit Swapsort (Weil man den für kleine Arrays gut hardcoden kann, sodass man keine Schleifen oder ähnliches hat) sortieren, anschließend nicht in 1er Schritten durch das Array laufen, sondern in 5er Schritten (Wenn man hinten angekommen ist wieder von Vorne starten und ein element versetzt weitermachen).
    Resultat:
    - in den ersten n/5 der Elementen hat man jeweils die größten Elemente aus den 5er Teilarrays.
    - in den zweiten n/5 Elementen hat man jeweils die 2t größten Elemente aus den 5er Teilarrays... usw
    Anschließend kann man eine meiner beiden Alten Methoden (Mars03 und Mars04) über das teilweise vorsortierte Array laufen lassen, die nun wesentlich schneller zum Ergebnis kommen. Insgesamt ist die Sache zwar schneller als meine bisherigen Versuche, aber wesentlich langsamer als die Post17 Methode. Hab aber noch ein paar Ideen auf lager, mal schauen ob da noch was geht^^

    Auch der von mir hier verwendete Quick-Select hat noch deutliches Optimierungspotential. Das dürfte sich allerdings erst bei sehr großen Arrays und ungewöhnlichen Elementanordnungen bemerkbar machen.

    Aktuell handelt es sich um einen Quick-Select der per Hoare partiniert und das Pivot-Element als Median des ersten, mittleren und letzten Elementes auswählt.
    Hoare ist schon ganz gut aber bei der Auswahl des Pivot-Elementes kann man noch bisschen was rausholen. Wer da Lust hat kann sich ja mal an Introselect oder dem Floyd-Rivest Algorithmus machen.

    Auch hatte ich ganz kurz überlegt ähnlich wie bei QuickSort auf einen Zwei-Pivot Algorithmus umzuschwenken. Nennt sich dann Dual Pivot QuickSelect. Gibt auch ziemlich aktuelle Paper dazu. Allerdings siegte die Vernunft dann ziemlich schnell. Habe sowas schonmal bei meiner Sortierfunktion in der DynArray-UDF implementiert und bin mir daher sicher das ich mir das nicht nochmal antue ;)

    Aber wer unbedingt auf Teufel komm raus noch ein paar Prozente rauskitzeln will (und sei es nur in der Theorie bei der Laufzeitanalyse anstatt in der Praxis) der kann sich gerne daran versuchen.

    Edit:

    Zitat von Mars

    diese mit Swapsort (Weil man den für kleine Arrays gut hardcoden kann, sodass man keine Schleifen oder ähnliches hat) sortieren

    Wenn man auf Spezialfallebene weiter optimieren will ist dein Hinweis echt gut.
    Hab mir mal angeschaut, was es ausmacht 5 Elemente per Abfragen zu sortieren statt per Insertion-Sort (welcher bei der Größe der schnellste Algorithmus sein sollte).
    Und siehe da:

    Es geht also auf der Ebene noch was.
    Eher interessant für meine Sortierfunktion aber wollte es dennoch

    Mir graut es bei dieser Vorstellung :D

    lg
    M