n log(n) - Barriere für Sortierfunktionen?

Ben04

http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo12.php

volkard

rapso schrieb:

ja, darueber hat ein lehrer auch mal mit mir gewettet und dass seine gwbasic implementierung von quicksort bewiesenermassen unschlagbar ist.
die simple loesung ihn zu schlagen war ein int array das die haeufigkeit der zahlen akkumuliert und danach im zweiten durchlauf wieder ins array fuettert.

das bricht eindeutig die bedingung, nur die vergleichsoperationen zu nehmen. außerdem war dein algo nur bei diesen eingangsdaten schneller, wo die werte sich oft wiederholt haben.

klar, es ist kein in-place algorithm, aber es gibt viele spezielle algorithmen (und manchmal sogar spezielle befehlssaetze) um sortieren bzw vergleichen zu beschleunigen. siehe z.b. bucketsort

nicht alle typen sind sinnvoll bucketisierbar. welche bucktes würde man für double anlegen, ohne weitere informationen über die verteilung der daten?

rapso schrieb:

es kommt immer drauf an was man an restriktionen setzt, wenn man z.b. stable und inplace sortieren will, bezweifle ich, dass es einen n log n gibt dafuer.

wenn ich dich recht verstanden habe, ist http://lmgtfy.com/?q=inplace+stable+sort ein gegenargument.

rapso

volkard schrieb:

rapso schrieb:

ja, darueber hat ein lehrer auch mal mit mir gewettet und dass seine gwbasic implementierung von quicksort bewiesenermassen unschlagbar ist.
die simple loesung ihn zu schlagen war ein int array das die haeufigkeit der zahlen akkumuliert und danach im zweiten durchlauf wieder ins array fuettert.

das bricht eindeutig die bedingung, nur die vergleichsoperationen zu nehmen. außerdem war dein algo nur bei diesen eingangsdaten schneller, wo die werte sich oft wiederholt haben.

nein, er war grundsaetlich O(n) und bricht keine bedingung, denn die war lediglich schneller zu sein beim sortieren von int. deswegen sagte ich ja: "es kommt immer drauf an was man an restriktionen setzt"

klar, es ist kein in-place algorithm, aber es gibt viele spezielle algorithmen (und manchmal sogar spezielle befehlssaetze) um sortieren bzw vergleichen zu beschleunigen. siehe z.b. bucketsort

nicht alle typen sind sinnvoll bucketisierbar. welche bucktes würde man für double anlegen, ohne weitere informationen über die verteilung der daten?

ich habe rekursiv ein byte je double genommen und damit indiziert.
z.b.

union
{
double foo;
uint8_t bar[sizeof(double)];
};

edit: anmerkung, ich hatte das so sortiert und doppelte werte herauszufiltern, die sortierung war nicht in fliesskomma richtig. aber mich weiss auch nicht worauf du hinaus wolltest um ehrlich zu sein.

rapso schrieb:

es kommt immer drauf an was man an restriktionen setzt, wenn man z.b. stable und inplace sortieren will, bezweifle ich, dass es einen n log n gibt dafuer.

wenn ich dich recht verstanden habe, ist http://lmgtfy.com/?q=inplace+stable+sort ein gegenargument.

verstanden hattest du richtig, und wenn du deinem link gefolgt bist weisst du auch dass das so ist.

unter den Bedingungen:

1. der Algo muß mit jeder Ordnungsrelation funktionieren
2. es darf nichts außer dieser Ordnungsrelation als Vergleichskriterium benutzt werden
(also keine Auswertung von Bitmustern o.ä. beim Sortieren von Zahlen)
3. sequentielle Ausführung

ist die Größenordnung n*log(n) als Anzahl an Vergleichsoperationen im Worst-case nicht zu verbessern.

rapso

u_ser-l schrieb:

unter den Bedingungen:

1. der Algo muß mit jeder Ordnungsrelation funktionieren
2. es darf nichts außer dieser Ordnungsrelation als Vergleichskriterium benutzt werden
(also keine Auswertung von Bitmustern o.ä. beim Sortieren von Zahlen)
3. sequentielle Ausführung

ist die Größenordnung n*log(n) als Anzahl an Vergleichsoperationen im Worst-case nicht zu verbessern.

leg noch was drauf
4. es sind keine zusatz allokationen erlaubt
5. belibige inputdaten bzw container
6. stabil

und dann ist auch n*log(n) nicht zu schaffen.

aber wenn es jemand dennoch schaffen wuerde, waere ich sehr dankbar

volkard

dreimal unfug.

satz:
jeder konkrete algo läuft in O(1) zeit.
beweis:
jede maschine kann nur endlich lange laufen.

auf diesem niveau werden wir uns nicht treffen. bin raus.

Jester

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.

Bashar

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

knivil

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.

Bashar

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.

rapso

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

Jester

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.

Christoph

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).

rapso

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 hat

nochmal 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.

Jester

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..."

rapso

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.

rapso

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.

knivil

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.