Sortieren ist schwierig!



  • Interessiert vielleicht den ein oder anderen, dass sichrp rausgestellt hat, dass weit verbreitete Implementationen eines Sortieralgos falsch sind... Nämlich die von Java, Android und Python.

    http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/

    Interessant ist auch wie es rausgefunden wurde -- nämlich indem versucht wurde die Korrektheit der Implementierung nachzuweisen.



  • Korrektheit für <2^49 Elemente ist für mich ausreichend. Dafür will ich nicht noch einen unnötigen Check drin haben, der alles langsam macht.



  • pragmatiker schrieb:

    Korrektheit für <2^49 Elemente ist für mich ausreichend. Dafür will ich nicht noch einen unnötigen Check drin haben, der alles langsam macht.

    Genau, 640K Speicher reichen ja auch und bis 2000 ist die Software eh nicht mehr in Betrieb... Und natürlich reicht ne 16bit variable für die steuerung unseres Raketenantriebs. 😉

    Wobei due Java-Implementierung wohl ggf. Früher das Handtuch schmeisst, wenn ich das richtig gesehen hab.

    Edit: der fix wirkt sich nur einmal pro merge run aus und dürfte damit insgesamt bei der Laufzeit nicht ins Gewicht fallen. Es ist also quasi umsonst das ganze zu fixen. Bei python us das wohl sogar schon erledigt.



  • Sehr interessant, danke! 👍

    Bloch 2006 kannte ich schon, aber der neue Artikel ist wirklich gut.



  • Jester schrieb:

    pragmatiker schrieb:

    Korrektheit für <2^49 Elemente ist für mich ausreichend. Dafür will ich nicht noch einen unnötigen Check drin haben, der alles langsam macht.

    Genau, 640K Speicher reichen ja auch und bis 2000 ist die Software eh nicht mehr in Betrieb... Und natürlich reicht ne 16bit variable für die steuerung unseres Raketenantriebs. 😉

    Wie lange würde der Algorithmus laufen, um 2^49 Elemente zu sortieren (du darfst für die Berechnung sogar so tun, also ob es schon so großen Arbeitsspeicher gäbe)?


  • Mod

    AManOnTheMoon schrieb:

    Jester schrieb:

    pragmatiker schrieb:

    Korrektheit für <2^49 Elemente ist für mich ausreichend. Dafür will ich nicht noch einen unnötigen Check drin haben, der alles langsam macht.

    Genau, 640K Speicher reichen ja auch und bis 2000 ist die Software eh nicht mehr in Betrieb... Und natürlich reicht ne 16bit variable für die steuerung unseres Raketenantriebs. 😉

    Wie lange würde der Algorithmus laufen, um 2^49 Elemente zu sortieren (du darfst für die Berechnung sogar so tun, also ob es schon so großen Arbeitsspeicher gäbe)?

    Auf einem Petaflopsupercomputer? Sekunden bis zu ein paar Minuten oder Stunden. Je nachdem, wie flott du den Speicher anbindest, bzw. wie schnell die Kommunikation zwischen weit entfernten Knoten abläuft. Jedenfalls locker machbar kurz. 2^49 Elemente ist, von der reinen Rechenleistung her, für einen Computer schon lange keine eindrucksvolle Zahl mehr. Beschränkung ist hier eben eher die genannte Kommunikation und der Speicher, weil die meisten Supercomputer heutzutage eher auf Rechenleistung als auf große Datenmengen optimiert sind.

    Und was vor 45 Jahren noch als Supercomputer galt, ist heute in einer besseren Armbanduhr drin.



  • SeppJ schrieb:

    Auf einem Petaflopsupercomputer? Sekunden bis zu ein paar Minuten oder Stunden. Je nachdem, wie flott du den Speicher anbindest, bzw. wie schnell die Kommunikation zwischen weit entfernten Knoten abläuft. Jedenfalls locker machbar kurz. 2^49 Elemente ist, von der reinen Rechenleistung her, für einen Computer schon lange keine eindrucksvolle Zahl mehr. Beschränkung ist hier eben eher die genannte Kommunikation und der Speicher, weil die meisten Supercomputer heutzutage eher auf Rechenleistung als auf große Datenmengen optimiert sind.

    Und was vor 45 Jahren noch als Supercomputer galt, ist heute in einer besseren Armbanduhr drin.

    Das hört sich ja fast so an, als ob der Bug momentan schon irgendwie ein Problem darstellt. So ist es definitiv nicht, nicht mal auf dem genannten Tianhe-2 Supercomputer. Und auf dem Rechner zu Hause hat man vielleicht 2^33 Byte Arbeitsspeicher.

    Was den Zeitbedarf betrifft, kann man ja mal auf einem einfachen Rechner ein paar Messungen machen und dann extrapolieren. Ich glaube, man kommt da auf wesentlich mehr Zeitbedarf als erwartet, auch wenn O(n*log(n)) sehr effizient ist. Auf einem Supercomputer macht es einen erheblichen Unterschied, ob man Sekunden oder Stunden für so etwas benötigt. Supercomputer nutzt man typischerweise durch ein Queueing-System, bei dem man eine bestimmte Menge an Rechenknoten beantragt und die dann für eine gewisse Zeit zur Verfügung hat. Die wenigsten Rechnungen auf einem Supercomputer haben die ganze Maschine zur Verfügung und wenn so ein Job den ganzen Supercomputer kriegt, dann nur für relativ kurze Zeit. Dort sind recht kurze Walltimes üblich. Vermutlich maximal einen halben Tag oder so.


  • Mod

    Mein Punkt war nicht die die Arbeitsrealität heutiger Supercomputer, sondern dass 2^49 schon mit heutiger Technik keine unvorstellbar große Zahl mehr ist und man durchaus den Fall in Betracht ziehen sollte, dass solche Datenmengen in absehbarer Zukunft verarbeitet werden könnten.



  • @Gregor
    Klar ist der Bug schon heute ein Problem.
    Die Jungs haben ja sogar ein Programm geschrieben das in Java wunderschön crasht (IndexOutOfRangeException) wegen dieses Bugs.

    Die 2^49 beziehen sich bloss auf die Implementierung von Python.



  • hustbaer schrieb:

    @Gregor
    Klar ist der Bug schon heute ein Problem.

    The bug was not deemed critical because no current machine could hold a sufficient number of elements, approximately 2^49 or 562 trillion ...

    http://en.wikipedia.org/wiki/Timsort#Debugging_with_Formal_Methods



  • Z schrieb:

    hustbaer schrieb:

    @Gregor
    Klar ist der Bug schon heute ein Problem.

    The bug was not deemed critical because no current machine could hold a sufficient number of elements, approximately 249 or 562 trillion ...

    http://en.wikipedia.org/wiki/Timsort#Debugging_with_Formal_Methods

    The bug was patched in Python a day later

    Es war ein unkritscher Problem, sonst würde er wohl nicht so fix gepatched - naja bei der Vorarbeit...



  • Z schrieb:

    hustbaer schrieb:

    @Gregor
    Klar ist der Bug schon heute ein Problem.

    The bug was not deemed critical because no current machine could hold a sufficient number of elements, approximately 2^49 or 562 trillion ...

    http://en.wikipedia.org/wiki/Timsort#Debugging_with_Formal_Methods

    Schau nochmal schnell nach ob Du vielleicht was aus dem Kontext gerissen hast und Deine Antwort deswegen vielleicht nicht passt.



  • Für alle die meinen sie seien so schlau: bitte doch einfach den Artikel den Jester verlinkt hat lesen bevor ihr antwortet.



  • SeppJ schrieb:

    AManOnTheMoon schrieb:

    Jester schrieb:

    pragmatiker schrieb:

    Korrektheit für <2^49 Elemente ist für mich ausreichend. Dafür will ich nicht noch einen unnötigen Check drin haben, der alles langsam macht.

    Genau, 640K Speicher reichen ja auch und bis 2000 ist die Software eh nicht mehr in Betrieb... Und natürlich reicht ne 16bit variable für die steuerung unseres Raketenantriebs. 😉

    Wie lange würde der Algorithmus laufen, um 2^49 Elemente zu sortieren (du darfst für die Berechnung sogar so tun, also ob es schon so großen Arbeitsspeicher gäbe)?

    Auf einem Petaflopsupercomputer?

    Parallelisier der Algorithmus und verteilt alles auf mehrere Kerne?


Log in to reply