Mir ist aufgefallen dass die Implementierung von Algorithmen in verschiedene
\nKategorien passen. Es geht also nicht um das, was der Algorithmus macht, sondenr
\nwie er programmiert ist. Die Kategorien sind auch meist Sprach uebergreifend.<\/p>\n
Beispiel: segmentTools vertex-collapse<\/p>\n
In der derzeitigen Version faellt der Algorithmus in die Kategorie
\n\"korret, aber nicht vollstaendig\".
\nDas bedeutet, das Programm bearbeitet die Probleme richtig, aber nicht fuer alle
\nFaelle. Es fehlen also einige Sonderfallbehandlungen.<\/p>\n
Die Kategorie \"Datenabhaenigkeit\" ist sehr komplex und oft untergliedert. Fuer den vertex-collaps
\nAlgorithmus gilt, dass ein Segment mit mehreren anderen Segmenten zusammen fallen kann. Also
\neine 1-n Beziehung. Momentan wird immernur eine 1-1 Beziehung bearbeitet.
\nDaher ist die derzeitige Version auch in der Kategorie \"nicht vollstaenig\". (Gluecklicherweise
\nkann durch wiederholte Aufrufe des Programms das Problem umgangen werden).<\/p>\n
Auch trifft die Kategorie \"langsam - quadratisch Laufzeit\" zu. Das bedeutet einfach,
\ndass die Berechnung statt Sekunden (mehrere) Tage dauert.
\nDementsprechend gibt es noch die Kategorie \"schnell - linear logarithmische Laufzeit\".<\/p>\n
Um nun den Algorithmen in die Kategorie \"schnell\" zu heben, gibt es einige schon ausgearbeitet
\nTechniken. Darum den Sweepline Algorithmus. Dieser steuert, auf einer intelligentere Art und Weise,
\nwelche Segmente der vertex-collapse Algo in welcher Reihenfolge bearbeiten wird. Der Sweepline Algorithmen
\nbedient sich eines weiteren Algorithmus zum Sortieren von Daten. <\/p>\n
Der vertex-collapse Algorithmus faellt also in weitere Kategorien.
\nEinmal \"Datenabhaenigkeit - Reihenfolge\". Dadurch entstehen weitere Sonderfaelle welche die 1-n Beziehnung noch
\nverkomplizieren.<\/p>\n
Und es gibt zusaetzliche die Kategoie \"Daten Redundanzen\/Kopien\".
\nHier gibt es zwei aehnliche Faelle.<\/p>\n
Fall 1:
\nUm nicht den orignal Datensatz zu veraendern, macht man in der Regel eine Kopie davon und sortiert ihn dann
\nmit Sweepline. Das funktioniert bei gro\u00dfen Datensatzen nicht mehr, da hier der RAM oft zu klein ist. (Der
\nErgebnisdatensatz sollte auch noch in den RAM passen).<\/p>\n
Eine g\u00e4ngige Methode um das zu umgehen ist, statt das eigentliche Datenobjekt zu sortieren (das Segment)
\nwerden nur die IDs sortiert. Aber nicht die ID als Nummer, sondern der (speziell hierfuer angepasster) Sortier Algoritmus greift beim
\nsortieren ueber die ID auf das Segmente Objekt zurueck und erstellt dementsprechend eine Sortierung der IDs.<\/p>\n
Das hat Vorteile und auch viele Nachteile.<\/p>\n
Vorteile:
\n* Der Speicherverbrauch sink. Nehmen wir z.B. ein Segment mit zwei 3D Punkten und doppelter Zahlengenauigkeit.
\n 2*3*8byte = 48byte pro Segment. Werden stattdessen nur IDs kopiert und sortiert, fallen nur 4byte pro Segment
\n zusaetzlich an.
\n* Die Geschwindigkeit steigt. Im jeder Sortieriteration werden Daten bewegt. Statt 48byte muessen nur 4byte im Ram
\n bewegt werden.<\/p>\n
Nachteile:
\n* Nicht jeder Datencontainer kann ueber eine integer ID effizient angesprochen werden. Das funktioniert nur effizent
\n bei Vector Containern. Deque, Hash und Sorted Maps sind auch noch moeglich. Bei Listen funktioniert es nicht mehr.<\/p>\n
* Nicht jeder Datencontainer kann ueberhaupt ueber eine integer ID angesprochen werden. Oft werden auch andere Typen
\n als ID benutzt. Zum Beispiel kurze Strings. Ein Mapping String ID -> Integer ID ist zwar moeglich, kostet aber wieder
\n Speicherplat und Geschwindigkeit.<\/p>\n
* Die ID Variable enthaelt keine Informationen ueber den Datentype auf den sie verweist. Arbeitet man mit mehreren Datensaetze
\n z.B. Segmente und Punkte, so ist es moeglich mit einer Segment ID Variable auf den Punkt Datensatz zuzugreifen ohne
\n dass dieser Programmierfehler sofort bemerkt wird.<\/p>\n
Fall 2:
\nDer zweite Fall bezieht sich auf Daten die der Sweepline Algoritmus zwischenspeichert. Auch hier muss wie beim Sortieren
\nauf die Datenobjekte zugegriffen werden und es entstehen die selben Vor und Nachteile.<\/p>\n
Weiterhin muss auch der Sortier Algorithmus darauf hin ausgelegt sein, nicht die eigentlichen Daten zu sortieren, sondern ihre
\nIDs.
\nDies fuehrt zu dem Problem, dass der Programmierer des Sort und auch Sweeplines mit einem unbekannten, benutzer definierten,
\nDatentype arbeiten muss.
\nDies wurde in C und Fortran dadurch geloest, dass der Benutzer definierte Datentype nur als Pointer von Type void (also
\nkeine Type Information), oder noch schlimmer: als Typ double, der Sortier Routine uebergeben wurde. Der Algorithmus arbeitet
\nalso blind aus den Daten und es liegt in der Hoffnung des Programmiers, dass es auch immer funktioniert.<\/p>\n
Noch dazu gibt es von C std lib keine Sortierfunktion die zusaetzlich auch IDs beruecksichtigt. Die Routine muss also immer
\nneu geschrieben werden mit allen Fehlern und Sonderfaelle. Insbesondere bei Fortran. Da es hier nicht mal eine Sortierfunktion
\nvon der Standardlib selbst gibt.<\/p>\n
Das Problem mit den benutzer definierten Datentypen wurde mit der Einfuehrung von C++ im Jahre 1984, und die integierte Template
\nSprache, geloest.
\nEs koennen nun abstrakt geschrieben werden und zur Compilierzeit wird der benutzer definierten Datentype eingebaut und entsprechende
\nFehler vom Compiler weise auf Probleme hin.<\/p>\n
Um die Probleme mit den IDs anzugehen kann man als erstes Versuchen satt einer Integer ID, einen Pointer auf das Datenobjeckt zu speichern
\nund zu sortieren. <\/p>\n
Vorteile:
\n* Es funktionieren nun alle Containertypen.
\n* Kein Problem mehr mit string IDs, da auf das Datenobjekt selbst zugegriffen wird.
\n* Keine extra Mapping sortierte ID -> container -> Datenobjekt mehr noetig
\n* Weiterhin Platzersparnig als wenn eine Kopie des Objekt sortiert wird<\/p>\n
Nachteile:
\n* Pointer verbrauchen auf 64bit Systemen 8byte, also doppelt so viel wie integer IDs
\n* Pointer koennen invalid sein. Immer ein Check noetig.
\n* Pointer muessen immer explizit dereferenziert werden um an das Objekt zu gelanden auf das sie zeigen.<\/p>\n
Weiterhin muss der Sortierfunktion eine Funktion uebergeben werden, die besagt, wie zwei Pointer Objeckte auf kleiner \"<\" verglichen werden konnen.\nDas ist aber schon immer in C und C++ moeglich. Nur eine Frage der kryptischen Syntax.\n\n\nUm auch die Nachteile der Pointer zu kompensieren, k\u00f6nnen Referenzen genutzt werden. \n\nVorteil: \n* Referenzen sind immer valid.\n* Refreenzen muessen nicht extrea dereferenziert werden.\n\nNachteil:\n* Referenzen brauchen wie Pointer 8byte.\n\nSeit C++ 2011 ist es moeglich auch Referenzen in einem Container zu speichern. Weiterhin gibt es mit Lambdas eine elegante Moeglichkeit\ndie relations Funktion zweite Datenobjekte zu formulieren. Kein kryptischer Code mehr.\n\nSomit bietet C++ seit 2011 die fehlerfreiste und performanteste Moeglichkeit einen Algorithmus schneller durch Sortierung zu machen.\n\nViele Worte, wenig Code. So siehts aus:\n\n\n\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Mir ist aufgefallen dass die Implementierung von Algorithmen in verschiedene Kategorien passen. Es geht also nicht um das, was der Algorithmus macht, sondenr wie er programmiert ist. Die Kategorien sind auch meist Sprach uebergreifend. Beispiel: segmentTools vertex-collapse In der derzeitigen Version faellt der Algorithmus in die Kategorie \"korret, aber nicht vollstaendig\". Das bedeutet, das Programm […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17],"class_list":["post-2575","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/2575","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2575"}],"version-history":[{"count":1,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/2575\/revisions"}],"predecessor-version":[{"id":2576,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/2575\/revisions\/2576"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2575"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2575"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}