Das Elend unter den Sortieralgorithmen
Herrje, die deutsche Informatik geht den Bach runter.
Gestattet mir die Alter-Knacker-Formulierung, es muss eben sein: Zu meiner Zeit war das mal in Informatik so üblich, dass man neue Algorithmen plausibel und nachvollbar beschreibt, ihr Zustandekommen, ihre Funktion. Dann war es so üblich, dass man deren Korrektheit darlegt. Und deren Laufzeitverhalten rechnerisch nachweist.
Und es war mal in Informatik üblich, eigentlich so in den ersten Semestern, dass man die bekannten Sortieralgorithmen rauf und runter lernt, und zudem lernt, wie man deren Aufwand und Korrektheit zeigt.
Ein Leser weist mich gerade auf dieses Paper über den angeblich neu entwickelten Algorithmus „RunSort” hin, das mir echt die Socken ausgezogen hat. Als Autor ist ein gewisser Professor Kowalk von der Uni Oldenburg angegeben, was vermutlich dieser Professor Wolfgang P. Kowalk sein dürfte. (Mal unterstellt, das Ding ist echt und kein untergeschobener Hoax.)
Man muss sich einfach mal den Stil des Papers durchlesen. Das liest sich wie von Laien für Laien geschrieben.
Sortieren ist weiterhin eine wichtige Anwendung für Algorithmen.
Was ist das für eine schräge Aussage? Eine „Anwendung für Algorithmen”?
Dabei kommt es in heutigen Systemen in erster Linie auf Geschwindigkeit und Sicherheit an; Speicherplatz ist eher von untergeordneter Bedeutung, da gegenwärtige Systeme meistens über sehr viel Speicherplatz verfügen. Außerdem werden Datensätze in modernen Programmiersprachen wie Java meistens nicht mehr direkt im Speicher sondern auf dem Heap abgelegt und nur noch über Referenzen angesprochen, so dass zusätzlicher ‘Speicher’ i.d.R. nur eine zusätzliche Referenz bedeutet, was z.B. bei doppelt verketteten Listen zum Standardzusatzaufwand gehört.
Ach, du liebe Güte.
Ja, Geschwindigkeit ist wichtig. Klar. Aber was ist „Sicherheit” eines Sortieralgorithmus? Dass der Prozessor nicht durchbrennt? Oder ist vielleicht doch Korrektheit gemeint? Ja, das wär natürlich schön, wenn Sortieralgorithmen korrekt wären und richtig sortieren würden, bei »heutigen Sytemen« erwartet man das neuerdings. Früher war das ja nicht so wichtig, da hat man es wohl nicht so ernst genommen, ob ein Sortieralgorithmus die Daten in die richtige Reihenfolge bringt, die hat man mehr aus sportlichen Gründen angewandt.
Und Speicheraufwand? Nöh, interessiert nicht mehr, weil heutige Systeme ja „sehr viel Speicherplatz haben”. Wir rechnen nicht mehr, die der Speicheraufwand von der Zahl der zu sortierenden Elemente abhängt, weil wir ja heute „sehr viel” Speicher haben. Was übrigens nicht stimmt. Wir haben zwar mehr Speicher als früher, aber wir sortieren auch mehr Daten als früher. Man muss sich nur mal vorstellen, was BND und NSA so alles sortieren müssen.
Und dass moderne Programmiersprachen wie Java die Daten meistens „nicht mehr im Speicher sondern auf dem Heap” ablegen? Sorry, wenn ich das mal so sage, aber der Heap ist Teil des Speichers. Und auch die alten Programmiersprachen haben durchaus Speicher verwendet. Es gab auch früher nur sehr wenige Programmiersprachen, die ohne Speicher auskamen. 😉
Und Daten über „Referenzen” anzusprechen ist ja auch so eine ganz neue Erfindung von Java. In C und Assembler hieß das nämlich Pointer. Und nur die allerdämlichsten Leute haben beim Sortieren die Daten umkopiert und nicht nur Pointer permutiert.
Sortieren wird heute in vielen Anwendungen verwendet. Neben den üblichen Anwendungen in der Datenverwaltung werden z.B. auch in 3D-Programmen Sortieralgorithmen benötigt, um Objekte in einer Reihenfolge abhängig von der Entfernung zu zeichnen, z.B. semitransparente Objekte, bei denen hintere Objekte durch vordere ‘durchscheinen’.
Jo. Sortieren wird heute in vielen Anwendungen verwendet. Das ist wohl wahr. Und ein hervorragendes Beispiel für die Notwendigkeit von Sortieralgorithmen sind „3D-Programme”, bei denen hintere Objekte durch semitransparente durchscheinen. Das muss dem Publikum des Papers ja auch erst mal gesagt werden, was ein Sortieralgorithmus ist, wozu der gut ist, und dass man die heute verwendet. 3D-Programme kennt jeder, und jeder wird einsehen, dass man durch durchsichtige Objekte auch durchsehen können muss. Sortieralgorithmen sind die, die Durchsichtiges durchsichtig machen. Wow.
Wenn ich mir das so überlege, kann man die Literatur über Sortieralgorithmen der letzten 30 Jahre einfach wegwerfen, denn niemand hat darin erklärt, dass Sortieren durchsichtig macht. Warum hat mir das niemand früher gesagt?
Und wie fortschrittlich und modern die Forschung heute ist, zeigt sich auch an den Qualitätskriterien, die für Sortieralgorithmen aufgestellt werden, und die die mit Blindheit geschlagene Fachwelt in den letzten 30, 40, 50 Jahren des Sortierens nicht erkannt hat:
Hier spielen alle drei genannten Eigenschaften eine wichtige Rolle. Stabilität wird benötigt, um bei gleicher Entfernung eine gegebene Ordnung nicht zu verletzen, da Objekte sonst ‘flackern’ würden. Ordnungsverträglichkeit wird benötigt,da sich in diesen Anwendungen die Ordnung einer Liste von Objekten nur wenig oder meist gar nicht ändert, so dass die Sortierung, die mehrere zig-Male in der Sekunde durchgeführt werden muss, in den meisten Fällen hinreichend schnell durchgeführt werden kann.
Äh, jo. Gute Sortieralgorithmen zeichen sich dadurch aus, dass sie stabil sind, damit die Objekte beim Sortieren nicht flackern. Das ist wirklich neu.
Und „ordnungsverträglich” müssen die Algorithmen sein. Was mir jetzt einen echten Schrecken eingejagt hat. Habe ich bisher womöglich ordnungsunverträgliche Sortieralgorithmen eingesetzt? Was passiert, wenn ein Algorithmus sortiert, der sich mit Ordnung nicht verträgt? Hört sich irgendwie nach Zufallszahlengenerator an. Eieiei, habe ich jahrelang Zufallszahlengeneratoren als Sortieralgorithmen verwendet und es nicht gemerkt?
Dann kommt ein Abschnitt über das „Konzept des Algorithmus”. Aber nur allgemeines Blabla. Herrlich finde ich auch diesen Satz:
Die Information über die Längen verschiedener konsekutiver Läufe wird in einem Stack verwahrt, was die Implementierung sicherlich recht kompliziert macht.
Oh ja, Sortieralgorithmen sind sicherlich recht kompliziert. Deshalb kamen die bei uns damals im ersten Semester dran. Nur die ganz Harten. Wie gut, dass das endlich mal in einer wissenschaftlichen Publikation erwähnt wird, dass das kompliziert sei, hätte sonst keiner mitbekommen.
Nicht fehlen darf natürlich, wie es gute wissenschaftliche Praxis ist, der Verweis auf die bestehende Literatur und die bestehenden Algorithmen:
Weitere Sortieralgorithmen findet man außer beim Autor auch in der Standardliteratur, z.B. Sedgewick und Knuth, und unter (Sorting algorithms) in Wikipedia.
Ja, das war wichtig. Weil das Fachpublikum bei wissenschaftlichen Arbeiten über Sortieralgorithmen sowas noch nie gesehen hat und erst mal einen Überblick darüber bekommen muss, was das überhaupt so ist und was es gibt. Als bis eben noch stolzer Besitzer solcher Standardwerke muss ich enttäuscht konstatieren, dass da semitransparente Objekte und flackerresistente Algorithmen nicht vorkommen. Was durchaus unterstreicht, wie sehr der Autor dem Stand des Wissens voraus ist.
Ja, und dann hab ich mal abgeschnallt, weil ich heute noch was anderes zu tun habe. Der Algorithmus wird nicht erklärt, sondern es wird einfach ein kaum kommentierter Quelltext als „selbsterklärend” hingeworfen. Selbsterklärend ist da, wenn der Autor von der Prozedur „findRun” redet, und man die erst mal suchen gehen darf, weil sie erst ein paar Seiten später kommt. Und natürlich unkommentiert ist.
Ich habe mir die Berechnungen zum Aufwand gerade nicht näher angesehen, ich habe wie gesagt gerade nicht so viel Zeit. Das dürfen interessierte Leser gerne mal tun. Aber ich halte sie sowieso a priori für falsch, jedenfalls was die Implementierung angeht. Denn die ist lausig. Das Problem ist nämlich, dass Java zwar Referenzen auf Objekte verwalten kann, es aber grundsätzlich von der Wahl der Programmiersprache und unter Umständen der Maschinenarchitektur abhängt, wieviel Aufwand ein Prozeduraufruf und die Übergabe der Parameter-Arrays verursacht. Und das wurde nicht berücksichtigt. Wer gut sortieren will, programmiert nicht in verschachtelten Prozeduren, sondern schreibt das ganze iterativ mit Inplace-Operationen, womit die Darstellung dann auch ziemlich unabhängig von Sprache und Maschine ist.
Ulkig finde ich dann die Angabe, dass die Messung auf einem Mac 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3-Rechner unter Java 6 ausgeführt wurden. Sowas ist mir auch noch nicht untergekommen. Algorithmen, deren Aufwand vom Speichertyp und Hersteller abhängt. Naja.
Fragwürdig sind auch die Graphen zur gemessenen Laufzeit. Sowas misst man normalerweise nicht in Millisekunden, sondern in der Zahl der Operationen. Und eigentlich misst man es auch nicht, sondern berechnet es. Und Größen bis zu 1000 oder 10000 Elemente zu sortieren ist da Killefit. Da wirken sich die Grundgrößen, die man im O-Kalkül eigentlich rausrechnet, noch viel zu stark aus. Wenn da nämlich ein Quicksort, der bekanntlich O(n*log(n)) hat, praktisch linear aussieht, merkt man gleich, dass da was faul ist.
Toll ist auch diese neue Erkenntnis, die die Messung hervorgebracht hat:
Bemerkenswert ist die Erkenntnis, dass invers sortierte Folgen offenbar wesentlich schneller sortiert werden als zufällige Folgen, nämlich mehr als doppelt so schnell. Dieses Phänomen findet sich auch bei anderen höheren Verfahren, die zumindest tendenziell bessere Laufzeiten bei vorsortierten Folgen haben (Quicksort gehört auch dazu!).
Wenn man verstanden hätte, wie Quicksort funktioniert, wüsste man sogar schon vorher, wie dieses sonderbare Phänomen zustandekommt. Stoff Informatik, erstes Semester. Wer das nicht weiß, muss sich bei Messungen über das Phänomen wundern und wird dafür in Deutschland Professor für Informatik.
So richtig von Wissenschaftlichkeit durchtränkt ist auch, wie präzise und wohldefiniert die Erkenntnisse sind:
Der Grund könnte darin liegen, dass beim stabilen Mischen inverser Folgen immer nur noch Listen vorkommen, bei denen die größeren Elemente vollständig in der einen, die kleineren vollständig in der anderen Liste liegen.
„Könnte”.
Ganz herrlich ist auch, dass der Algorithmus eine eigene Wikipedia-Seite hat. Die zur Löschung vorgeschlagen wurde, weil der Algorithmus mit Natural Mergesort übereinstimme. Auch noch ein Plagiat?
Interessante Frage, wer sowas in Wikipedia-Artikel verpackt. Würde mich nicht wundern, wenn das direkt aus der Uni Oldenburg gekommen wäre.
Erweckt bei mir den Eindruck, als ob da jemand anderes irgendwas in Java zusammengeklampft hat und der Autor versucht hat, was pseudoschlaues dazu zu schreiben.
So, die Leser dürfen sich gerne noch dran austoben.
Und immer dran denken: Professoren sind in Deutschland Beamte, unkündbar, freie Arbeitszeit, bekommen dicke Drittmittel, und eine Pension, die weit über der Rente normaler Bürger liegt – und wir zahlen das mit den Steuergeldern.
44 Kommentare (RSS-Feed)
Seit wann hast du denn ein Zählpixel der VG Wort? Fällt mir gerade zum ersten Mal auf.
Algorithmik scheint auch nicht das Fachgebiet des Herren zu sein. Deswegen sollte man da vielleicht nicht zu harsch urteilen. Als Mathematiker, der auch auf diesem Gebiet arbeitet, kann ich nur sagen, dass soetwas natürlich nicht geht. In jeder einführenden Vorlesung über Algorithmik wird der Student mit Korrektheitsbeweis und Laufzeitanalyse in O-Notation vertraut gemacht.
Nicht schlecht. Ich denke, ich warte nochmal zehn Jahre, dann nehme ich den Dr. Inf. mal nebenbei so mit. Nicht weil ich den dringend brauche, aber macht sich dann bestimmt noch gut auf der Visitenkarte. 😉
Hauptproblem wird sein, ein Promotionsthema zu finden, das der Doktorvater noch versteht.
[…] semitransparente Objekte und flackerresistente Algorithmen […]
sind einfach alternativloses Neuland. Haettste ja mal selbst drauf kommen koennen, maskulinistischer Kacker.
🙂
Hmm, vielleicht kommt der ja aus der Computergrafik?
Das würde die Beispiele mit dem Flackern von Objekten bei gleicher Entfernung (z-Fighting) und den transparenten Objekten erklären.
Außerdem wird in der CG auch mehr auf fps statt auf Berechnung der Laufzeitkomplexität in O-Notation Wert gelegt, da der Spaß ja im Besten Falle 60 mal in der Sekunde für eine meist eher geringe Anzahl von Objekten laufen muss.
Meist hat da der konstante Teil den größten Einfluss auf die Laufzeit, wie du schon sagtest.
Wobei mir aber dann wiederum schleierhaft ist, warum er das in Java macht. Und für allgemeine Tiefenberechnungen nimmt man den z-Buffer, das ist alles in Hardware gelöst. Nur das Beispiel mit den transparenten Objekten hat eigentlich Relevanz. Und selbst da ist das ein Sortieren von 3D Objekten im Raum, wo man noch ganz andere Algorithmen braucht.
Ganz abgesehen davon ist das Paper mehr als grausig. Wenn ich in den References nur Wikipediaartikel zitieren würde, würde mich mein Professor feuern, wieder einstellen und dann gleich noch mal feuern.
Stabilität von Sortierverfahren ist tatsächlich bei Anwendungen wie der genannten ein wichtiges Kriterium bei der Auswahl, siehe auch hier (Diskussion): http://stackoverflow.com/questions/12461328/behaviour-of-listt-sort-in-net-4-5-changed-from-net-4-0
@M0ep: Ja, aber dann definiert man , was ma darunter versteht und zeigt, dass der Algo das erfüllt.
ich bin ja nun kein studierter Informatiker, sondern gelernter DV-Kaufmann uns als solcher sozusagen “Handwerker”. Für mich ist die Wahl des Sortieralgorithmus eine rein technische Entscheidung, bei der ich wissen will: welcher Algorithmus hat in welchen Konstellationen welche Vor- und Nachteile, damit ich halt den richtigen auswähle.
Da ist mir dieses ganze Geschwafel völlig egal, sondern wenn da jemand mit nem neuen Algorithmus kommt, will ich wissen, wie er sich in den üblichen Situationen verhält. Und zwar genau! Denn die Entscheidung zwischen zwei Algorithmen kann durchaus mal eng sein.
Habs nur kurz überflogen, erscheint mir aber wie natural mergesort.
Ich hab die Arbeit mal kurz überflogen:
“Abstrakt” schreibt man auch auf deutsch “Abstract”.
“Der Algorithmus ist daher sicher, stabil und ordnungsverträglich” warum hier “daher”? Eine Schlussfolgerung von der Laufzeit O(n * log n) auf diese Eigenschaften ist nicht möglich (Gegenbeispiel HeapSort: hat O(n * log n) ist aber nicht stabil).
“Ordnungsvertäglich” kenne ich nicht, vlt mal eine Definition bringen.
“in der Regel”, “merkbar”, “meistens”, “sicherlich recht kompiliziert” haben in (naturwissenschaftlichen) Arbeiten nichts zu suchen. Immer Messwerte angeben.
So geht es in der Arbeit weiter. Ich erwähne das jetzt nicht mehr.
Wikipedia als Verweis geht nicht. Auch wenn es Standardwerke sind, kann man
richtig zitieren.
Achsenbeschriftung der Abbildungen kann man kaum lesen, die wurden als
komprimiertes Bild eingefügt. Warum? LaTeX kann doch Gnuplot direkt einbinden.
Eckige Klammern braucht man bei Einheiten nicht.
Jede Abbildung erfordert eine Bildunterschrift, die die Abbildung erklärt. Im Idealfall muss man nicht den Text lesen.
@Hadmut: Die Angabe des Rechners, auf dem die Messung durchgeführt werden, ist
in wissenschaftlichen Arbeiten erforderlich. Alle Methoden und verwedenten
Hilfsmittel müssen genau angegeben werden.
“runSort könnte hier wohl effektiv eine Verbesserung im Sinne des Einsparen
von Speicherplatz und Laufzeit ermöglichen.” (S.13) Hmmm, ich dachte Speicherplatz
ist heute nicht soo wichtig…
Moin,
ich hab bei Kowalk “Rechnernetze” und “Algorithmen und Programmierung” gehört, ist schon ein paar Jahre her. Die Qualität der Lehrveranstaltungen war, gelinde gesagt, eine Katastrophe. Uns Studenten war damals schon nicht so richtig klar, wie der Mann es fertig gebracht hat, an eine Professur zu kommen. Wie ich das mitbekommen habe, ist man an der Uni OL auch froh, dass sich der Mann demnächst in den Ruhestand verabschieden wird.
Das ist doch ein Scherz, oder ?
Wann ruft einer “Vorsicht, Kamera !” oder “Helau !” oder so etwas ?
Natürlich ist Sortieren durch Mischen die Wahl, wenn man über hinreichend Speicher verfügt und ein stabiles Verfahren will. Nichts anderes habe ich im Studium in den 80ern gelernt. Insbesondere beim hinzufügen einer geringen Anzahl von neuen Elementen zu einer sortierten Liste, ist es die Methode der Wahl.
Dann stellt er auch noch fest, das feldbasierte Verfahren etwas schneller laufen, als verkettete Listen, wenn man sehr große Datenmengen hat. Da schaue man sich doch einfach mal die Zugriffsmuster an. Letztendlich hat er anscheinend doch nicht genug Speicher und keine Ahnung, wie virtueller Speicher und Caches die Konstanten beeinflussen.
Auch die Hinweise zu den Sortieralgorithmen sind unteres Studenten bzw. Schülerniveau. Auf dem Bild scheint der Mann eigentlich so um die 50 zu sein, also müßte er auch in den 80er studiert haben. Könnte es sich um Demenz handeln ?
Ich vermute eher einen Scherz auf Kosten dessen der so ein Papier veröffentlicht. Möglicherweise hat der einen Schulaufsatz seines Nachwuchses mit Autorentitel und Abstract (Weiß noch jemand, ob es da mal ein deutsche Wort gab ? Oder war es unüblich der Zusammenfassung ein Wort voranzustellen ?) gepimpt und wollte mal sehen, ob das irgendwo reviewed oder gar veröffentlicht wird.
Liest sich für mich als ob der Autor entweder beim verfassen nicht mehr ganz nüchtern war, oder aber wie ein Versuch einen Fachbeitrag in “einfacher Sprache” (layman language) zu verfassen.
Letzteres ist zZ so ein Trend den man z.B. auf einigen Seiten des Bundestags findet. siehe http://www.bundestag.de/leichte_sprache
Da der wehrte Professor sich offenbar ein wenig mit Computergrafik beschäftigt bemüht er ein Problem aus diesem Bereich. Allerdings nach meiner Einschätzung falsch:
Für photorealistische Darstellungen transparenter Objekte benötigt man für Raytracing-verfahren tatsächlich die korrekte Reihenfolge in Blickrichtung des Betrachters. Auf Objektebene liegen die Positionsangaben üblicherweise als Fließkommawerte vor, was üblicherweise ausreicht um eine sichere Entscheidung zu treffen, welches Objekt nun näher am Betrachter liegt und welches weiter entfernt liegt.
Ansonsten wird zur Festlegung der Sichtbarkeit dass von Grafik-APIs wie OpenGL unterstützte Z-Buffer Verfahren verwendet. Dabei wird allerdings nichts sortiert sondern einfach die Z-Werte der Objekte in besagtem Puffer geschrieben. Aufgrund der begrenzten Bit-Auflösung dieses Puffers kann es zum “flackern” kommen.
Mir scheint hier wurden Äpfel mit Birnen vertauscht.
Da Herr Kowalk im Bereich Rechnernetze und Telekommunikation arbeitet wäre es evtl interessant zu wissen wie sonst seine Publikationen aussehen. Dieses “RunSort” Paper wäre mir selbst als studentischer Hoax zu peinlich.
Peter meinte, der Professor kommt vielleicht aus der Computergrafik. Nun, das bestimmt nicht. Er schreibt:
“Neben den üblichen Anwendungen in der Datenverwaltung werden z.B. auch in 3D-Programmen Sortieralgorithmen benötigt, um Objekte
in einer Reihenfolge abhängig von der Entfernung zu zeichnen, z.B. semitransparente Objekte, bei denen hintere Objekte durch vordere ‘durchscheinen’.”
Der Professor meint hier wohl list-priority- bzw. depth-sort-Algorythmen. Bei denen werden Objekte von “hinten” nach “vorne” gezeichnet, um das hidden-surface-Problem zu lösen. Das Problem ist nur: die Algorithmen wurden etwa 1972 entwickelt und kamen nie richtig zur Anwendung, weil sie nicht tragbar waren. Der Professor hat diesbezüglich also keine Ahnung.
Anders sieht es beim Rendern von transparenten Objekten aus. Da werden Objekte in _manchen_ Algorithmen sortiert. Allerdings gibt es da bessere Verfahren (siehe “Computer Graphics: Principle and Practise” 1991; S. 754).
Auch Herr Kowalk lehrt übrigens Sortieralgorithmen in seinen “Algorithmen und Datenstrukturen”-Vorlesungen (ob es jetzt A&D I, sprich erstes Semester, oder A&D II, sprich zweites Semester war, weiß ich nicht mehr genau, ich tippe aber eher auf letzteres), wenigstens war das vor ca. 10 Jahren noch so. Dem Thema widmet er immerhin auch ein Kapitel in seinem Buch “System, Modell, Programm”.
Ansonsten spare ich mir weitere Kommentare, möchte aber darauf hinweisen, dass Herr Kowalk sicherlich nicht stellvertretend für die Oldenburger Informatik steht. Diese Aussage mag man jetzt interpretieren, wie man möchte.
Mit Ordnungsverträglichkeit könnte gemeint sein, daß 2 Elemente, die nach dem Sortierkriterium gleich groß sind, auch in der sortierten Liste ihre Plätze nicht tauschen.
In der Schule läuft das nicht anders. Falls überhaupt programmiert wird, und nicht nur Windows-Anwenderschulung betrieben wird.
Die PISA-Generation erreicht jetzt die Lehrstühle.
@beeblebrox: Kowalk publiziert seit Ewigkeiten so gut wie gar nicht und wenn, dann Beiträge für Informatik-Lexika o. ä., vgl. bspw. DBLP http://www.informatik.uni-trier.de/~ley/pers/hd/k/Kowalk:Wolfgang. Er hat im Übrigen auch kaum Mitarbeiter oder Projekte. Sein Arbeitsschwerpunkt ist sicherlich die Lehre, wobei .S. W sich ja schon dazu geäußert hat.
@claus: Doch, Kowalk beschäftigt sich seit vielen Jahren eigentlich nur noch mit Computergraphik, auch wenn sein Lehrstuhl eine andere Bezeichnung hat.
@marsipulami: Nein, das ist Stabilität. Auf Seite 5 wird für “ordnungsverträglich” der englische Begriff “adaptive” als Synonym angegeben. Aber auch den hätte man definieren müssen …
Wikipedia gibt einen ersten Anhaltspunkt: https://en.wikipedia.org/wiki/Adaptive_sort :
A sorting algorithm falls into the adaptive sort family if it takes advantage of existing order in its input. It benefits from the presortedness in the input sequence – or a limited amount of disorder for various definitions of measures of disorder – and sorts faster. Adaptive sorting is usually performed by modifying existing sorting algorithms.
Das Konzept dürfte soweit klar sein – aber man braucht natürlich eine saubere Definition des Unordnungsmaßes …
Der Wikipedia-Artikel verweist übrigens auf Adaptive aka Natural Merge Sort …
@beeblebrox: “Für photorealistische Darstellungen transparenter Objekte benötigt man für Raytracing-verfahren tatsächlich die korrekte Reihenfolge in Blickrichtung des Betrachters.”
Nicht zwingend. Erstens funktioniert das nur bei nicht-refraktiver Transparenz. Und zweitens: man kann auch zunächst ganz klassisch den dem Beobachter nähesten Hitpoint ermitteln und wenn das Objekt transparent ist, erzeugt man einfach einen weiteren Strahl, der kurz hinter dem Hitpoint beginnt (recursive ray tracing). Diese Variante ist eleganter, weil sie auch mit geringen Modifikationen refraktive Transparenz abhandeln kann.
Allerdings kann die Reihenfolge von Schnittpunkten _eines_ Objekts bei CSG-Operationen (constructive solid geometry) wichtig sein. Da sind Sortieralgorithmen aber nicht sonderlich wichtig, da i.d.R. nur ganz wenige Schnittpunkte vorliegen.
Sorry für die Klugscheißerei. Ich habe aber wenig Gelegenheit, auf dem Gebiet fachzusimpeln.
Allgemein zu Stabilität und Ordnungsverträglichkeit: da gibt es einen Link, der die Begriffe erklärt: http://www.iste.uni-stuttgart.de/fileadmin/user_upload/iste/se/research/publications/Skriptum_HJAx_JL_MEDOC/Skriptum_Informatik/6d.html
Ein Sortieralgorithmus ist stabil, wenn die Reihenfolge von zwei oder mehr Elementen der zu ordnenden Menge durch (nochmaliges) Sortieren nicht verändert wird.
Ordnungsverträglich ist er, wenn er eine bereits (teilweise) Sortierte Menge schneller sortieren kann als eine komplett unsortierte.
@heinz456
Kowalk hat genau einen Mitarbeiter.
Die Veranstaltungen AD1 und AD2 werden abwechselnd von Prof. Kowalk und Prof. Sonnenschein gehalten, wobei die Veranstaltung von Sonnenschein wesentlich besser ist.
Zur AD2-Veranstaltung von Kowalk kann ich sagen, dass zudem die Tutoren der Veranstaltung keine Musterlösungen für die Übungen erhalten, sich quasi selbst mit den teilweise sehr kryptischen Übungsaufgaben auseinander setzen dürfen. Somit waren auch die Tutorien teilweise abenteuerlich, da halt auch die Tutoren keine Ahnung hatten, was Kowalk eigentlich von den Studenten wollte (wahrscheinlich wusste er es selbst nicht).
Ich möchte an dieser Stelle auch betonen, dass Kowalk nicht stellvertretend für die Oldenburger Informatik gesehen werden kann. Er ist wohl eher das schwarze Schaf.
“Ganz herrlich ist auch, dass der Algorithmus eine eigene Wikipedia-Seite hat. Die zur Löschung vorgeschlagen wurde, weil der Algorithmus mit Natural Mergesort übereinstimme. Auch noch ein Plagiat?”
Und eine IP (immerhin aus dem Telekom-Netz, nicht direkt aus dem Netz der Uni Oldenburg …) argumentiert gegen die Löschung.
Noch ein Sortierverfahren von Kowalk…
http://einstein.informatik.uni-oldenburg.de/20908.html
“Quicker than Quicksort – A very fast sorting algorithm -”
http://einstein.informatik.uni-oldenburg.de/forschung/sortieren/DistrSort.pdf
“The algorithm has been tested carefully so that we will assume that it works correctly”
> “The algorithm has been tested carefully so that we will assume that it works correctly”
Geil!
@Info: Informatik ist keine Naturwissenschaft! Wenn man wissen will, wie Aufwendig ein Algorithmus ist (Bedarf an Rechenschritten und Speicher), dann rechnet man das aus oder macht zumindest eine pessimistische Abschätzung, wenn man die Berechnung nicht hinbekommt. Das fällt in den Bereich der Komplexitätstheorie und sollte ALLEN Informatikern an der Uni zumindest in den Grundlagen geläufig sein. Der Test auf einer realen Maschine sagt nicht viel über den Algorithmus, verschafft aber vielleicht eine grobe Kenntnis über ein reales Anwendungsszenario einer realen Implementation, aber da hat Hadmut schon recht, 1000 oder 10000 Elemente Sortieren ist witzlos, da kann man auch Bubblesort nehmen oder irgend so einen Quatsch.
Wohnt Kowalk bei Nürnberg? Dort kommt die IP her, die bei der Wikipedia gegen die Löschung von RunSort argumentiert.
https://de.wikipedia.org/wiki/Wikipedia:Löschkandidaten/4._Oktober_2013#RunSort
Es scheint jedenfalls ein namensgleicher Herr mal bei Philips in Nürnberg gearbeitet zu haben und noch ist vorlesungsfrei:
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=10666
Oh, Schreck !
Jetzt hat er auch noch Radixsort neu erfunden.
Da kommt er bestimmt demnächst auf die Idee bei Zeichenketten die Bereiche nach der unterschiedlichen Auftretenswahrscheinlichkeit von Wortanfängen aufzuteilen.
Ist also anscheinend kein Scherz, sondern eine Methode um Veröffentlichungen zu produzieren. Der sollte sich mal bei mir melden. Ich habe da ein hochgeheimes Verfahren um Zahlen von 0..1023 in O(N) zu sortieren. Ich warte da immer noch auf mein Patent …
@Guy Incognito: Nein, Kowalk wohnt in Oldenburg bzw. Umgebung und hat IMO den akademischen Bereich auch noch nie verlassen. Sollte mich also wundern, wenn er mal bei Siemens gearbeitet hat.
@Knut: Das sind keine Veröffentlichungen, sondern maximal Arbeitspapiere. Wie bereits oben geschrieben veröffentlicht Kowalk praktisch überhaupt nicht.
@Knut
WTF?
Die Zahlen von 0..1023 sortiere ich in O(1) ( == O(1024) )
🙂
“RandomSort: Slower than BubbleSort”
Funktioniert wie folgt: Eine zufällige Anzahl zufälliger Vertauschungen vornehmen, dann prüfen, ob die Folge jetzt sortiert ist.
“We will assume that in most cases the algorithm terminates after a finite number of steps.”
@Alex:
Ja, aber O(1) ist Teilmenge von O(n). Das war wohl der Gag dabei…
@Jens: Den gibt es schon, der heißt BogoSort. PLAGIAT! (SCNR)
@Alex Es geht eher um Datenstrukturen, die nach Schlüsseln 1 bis n zu sortieren sind. Da man diese ja auch in die entsprechende Reihenfolge bringen muss, ist die Komplexität eben nicht O(1) sondern ?(n). Der zugehörige Algorithmus heißt Loopsort.
@tph Bei Knuth hieß das doch noch »Beware of bugs in the above code; I have only proved it correct, not tried it.« (vgl. https://en.wikiquote.org/wiki/Donald_Knuth), oder?
Es ist schon schlimm genug, dass sie überhaupt Java dafür verwenden.
Und dann auch noch von “Geschwindigkeit” reden.
“Wenn ich mir das so überlege, kann man die Literatur über Sortieralgorithmen der letzten 30 Jahre einfach wegwerfen, denn niemand hat darin erklärt, dass Sortieren durchsichtig macht. Warum hat mir das niemand früher gesagt?”
Tja, weil heute halt jeder über Transparenz redet, darf dieser Grundschüler, äääh ach ne, Prof., eben auch mal was dazu sagen…
Auch wenn ich kein Informatiker bin kommt mir bei de zitierten Stellen schon das kotzen. Ist das Paper an Drittklässler gerichtet?
oder von solchen geschrieben worden?
“Und immer dran denken: Professoren sind in Deutschland Beamte, unkündbar, freie Arbeitszeit, bekommen dicke Drittmittel, und eine Pension, die weit über der Rente normaler Bürger liegt – und wir zahlen das mit den Steuergeldern.”
Wir zahlen ja von unseren Stuergeldern auch die ganzen Pfaffen und kirchlichen Lohndrückerinstitutionen. Da kommt’s auf ein paar Uni-Profs auch nicht mehr drauf an.
Die Pfaffen haben allerdings die Lizenz zum Lügen und Schwafeln.
daß die Profs. dem nun gleichziehen wollen grenzt schon an Amtsanmaßung… oder war es Gotteslästerung? 😉
http://www.alibri-buecher.de/Buecher/Kirchenkritik/Carsten-Frerk-Violettbuch-Kirchenfinanzen::348.html
@Peter: “Wobei mir aber dann wiederum schleierhaft ist, warum er das in Java macht.”
Weil das heutzutage eben “jeder” so macht.
Hast Du noch immer nicht mitbekommen,
daß IT ebenso von Modeströmungen abhängt,
wie die eigentliche Modebranche?
Die wichtigsten IT-Koryphäen findet man hier:
http://www.krawattenknoten.info/krawatten/designmode/modedesigner-modeschoepfer.html
😛
“RunSort
Diese Seite wurde gelöscht. Zur Information folgt das Lösch- und Verschiebungs-Logbuch dieser Seite.”
Na endlich …
[…] verfassen zuweilen sehr komische veröffentlichungen, damit sie auch mal wieder etwas veröffentlicht haben. Gut, dass sie mit ihrer professur nicht […]
Was hier dem guten armen Mann alles unterstellt wird. Dabei bemüht er sich doch nur, den neuen Anforderungen an die Lehre gerecht zu werden. Z.B. seine Studenten und andere dem Fach nahestehenden Personen nicht durch allzu große Korrektheit, Formalität und Rigidität im Ausdruck zu überfordern oder verunsichern. Außerdem entspricht der sprachliche Duktus wie
>“in der Regel”, “merkbar”, “meistens”, “sicherlich recht kompiliziert”
dem neuen Paradigma in der Wissenschaft, denn Ausdrücke wie “ist”, “beweisbar” u.ä. transportieren die Vorstellung einer absoluten und unabhängigen Wahrheit, die ohne Dekonstruktion und Diskurs feststellbar wäre. Dabei sind wissenschaftliche Erkenntnisse zunächst nur Hypothesen, die nur durch diskursive Dekonstruktion und Rekonstruktion in einem quoten- und minderheitengerechten Stuhlkreis die höheren Weihen der Wahrheitsfindung erhalten können.
Mit hochachtungsvollen Grüßen
jd.
>>“in der Regel”, “merkbar”, “meistens”, “sicherlich recht kompiliziert”
Ja, das ist ja auch das, was die Feministinnen fordern. Sowas ist dann “frauengerechte” Informatik.
Ansonsten meinen Respekt an alle, die beim Lesen dieses “Papieres” weiter als drei Absätze gekommen sind. Und selbst diese drei Absätze konnte ich nur anreißen und überfliegen.
jd.
Da das Paper nicht mehr auf dem Uni-Server zu finden ist, ebensowenig wie eine Biografie, habe ich mal im Archiv nachgeschaut:
Die haben in Oldenburg hoffentlich gute Deiche, wenn das Niveau da so tief liegt …