Überflüssige Algorithmen (Programmierabfall)

  • :D Zeit :birne: für :s18: ein :freu2: wenig :sieg: Nostalgie :!:

    Für das Sortieren von 500.000 8-Byte-Zufallsintegers in XProfan11.2a brauchte mein 2.5 GHz Rechner (Profan rechnet dabei nur auf einem Kern) mit diesem Algorithmus 186,61 bzw. 185,41 Sekunden. Nostalgie halt... Für solche Arraygrößen bitte die Zeile mit Locate 2,2 auskommentieren, sonst kann man sich während der Zufallsgenerierung einen Kaffee machen gehen.

    Gruss

    P.S.: ... und Alles Gute den Vätern!

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

    • Anzeige

    Hallo!

    Wenn du gerade an deiner Website arbeitest oder dein aktuelles Hosting überdenkst: Wir betreiben mit NetzLiving eine Hosting-Plattform, die speziell auf Performance, Sicherheit und einfache Verwaltung ausgelegt ist.

    • ✔️ Schnelle Ladezeiten (optimiert für WordPress, WoltLab & Co.)
    • ✔️ Deutsche Server & DSGVO-konform
    • ✔️ Persönlicher Support (kein 0815-Ticket-System)

    Mehr erfahren

  • Deshalb ja auch in dieser Rubrik. Die spinnen offenbar, die bei Google!

    Zu oben: Kleiner Fehler ausgebessert: Randomwert auch für das 0-Element (Arrays beginnen bei Null).
    Nun kann man auch Laufzeiten unterschiedlicher Sorts vergleichen, zum Beispiel wenn man 500000 8-Byte-Floatwerte sortiert: 184,31 Sekunden...

    und das gleiche (185,66 Sekunden) für 8-Byte Strings:


    ...also alles erstaunlich konstant!

    P.S.: Zweiten kleinen Fehler entdeckt und in allen 3 Codes behoben...

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Nö, kann man nicht, weil das sehr vom Datenmaterial abhängt. Aber Quicksort ist einer der besten Sorts für Durschschnittsdaten (Anm: In der Split-Phase, wenn die Teilbereichsbreite ca. 12 Einträge unterschreitet, wäre es noch durch Umschalten auf Insert-Sort um ca. 5% zu beschleunigen). Moderne Sortierprogramme bestehen ja aus unterschiedlichen Algorithmen und analysieren regelmäßig ein Datensample, um so den jeweils günstigsten Algorithmus auszuwählen.

    Alles Nostalgie, denn physisches Sortieren ist inzwischen ohnehin Mega-Out. Es wurde abgelöst durch das Mitschreiben von (u.U. mehrfachen) Index-Feldern, z.B. in Form eines in sich verlinkten oder z.B. eines gewogenen Binärbaums (B*-Tree). Selbst dabei gibt es noch immer wieder Verbesserungen, die z.B. auf die Datenträger-Zugriffseigenschaften besonders eingehen. Die Theorie (in Form von Doktorarbeiten) ist dabei viel weiter als die Praxis: Ich habe zufälig mal ein Programm gesehen, das für Harddisks mit 3 bis 6 unabhängigen Zugriffsarmen PRO OBERFLÄCHE optimiert wurde. Wird man im Zeitalter, wo auf vollelektronische Flashdisks umgestiegen wird, vermutlich nie brauchen...

    Gruss

    P.S.: Gutes Link zum Thema SORTS

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Am flottesten ist derzeit BurstSort, eine verbesserte Variante des "American flag sort" (dieser wiederum ist vom Typ BucketSort und für Strings optimiert): Es benötigt nur die Hälfte der Zeit von QuickSort, allerdings auch ein Hilfsarray mit (Platten-)Speicherbedarf in Größe des zu sortierenden Datenfeldes. Davon müssen aber nur die Baumwurzel und einige wenige "Bucket"-Ebenen in einem Cache im RAM gehalten werden. Klingt nicht schlecht... Der Algorithmus ist allerdings für Zeichensätze bis 256 Zeichen optimiert. Quellen-Link hier, Testergebnisse siehe S.8

    Gruss

    P.S. Ich sehe gerade: Stefan Webb, 2007 Wirtschaftsstudent in Österreich, hat dazu damals unter GNU General Public License eine BurstSort C++ Bibliothek auf Sourceforge gestellt. Benutzt Unicode! Reife Leistung, sicher nicht überflüssig - Von hier aus mal herzliche Grüße!

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Und selbst das mit dem Speicherhunger lässt sich noch verbessern:
    Durch Verwendung von Patricia-Trie-Techniken (Trie = reTRIEval-Technik "Practical Algorithm to Retrieve Information Coded in Alphanumeric", kein Schreibfehler in "tree"!) Ohne eingehende Befassung hab ich da erst mal garnix kapiert. Naja...

    Gruss

    P.S.: Spruch in der Werkstätte meines Mechanikers: "Wenn wir es nicht reparieren können, war´s garnicht kaputt!"

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Mitte 2006 wurde die Sortiergeschwindigkeit dann nochmals verdoppelt: CP-Burstsort ist doppelt so schnell wie Burstsort, indem vorhandene CPU-Caches bestmöglich ausgenutzt werden - diesmal unter Beibehaltung von Vorsortierungen in anderen Datenfeldern ("Sortiertreue"). Was jetzt noch fehlt, aber im Grunde recht einfach scheint, ist die Berücksichtigung von Level III-Cache-Eigenschaften der Multi-Core-CPUs. Es scheinen also weitere Verbesserungen möglich - man denke nur an die angekündigten 8-Kern-CPUs...
    Die (englische) Beschreibung von CP-Burstsort findet man hier: http://www.cs.mu.oz.au/~rsinha/papers…gZobel-2006.pdf

    Gruss

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Was für Mausfreunde. Je nach Rechnergeschwindigkeit und CPU-Auslastung klappt das da gut oder eher schlecht:

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Fünftasten-Mäuse werden von obigem Programm richtig erkannt, derzeit können die Seitentasten links und rechts aber leider noch nicht ausgewertet werden, weil ich den korrekten Rückgabewert noch nicht gefunden habe... Beim Mausrad besteht auch noch das alte Leiden, dass der allererste Mausrad-Zahn u.U. falsch als "Rad hinauf" erkannt wird.

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Danke, wird getestet. Zur Ehrenrettung: Rechte (1) und Linke Maustaste (2), Trackball selbst ist vermutlich klickbar (3) und hat die üblichen Mausradrichtungen VOR und ZURÜCK, aber daneben eben noch die Sonder-Richtungen LINKS (4) und RECHTS (5). 5 ist bei "geeigneter" Zählweise also richtig ;)

    P.S.: Mund zu voll genommen: Bitte welche Include definiert mir WM_XButtonDown/Up?
    Und muss ich die Abfrage erst registrieren?

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Die Windows-Welt wird immer komplizierter. Ob sie dadurch wirklich sicherer wird?

    Sicherheitsstufe von ausführbaren Programmen
    ==============================
    Seit Windows Vista und Win7 haben Programme niedriger Sicherheitsstufe (z.B. aus dem Internet geladene Nicht-Microsoftzertifizierte Programme, Internet Explorer AddOns etc.) eigene Datei- und Registry-Pfade, damit auch sie in den neueren Systemen noch Schreibzugriff haben und (sicherheits-gemanaged) ablaufen können.

    Registry:
    Prozesse mit geringer Sicherhit haben Schreibzugriff/können Subkeys anlegen unter
    HKEY_CURRENT_USER\Software\AppDataLow

    Dateien:
    Prozesse/Programme geringer Sicherheitsstufe haben Schreibzugriff auf
    %USER PROFILE%\AppData\LocalLow


    Und was ist mit "AppData\Local" ?
    Hier werden Programme und Dateien gespeichert, die stets auf diesem Computer verbleiben sollen (Wenn eine bestimmte Aufgabe stets auf diesem speziellen PC laufen soll), - oder Programme und Dateien die zu groß sind, um sie im Falle des Umzugs eines Users jedesmal automatisch neu auf den anderen Computer im Netzwerk zu übertragen, auf dem der User neuerdings arbeitet (Das gäbe eine zu hohe Netzbelastung). Automatische Übertragungen finden z.B. bei den Desktop-Einstellungen eines bestimmten Users statt, der sich auf einem anderen PC einlogged. Das geht normalerweise so schnell, daß die meisten User es gar nicht bemerken.

    Anders dagegen Programme, Links usw. im Verzeichnis "AppData\Roaming":
    Roaming (engl. "umherstreunen") bedeutet, daß die Programme von einem anderen Netzwerkstandort abgefragt bzw. die Inhalte an diesen übertragen werden können.

    Übersetzt aus Internet-Quellen, u.a. diese.

    Achtung: Neuere Windows-Systeme gaukeln älteren Programmen die für diese altbekannten XP- oder Win98-Pfade vor, schicken und holen Daten aber eiskalt in/von oben beschriebene/n Verzeichnisse/n. Die genauen Regeln, wann das geschieht und wann nicht, sind oft selbst Insidern ein Rätsel...

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!