n log(n) - Barriere für Sortierfunktionen?
-
rapso: Du hast eine ganz wichtige Eigenschaft der Daten, die Du sortiert hast verwendet, nämlich dass es Daten aus einem festen Bereich waren. Nur in diesem Fall funktioniert Bucketsort so schnell. Dabei nutzt Du aber mehr aus als das pure Vergleichen. Insbesondere benutzt Du, dass es sich um ints handelt. Mit Bucketsort und beschränkter Größe geht das in O(n) Zeit. Ist die Größe beschränkt, geht es immerhin noch in O(n log log n) Zeit (mit ints kann man halt noch rechnen -- damit kann man mehr Information bekommen). Wenn Du Dich auch reine Vergleiche beschränkst, dann geht es nicht schneller als O(n log n). Dazu ein kleiner Beweis.
-
Jeder Vergleich gibt Dir genau 1 bit Information, nicht mehr, aber, wenn Du es geschickt anstellst auch nicht weniger.
-
Es gibt n! verschiedene Permutationen der Eingabemenge. Dein Algorithmus muß sich für jede diese verschiedenen Permutationen leicht unterschiedlich verhalten (würde er beide male exakt dasselbe tun, würde eine der beiden Zahlenfolgen nicht korrekt sortiert).
-
Also muß Dein Algorithmus sich genug Informationen beschaffen, um diese n! verschiedenen Permutationen unterscheiden zu können. Das sind natürlich log(n!) bit Information. Das sind (nachrechnen oder nachschlagen) Ω(n log n) bit benötigte Information.
-
Bei nur einem bit Information pro Vergleich braucht man also Ω(n log n) Vergleiche.
Es sagt niemand, man könne nicht schneller sortieren, nur dass es eben nicht schneller geht mir Vergleichen, das ist völlig unabhängig von Dingen wie Stabilität, in-place oder ähnlichen Dingen. Stell Dir vor, ich geb Dir eine Klasse, die den op< überlädt. Ohne weitere Informationen ist die nlogn-Schranke nicht zu brechen.
Wenn Du's nicht glaubst, dann haben wir ja eine neue Challenge für Dich.
-
-
Ist das sowas wie Godwin's Law?
"In jedem Thread über Algorithmenkomplexität steigt mit zunehmender Länge die Wahrscheinlichkeit, dass jemand damit argumentiert, dass reale Computer endliche Automaten sind. Damit ist die Diskussion beendet. Wer dieses Argument gebracht hat, hat verloren."
-
Bashar schrieb:
Ist das sowas wie Godwin's Law?
"In jedem Thread über Algorithmenkomplexität steigt mit zunehmender Länge die Wahrscheinlichkeit, dass jemand damit argumentiert, dass reale Computer endliche Automaten sind. Damit ist die Diskussion beendet. Wer dieses Argument gebracht hat, hat verloren."
Das war doch nur ein Strohmann von volkard... also Volkard's Law
-
4. es sind keine zusatz allokationen erlaubt
Warum nicht?
5. belibige inputdaten bzw container
Kein Problem, wenn Punkt 4 nicht ist. Aber sortieren in n log n setzt random access container voraus.
6. stabil
Meist nicht das Problem.
Restriktionen sind ok, solange sie vernuenftig sind. Die hier angefuehrten sind nicht oder nur in Ausnahmefaellen vernuenftig.
-
knivil schrieb:
4. es sind keine zusatz allokationen erlaubt
Warum nicht?
Wegen in-place. Eigentlich formuliert man das so, dass nur O(1) zusätzlicher Speicher alloziert werden darf, ich nehme an, das ist auch gemeint.
-
Jester schrieb:
rapso: Du hast eine ganz wichtige Eigenschaft der Daten, die Du sortiert hast verwendet, nämlich dass es Daten aus einem festen Bereich waren. Nur in diesem Fall funktioniert Bucketsort so schnell. Dabei nutzt Du aber mehr aus als das pure Vergleichen.
natuerlich, es war ein spezialisierter fall, ich wollte damit nur aufzeigen, dass man mit mehr wissen ueber die daten und hardware und... durchaus schneller sein kann als n*log(n), das geht selbst mit nur operator< in spezialfaellen.
Wenn Du Dich auch reine Vergleiche beschränkst, dann geht es nicht schneller als O(n log n). Dazu ein kleiner Beweis.
ich weiss ;), aber dir duerfte dann auch klar sein, dass es eine nur durch deine beschraenkung kommt "reine Vergleiche" und "komplettes unwissen ueber alle daten".
und genauso kann ich ebenfalls beschraenkungen einfuehren wie z.b. stabil und ohne extra allokation (also nur compare+swap) und du dann nichtmal n*log(n) erreichen kannst.Es sagt niemand, man könne nicht schneller sortieren, nur dass es eben nicht schneller geht mir Vergleichen, das ist völlig unabhängig von Dingen wie Stabilität, in-place oder ähnlichen Dingen. Stell Dir vor, ich geb Dir eine Klasse, die den op< überlädt. Ohne weitere Informationen ist die nlogn-Schranke nicht zu brechen.
(nur mit vergleichen und komplettem unwissen ueber die daten) ja das stimmt, dagegen sag ich nichts.
nur war mein zweiter punkt, dass n*log(n) eben nicht immer die schranke ist wie manche meinen, sondern sehr einfach durch zusatzverlangen komplexer als das wird und eben auch durch zusatz wissen schneller wird.
Wenn Du's nicht glaubst, dann haben wir ja eine neue Challenge für Dich.
wiederleg erstmal meine aussage
-
Wenn Dir das alles so klar ist, dann frage ich mich, warum Du, obwohl hier sehr klar jeder beschrieben hatte unter welchen Bedingungen nlogn eine untere Schranke ist, ein prolliges "da hab ich mal ne wette gewonnen, es geht nämlich wohl in O(n)" reinwirfst. Wenn Unwissenheit als Grund wegfällt, fallen mir nicht mehr so viele netten Gründe ein.
Wenn Du einfach zusätzlich informieren willst, dann schreib doch Deine zusätzlichen Voraussetzungen dazu und widersprich nicht denen, die auch richtige Sachen gesagt haben. Unter den in obigen Postings genannten Bedingungen ist O(n log n) jedenfalls unbestreitbar optimal.
-
knivil schrieb:
5. belibige inputdaten bzw container
Kein Problem, wenn Punkt 4 nicht ist. Aber sortieren in n log n setzt random access container voraus.
Dem würde ich widersprechen: Merge sort funktioniert wunderbar mit einfach verketteten Listen und liegt trotzdem noch in O(n log n).
-
Jester schrieb:
Wenn Dir das alles so klar ist, dann frage ich mich, warum Du, obwohl hier sehr klar jeder beschrieben hatte unter welchen Bedingungen nlogn eine untere Schranke ist, ein prolliges "da hab ich mal ne wette gewonnen, es geht nämlich wohl in O(n)" reinwirfst. Wenn Unwissenheit als Grund wegfällt, fallen mir nicht mehr so viele netten Gründe ein.
wie ich schon sagte, ich wollte aufzeigen, dass die barriere nur bei speziellen vorraussetzungen gilt. 'wenn man eine sortierfunktion ist' kann man auch schneller oder langsammer sein.
Wenn Du einfach zusätzlich informieren willst, dann schreib doch Deine zusätzlichen Voraussetzungen dazu und widersprich nicht denen, die auch richtige Sachen gesagt haben. Unter den in obigen Postings genannten Bedingungen ist O(n log n) jedenfalls unbestreitbar optimal.
und diese bedingungen standen beim zittierten satz nicht da, deswegen hab ich das beispiel mit meinem lehrer genannt. alle lesen immer n*log(n) und erzaehlen unreflektiert weiter, dass es nur n*log(n) gibt als barriere fuer alle sortierfunktionen.
mit dem zittierten satz will man auch implizieren, dass es unmoeglich ist "schneller" zu sein als n*log(n) vergleiche und gleichzeitig, dass das das optimum ist. beides ist nicht allgemein gueltig.Es ist wahr wenn
-man nur diesen einen vergleichoperator hat
-nichts ueber die menge weiss
-keine weiteren anforderungen an die zu sortierende menge hatnochmal ganz deutlich: unter deinen bedingungen ist n*log(n) richtig. so "if you were a sort function, you'd never break the nlogn barrier" ist es nicht richtig.
-
rapso schrieb:
so "if you were a sort function, you'd never break the nlogn barrier" ist es nicht richtig.
Und den ersten Teil des Zitates hast du überlesen?
Forever comparing, never evaluating on any external scale.
-
rapso schrieb:
so "if you were a sort function, you'd never break the nlogn barrier" ist es nicht richtig.
stimmt, aber wenn Du das komplette Zitat mitnimmst schon: "forever comparing..."
-
knivil schrieb:
4. es sind keine zusatz allokationen erlaubt
Warum nicht?
warum was nicht? wieso das jemand nicht haben wollen wuerde? da gibt es unmengen von gruenden, z.b. das allokationen sehr viel mehr kosten koennen als das sortieren selbst und man dann lieber einen 'komplexeren' algorithmus haben will, der aber garantiert in-place ist. Oder man ist an einem kritischen bereich der nicht wegen speicher limitierungen fehlschlagen darf. oder einfach weil du feste speicher budgets hast und garnicht allokieren kannst.
5. belibige inputdaten bzw container
Kein Problem, wenn Punkt 4 nicht ist. Aber sortieren in n log n setzt random access container voraus.
jap, wenn du belibig allokieren kannst, kannst du auch listen an alles dranknallen und mit merge sort sortieren.
6. stabil
Meist nicht das Problem.
ja, "meist" reicht vielen irgendein sort aus, aus einer lib dem man einfach vertraut schon das richtige zu tun, da ist es einem oft auch egal, ob worst case bei O(n*n) liegt oder best case bei O(n) ist und wenn man die leute fragt was verwendet wird, sagen sie ohne nachzudenken "quicksort", obwohl das 'meist' nicht der fall ist.
Restriktionen sind ok, solange sie vernuenftig sind. Die hier angefuehrten sind nicht oder nur in Ausnahmefaellen vernuenftig.
ich weiss nicht anhand von was du glaubst die allgemeinfaelle so gut zu kennen, aber dennoch gibt es viele verschiedene faelle, entsprechend viele sortier algorithmen und deren komplexitaet reicht entsprechend weit auseinander und ist nicht mit n*log(n) als mass aller dinge als mutter aller grenzen zu setzen.
-
Tim schrieb:
rapso schrieb:
so "if you were a sort function, you'd never break the nlogn barrier" ist es nicht richtig.
Und den ersten Teil des Zitates hast du überlesen?
Forever comparing, never evaluating on any external scale.
nein, hab ich nicht ueberlesen, das war der grund weshalb mir der zweite satz so auffiel.
vielleicht intepretiere ich das falsch. sorry dann. aber es liest sich fuer mich nicht nach 'unter den bedingungen ist es so', sondern 'so funktioniert sortieren: nur vergleichen, kein weiteres wissen''sortieren kann nicht schneller als.. sein'. also eher nach einem suggestiv satz denn nach einer bedingung.aber wenn ihr das alle anders interpretiert, wird es wohl so gemein sein, das war mir vorher nicht bewust. sorry.
-
Christoph schrieb:
Dem würde ich widersprechen: Merge sort funktioniert wunderbar mit einfach verketteten Listen und liegt trotzdem noch in O(n log n).
Wie erhaelst du die Mitte einer Liste?
edit: Ja, ich hab 's ...
@rapso: Du vergleichst zwei Algorithmen, die einfach unterschiedliche Annahmen an die Daten machen. Das ist witzlos. Fuer eine allgemeine Sortierfunktion (auch von natuerlichen Zahlen, unbeschraenkt) ist n log n die untere Schranke. Und wenn die Anzahl der Vergleiche die Komplexitaet bestimmt, dann gibt es zumindestens fuer Zahlen eine Sortierfunktion ganz ohne Vergleiche.
-
rapso schrieb:
6. stabil
Meist nicht das Problem.
ja, "meist" reicht vielen irgendein sort aus, aus einer lib dem man einfach vertraut schon das richtige zu tun, da ist es einem oft auch egal, ob worst case bei O(n*n) liegt oder best case bei O(n) ist und wenn man die leute fragt was verwendet wird, sagen sie ohne nachzudenken "quicksort", obwohl das 'meist' nicht der fall ist.
Ich würde auch sagen, Stabilität ist sehr wichtig. Jedenfalls wenn die zu sortierenen Objekte noch andere Eigenschaften als das Sortierkriterium haben. Sonst gibt es böse Überraschungen. Reine Zahlenarrays kannst du gerne mit Qicksort sortieren.
-
knivil schrieb:
Christoph schrieb:
Dem würde ich widersprechen: Merge sort funktioniert wunderbar mit einfach verketteten Listen und liegt trotzdem noch in O(n log n).
Wie erhaelst du die Mitte einer Liste?
edit: Ja, ich hab 's ...
Und wie?
-
Du brauchst keine Mitte. Einfach die Liste durchgehen und abwechselnd auf zwei Listen verteilen. Dann haste zwei gleichlange Listen.
-
Zu Vergleichsbasiert, stabil, inplace und n log n. Wie wärs mit Heapsort auf einem Schlüssel, dann gleiche Schlüsselbereiche nochmal mit Heapsort nach zweiten Key sortieren. Könnte funktionieren. Muss nochmal nachdenken.