Sonntag, 5. Februar 2017
Mathematische Regressionsanalyse und Hierarisches Clustering in der Ökonomie/Wirtschaft
Hierarchical-Clustering und seine Schwächen
Sehr geehrte Damen und Herren,
das was man lernt in seinem Studium, dass was man gesagt bekommt, ergibt sich erst später und wird einem erst klar, nachdem man es "setzen" hat lassen.
So ist es zum Beispiel mit der Vorlesung der "Ökonometrie".
Auch in der Gefahr, dass es nicht ganz richtig ist, was den Stoff der Ökonometrie angeht, schreibe ich meine Gedanken auf.
Es gibt zwei Verfahren in der Ökonometrie, die gerne in Kombination verwendet werden: Das Hierarchical-Clustering und die Regressionsanalyse.
Das Hierarchical-Clustering wird zur Bestimmung von Gruppen verwendet und deren Beziehung dann in der Regressionsanalyse berechnet.
Da die Regressionsanalyse schon sehr ausgeschöpft ist und da der Kern der Frage in der Bestimmung der Gruppen liegt, wird hier auf das Clustering wert gelegt.
Hierarchical-Clustering sucht immer die am Nächsten liegenden Punkte oder Mittelwerte einer Gruppe und verbindet die beiden Punkte zu einer neuen Gruppe. Das Ergebnis sieht wie folgt aus:
Nach Wikipedia gibt es zwei Verfahren:
- divisiv - bzw "Top-down"
- und agglomerativ - bzw "Bottom-up"
Pattern-Recognition anhand von Hierarchical-Clustering mit Hilfe des Cut-Off-Criterium
Leider sind nach Wikipedia die Verfahren Top-Down und Bottom-Up in ihrer Komplexität unterschiedlich.
Top-Down brauch naiv
Schritte.Bottom-Up hingegen nur
Schritte.Natürlich geht der Vorteil mit Verlust von Information/Unterscheidungsmöglichkeiten einher.
Doch dies ist hier nur prognostiziert.
Da ein Hierarchical-Clustering mit dem Hierarchie-Diagramm wie in Abbildung 1 nicht viel hilfreich ist, wird der Abstand zwischen den Clustern beim Vereinigungspunkt auf der Y-Achse abgebildet. Dies ist dann ein "Dendogramm", welches auch gedreht dargestellt werden kann. Ein Beispiel ist in Abb.2 gezeigt.
Abb. 2 - Beispiel für ein typisches Dendrogramm [1]
Hier wird dann das Cut-Off-Criterium angewendet, welches dazu dient die Cluster zu bestimmen.
Dazu gibt es unterschiedliche Verfahren, welche in: Pattern-Recognition anhand von Hierarchical-Clustering mit Hilfe des Cut-Off-Criterium vertieft werden können.
Manchmal reicht ein einzelnes Cut-Off-Criterum nicht aus, weil dann nur eine kleine Menge und eine ganz große Menge entsteht, welche oft nicht der Realität entsprechen. Daher wird gerne ein zweiter Schnitt gemacht, welcher dann nur auf die Große Menge bezogen wird und diese weiter unterteilt. Siehe dazu Abbildung 3. Durch Wiederholung dieses Verfahrens bis auf vorgegebene Größen von Mengen, ist dieses Verfahren sicherlich sinnvoll. Leider sind jedoch dadurch keine großen Mengen mehr erkennbar/unterscheidbar. Im Allgemeinen geht der Vorteil des Clusterns damit verloren. Denn, jede Menge lässt sich natürlich in andere Mengen unterteilen. Und am Ende sind die Mengen immer nur von zwei Elementen Abhängig.
Abb. 3 - Zwei cut-off Kriterien [3]
Trotz dem mehrfachen Unterteilen, liegt das Problem, weshalb Hierarchical-Clustering nicht vollständig als perfektes Verfahren etabliert ist, auch in der Möglichkeit, dass das Clustering "entartet". Man kann sagen: Die Frage der Entartung ist analog zur Frage wo geschnitten werden kann.
Genauso, wie es unter Binärbäumen entartete Bäume gibt, gibt es beim Hierarchical-Clustering auch entartete Hierarchien. Siehe dazu Abbildung 4.
Dies wird ebenfalls im Wikipeida Artikel[1] beschrieben, und dort als "single-link effect" (dt. Ketteneffekt) bezeichnet.
Es wird versucht mit verschiedenen Verfahren beim Alignment/Linkage das Probelm des single-link effects zu verhindern. Dabei wird zwischen drei Knoten im Hierarchical-Tree unterschieden. Der einzufügende/aligning Knoten (g_a) und die beiden letzten Knoten der aktuell betrachteten Menge (g_b).
Abb. 5 - "Daten und Dendrogramm mit der Centroid-Methode." [1]
Wie in Wikipedia[1] beschrieben, gibt es unterschiedlichste Verfahren zur Verhinderung von single-link effect.
Aktuell sind jedoch nur empfehlenswert, das Average-Linkage und das Centroid-Linkage Verfahren. Das liegt an der Betrachtungsweise. Für die Anwendungen in der Betriebswirtschaft ist es notwendig den natürlichen Gegebenheiten der Welt und dem natürlichem Verhalten von Menschen ähnlich zu sein. Dafür bietet sich das Centroid-Linkage und das Average-Linkage am besten an. Näheres über die Verfahren in [1]. Die beiden Verfahren Centroid und Average sind auch in erster Linie die Wahl, da andere Verfahren wie Median-Berechnung nur sinnvoll sind, wenn die Mittelwert-Berechnung an Aussagekraft verliert.
Der Grund hinter dem Linkage-Verfahren mit drei Gruppen/Mengen liegt, wie schon erwähnt, in der Lösung des single-link effect.
Um die Idee näher zu verstehen, ist es dienlich das Problem kurz zu umschreiben.
Problem der Entartung von Bäumen
Eine Entartung entsteht, wenn eine der zu vereinigenden Gruppen g_a oder g_b eine Stufe zuvor auch schon vereinigt wurden.Um das zu erklären, ist es praktisch kurz die Eigenschaften eines entarteten Baumes zu beschreiben:
- das zuletzt hinzugefügte Element zu einer Gruppe,
ist auch wieder Element der nächsten Gruppe, - der Baum hat genauso viele Ebenen, wie Elemente (n).
Bei einem ausgeglichen Baum gibt es hingegen nur log(n) Ebenen für n Elemente.
Daraus folgt:
Wenn k = | i - j |, mit |.| = Absolutwert der Ebenen-Nummer i für g_a und j für g_b, dann ergibt sich folgende Regel:
Ist |i-j| < log(n)/2, so führt diese Verbindung zur Entartung.
Nun kann man diese Verbindung auslasse und die nächst beste Gruppe nach dem Linkage-Verfahren betrachten.
Deshalb wird gerne das Linkage-Verfahren variiert um den single-link effect zu vermeiden.
Doch leider hat das Problem der entarteten Bäume wenig mit dem Linkage-Verfahren zu tun. Das Linkage-Verfahren dient nur der Frage, wie die Elemente ausgewählt werden um miteinander verbunden zu werden. Naturgemäß ist da das Kriterium des nähesten oder mittlersten Elementes, innerhalb zwei Gruppen A und B, am passendsten. Beispielsweise gäbe es noch das Verfahren des weitesten entfernten Elementes aus zwei Gruppen als Linkage (Complete-Linkage) zu betrachten, nur wird dies dem natürlichem Verhalten von Personen und Optionen kaum gerecht.
Die Entartung der Bäume liegt demnach nicht an dem Linkage-Verfahren.
Eine naive Lösung wäre nicht das Linkage-Verfahren zu variieren, sondern wie folgt.
Naive Lösung
- Wenn |i(g_a) - i(g_b)| < log(n)/2 * 0,8 = log(n) 2/5,
wobei i(g_a) die Ebenen-Nummer bei Vereinigung von Gruppe A ist und 0,8 o.B.d.A ein Wert, der für signifikant kleiner steht, ist,
dann wähle die nächste, dem Linkage-Verfahren passende Gruppe g_c, welche zu g_a aligned würde. - ist dann |i(g_a) - i(g-c)| >= 2/5 log(n), höre auf und verbinde g_a mit g_c.
- ist |i(g_a) - i(g_c)| < 2/5 log(n), dann wiederhole Schritt 1,
- bis keine alternative Gruppe gefunden wurde. So wähle g_b.
Diese Lösung ähnelt in etwa einem AVL-Baum[6]. Der Baum wird ausgeglichen um die "Entartung" zu vermeiden. Der Trick des AVL-Baumes besteht darin, den rechts oder links-lastigen Zweig höher zu stellen, indem ein anderer Root-Knoten gewählt wird. Dabei spricht man von Links-, Rechts- oder Doppelrotation.
Abb. 6 zeigt eine Linksrotation um den rechten schwereren Zweig auszugleichen.
Problem der Naiven Lösung
Leider ist das Problem der Naiven Lösung ganz offensichtlich: Die Mengen A wird mit einer anderen Menge C anstelle der von B verknüpft. Die Menge C ist jedoch von der Lokalisation weiter entfernt als B, und entspricht daher nicht dem Ähnlichkeitsprinzip. Geht es bei der Erstellung des AVL-Baumes nur um eine korrekte Sortierung der Elemente nach > oder <=, so ist ein AVL-Baum ausreichend. Hier im ökonomischen Zweig, geht es jedoch um Erkennung von Gruppen und diese sind nach Rotation, oder Wahl von C anstelle von B, zerstört.Elegante Lösung
Ist der Datensatz mehr als eindimensional, also ein Vektor, so ist generell eine hierarchische Aufteilung nicht möglich. Die Datensätze besitzen nun eine Position in einem mehrdimensionalen Raum. Sie besitzen eine Lokalisation. D.h. die Datensätze haben mehrere Abstände zu ihren nächsten Nachbarn auf unterschiedlichen Achsen.
Eine Vereinfachung auf den am nahestehend Datensatz/Gruppe/Knotenpunkt ist somit eine Reduktion der anderen Abstände auf den anderen Achsen.
Durch dies Reduktion geht Information verloren, und das Ergebnis entspricht nicht dem gewünschtem Ergebnis.
Im Prinzip ist das Hierarchical-Clustering auf mehrdimensionale Daten ungenügend. Aktuell erstellt es eine Hierarchie, die so nicht die Gruppen der mehrdimensionalen Daten abbildet.
Vielleicht wäre eine Lösung durch einen vollständigen Travelling-Salesman-Path möglich.
Das Travelling-Salesman-Problem ist die Frage nach dem kürzesten Round-Trip, wenn alle Punkte/Städte auf mindestens Intervallskala, miteinander auf direktem Wege erreichbar sind.
Die Lösung wäre:
- Das TSP auf den Daten X zu lösen
- Bei der größten Teilstrecke in eine Richtung zu starten
- Alle Punkte als eine gemeinsame Menge zu sehen, welche mit den TSP-Streckenabschnitten s verbunden sind, die kürzer als der durchschnittlichen Streckenabschnittslänge µ, abzüglich des Fehlers e, sind.
s < (µ - e) ==> verbinden des vorherigen und nächsten Punktes.
Wie das TSP lösbar ist, wird in einem anderen Blog-Beitrag besprochen.
Siehe tspsolved.blogspot.de .
Als Fehler e verwenden wir das a-Quantil mit alpha=0,04. D.h. bei z_(1-a/2) = 0,5160 für Normalverteilung, ist der Fehler:
[7]Leider ist das TSP auf naive Variante noch O(n!). D.h. zu langsam. Mit der Lösung des TSP wie unter tspsolved.blogspot.de, kommt es zur Veränderung in der Komplexität und einem großen Einfluss auf die Welt.
So kann das TSP einen Beitrag für die Öknometrie leisten.
mit freundlichen Grüßen, hochachtungsvoll, Ihr Sebastian
References
[1] https://de.wikipedia.org/wiki/Hierarchische_Clusteranalyse[2] http://sebastianboehmercomputing.blogspot.de/2009/12/pattern-recognition-anhand-von.html
[3] http://compbio.pbworks.com/f/partitonal.JPG
[4] http://www.saedsayad.com/images/Clustering_h1.png
[5] http://www2.cs.uregina.ca/~dbd/cs831/notes/clustering/Hiereg.gif
[6] https://de.wikipedia.org/wiki/AVL-Baum
[7] https://de.wikipedia.org/wiki/Konfidenzintervall
Donnerstag, 19. Januar 2017
Programmkonstrukt - Grundlagen für eine Programmiersprache
Sehr geehrte Damen und Herren,
folgender Text ist unausgereift und hier nur als Skizze zu sehen.
eigentlich ist es ja so: Mit jeder neuen Technologie stellt sich die Frage, ob man diese brauch. Auch ist es immer wieder fraglich, ob es vorteilhafter wird, ob es einfacher wird, oder nur komplexer. Es stellt sich die Frage, ob die Technologie eine gute Idee war.
Prinzipiell ist jede Technologie gut. Jedoch gibt es auch die Möglichkeit eine unnötige Technologie zu besitzen oder Zeit in diese zu investieren. Man stelle sich vor, man hätte eine Waschmaschine, in die man nur ein Teil jeweils rein machen kann, die trotzdem eine Stunde pro Teil brauch. Oder ein stylischen Tretroller (Scooter), der ganze 10 kg wiegt.
Und im Prinzip verhält es sich mit der Programmierung gleich. Es gibt komplizierte Programmierkonstrukte, die mehr Chaos als Ordnung in die Programmierung bringen. Es sieht so aus, als ob nicht jedes Programmierkonstrukt geeignet ist. Es sieht so aus, als ob es ein optimale Technik geben könnte. Ich weiß, dass manche ja behaupten, jede Programmiersprache habe seine Berechtigung. Klar, jeder Mensch und jede Menschensprache auch. Nur gibt es auch Mörder und Kaudawelsch.
Wollen wir wirklich mörderisches Chaos? Wollen wir wirklich Programmiersprachen als Kaudawelsch? Sicherlich sehr künstlerisch, und sicherlich auch sehr cool. Nur leider nicht zielstrebig um folgende Punkte zu lösen:
* Schnelles Auffinden von Code-Stellen.
* Leichtes Einarbeiten in neuen Code.
* Schnelles Implementieren von neuen Features.
* Zukünftige und andauernde Verwendung dieses Programmierkonstrukts.
Ziel ist es eine Programmierkonstrukt zu bekommen, welches die Punkte, wie oben beschrieben erfüllt:
Ziele:
* Schnelles Auffinden von Code-Stellen.
* Leichtes Einarbeiten in neuen Code.
* Schnelles Implementieren von neuen Features.
* Zukünftiges und andauerndes Verwenden des Programmierkonstrukts.
* Möglichst einfaches und fehlerfreies implementieren.
Das Programmierkonstrukt brauch eine hierarchische Ordnung. Es sollte folgende schon vorhandene und bewährte Hierarchien übernehmen.
Eigenschaften:
* Prozesse und Threads
* Memory Pages und Shared Memory
* Daten in JSON and Binary-Part in JSON
Im Prinzip ist ein Rechner eine Turing-Maschine. D.h. er besteht nur aus Einem Band, einem Schreib/Lese-Kopf und einem Alphabet mit Regeln.
Das Band sind Memory Pages und Shared Memory. Der Schreib-/Lese-Kopf sind die Prozesse und Threads. Das Alphabet sind die Daten und Programme. Und die Regeln sind die Rechenoperationen der CPU.
Im Prinzip lässt sich alles auf ein Netzwerk von Daten und Programminstruktionen reduzieren. In diesem Netzwerk verläuft man nun einen Weg. Um genauer zu sein, ist der Weg immer einen Round-Trip, sonst muss man die Maschine immer wieder neu-starten. Was dann auch einem Round-Trip entspricht.
Es bietet sich nun an einen Round-Trip immer im kürzesten Weg zu machen, denn wir wollen ja eine schnelle Maschine. Und nicht die Waschmaschine mit einem Teil.
D.h. der Programmierer ist immer dabei bei gegebenen Daten und Instruktionen den kürzesten Round-Trip zu formulieren, so dass am Ende das gewünschte Endprodukt entstanden ist, oder der gewünschte Prozess durchgeführt wurde.
Das Programmkonstrukt soll den Programmiere nun dabei unterstützen diese Round-Trips zu erschaffen und dabei die oben genannten "Ziele" zu berücksichtigen.
Man sieht sofort, es ist nicht möglich durch chaotische Programmkonstrukte einen kürzesten Round-Trip zu finden.
Ein Beispiel für einen gelungenen Round-Trip wäre:
Round-Trip A
1. warte auf User-Input
2. Lese User-Input
3. If (data x == 1) starte Round-Trip B
4. Drucke Information auf Bildschirm
5. Beginne wieder mit 1.
Round-Trip B
1. Drucke "Wie ist Dein name".
2. Warte auf User-Input
3. Drucke "Hallo " + Data y + " !"
4. Beginne mit Round-Trip A.1.
Wie man an dem Beispiel sieht sind mehrere Round-Trips auch miteinander Verknüpft. Jedoch wissen Informatiker, dass dabei nicht ein wildes umherspringen zwischen den Round-Trips passieren sollte, wie es z.B. mit Goto-Anweisungen früher der Fall war. Sonder, dass jeder Round-Trip auch einen klaren Pfad haben sollte, der einem "kurzen" Weg entsprechen sollte. "kurz" hier in dem Sinne von nützlich. Es ist z.B. nicht nützlich in B.2.5. einen Schritt "Warte auf User-Input" zu setzen und die Eingabe dann zu verwerfen. Denn, das wäre dann die Waschmaschine mit nur einem Teil.
Unter der Betrachtung von Daten und Instruktionen als Punkte-Menge, wäre das eine Abzweigung ohne zurück zu kommen. Demnach kein Round-Trip, demnach hier nicht gewünscht.
Aus der Lösung eines Travelling-Salesman-Problem (TSP) wissen wir, dass ein kürzester Round-Trip durch ein Devide-And-Conquer-Verfahren gelöst werden kann. D.h. der Raum wird in Teilräume unterteilt und jeder Teilraum löst wieder ein TSP.
Die Punkte im TSP ist das Turing-Maschine Alphabet mit Daten und Instruktionen. Jedes Datum ein Punkt und jede Instruktion ein Punkt. Auf diesen Knoten bilden wir nun die Struktur.
Aus dem TSP-Solver wissen wir, dass es eine hierarchische Baumstruktur seien sollte.
Unterste Ebene: Binärdaten
zweite Ebene: Primitive Data-Types (float, int, double, long, char)
dritte Ebene: JSON oder binary JSON. Am besten beides.
JSON ist dann eine hierarchische Ordnung der Daten und damit das Ziel erreicht.
Instruktionen:
Unterste Ebene: Maschinencode
zweite Ebene: Assembler-Befehle
dritte Ebene: Konstrukte höherer Programmiersprachen
vierte Ebene: OOP
fünfte Ebene: Spring-Framework?
Bei OOP sind wir in der hierarchischen Ordnung für Daten angekommen.
Jetzt benötigen wir noch eine hierarchische Ordnung/Aufteilung dieser Daten/Instruktionen.
Das ist zum einen die OOP, die zugehörige Daten mit Instruktionen verbindet und zum anderen, unser gesuchtes Programmkonstrukt, welches Diese OOP's dann wieder in Bereiche einteilt.
Eigenschaften des neuen Konstrukts:
* Jeder Bereich sollte maximal und minimal einen Round-Trip enthalten.
* Die Round-Trips, welche ineinander gehen, liegen in der hierarchie nebeneinander.
* Der oberste Knoten in dem Konstrukt sollte Versionierung und Varianten enthalten. Versionierung um eine Zeitskala abzubilden und Varianten um die Frage "für wen" abzubilden. Also kundenspezifische Varianten.
* Die oberen Nodes im Baum sollten auf beliebige Tiefe laufen können um mehrdimmensionale Eigenschaften abzubilden. Z.b. erste Ebene ist der Kunde, zweite Ebene ist der Ort/die Maschine, und dritte Eben ist die Version.
* Aspect-Orientierte-Programmierung sollte durch die Hierarchie ermöglicht werden.
D.h. von dem ursprünglichen Zweig kann jeweils immer eine andere Variante abgezweigt werden, die nur eine Erweiterung des Code's vom Original enthält.
* Prozess-hierarchien wie sie bei Multiprozessor-Technologien erscheinen, sind durch die Hierarchie im Programmierkonstrukt ebenfalls abgedeckt. D.h. das Programmkonstrukt brauch noch festgelegte Struktur, bevor es in die oberste, freie Struktur der Varianten gehen kann.
Threads sind gut in Prozesse gekapselt.
Memory ist gut in Pages und shared Memory eingeteilt.
Festplatten sind gut in Sektionen aufgeteilt.
Damit sind die Turing-Maschinen Features unterteilt.
Bleibt nur noch die Hierarchie für alle Komponenten zusammen.
Gewünscht ist:
* Mehrere Prozesse sollen miteinander Kommunizieren.
* Mehrere Daten und Instruktionen sollen miteinander Verbunden werden.
* Mehrere Zugriffsmöglichkeiten auf Memory und Festplattte sollen Verbunden werden.
Aktuelle Lösung:
* Prozesse kommunizieren über Inter-Process-Communication.
* Daten und Instruktionen sind in Bibliotheken miteinander verbunden.
* Zugriffsmöglichkeiten sind auf Memory und Festplatte über Datenbanken verbunden.
Gesucht ist also ein Konstrukte, welches:
* Inter-Process-Communication macht. Auf hierarchische Art-und-Weise.
* Bibliotheken und Versionierungssystem enthält.
* Und eine verteilte Datenbankanbindung nach dem CouchDB Prinzip enthält.
CouchDB:
Primitive Instructions einer Datenbank sind: query, edit, add und delete.
Eigenschaften sind: append-only updates, indizes as b-trees.
Pro CouchDB:
* Document-Based
* "Views are the method of aggregating and reporting on the documents in a database"[¹]
* "as many different view representations of the same data as you like"¹
Contra CouchDB:
* "When CouchDB documents are updated, all data and associated indexes are flushed to disk"[1]
MongoDB:
Neben CouchDB gibt es noch eine nach meiner Meinung geeignetere Datenbank.
Diese ist MongoDB. Sie ist insbesondere besser geeignet, da sie Consistency garantiert und nicht wie CouchDB zwischen verschiedenen Clients evtl. veraltete Daten besitzt. Die schnelle Erreichbarkeit ist eine andere Frage und kann einfacherweise später auf Consistency drauf gesetzt werden.
Pro MongoDB:
* Document-based,
* Consistency.
* typical find() method for queries.
Contra MongoDB:
* nicht so gute Availability.
Beide Datenbanken haben einen entscheidenden Nachteil. Ihre Basis sind nicht Elemente, sondern Documente. Es können so nur ganze Documente einen Index enthalten. Für das Union-Find Problem auf Datenbanken wäre ein Mengen-Orientierte Datenbank noch praktischer.
==> Entscheidung für MongoDB
Bleibt noch das Paketsystem.
Und bleibt noch die Inter-Process-Communication.
==> Das Paketsystem is mnu für JavaScript updater.
==> Die Inter-Process-Communication ist dann mit Events auf der Basis von Node.js
Contra Node.js:
* keine Typisierung im JavaScript - die Differenzierung der Daten geht verloren.
(z.B. wie kann man einen 64Int in JavaScript darstellen? - nur mit einer Hilfsbibliothek, was zu Performance-Einbusen führt)
* Es ist ein Interpreter kein Compiler. Manche Fehler werden erst nicht zur Compilezeit aufgedeckt. Alles muss intensiver getestet werden, gerade, da Typ-Converting-Fehler auftreten können. (z.B. ein String in einen Integer).
* Eine Variable kann die eine Sekunde Integer und die andere Sekunde ein String sein. Daher keine klare Trennung von Daten.
* Keine besonderen Features guter Programmiersprachen, wie
- exception-handling
- Generics/Templates
- kein AOP (aspect-oriented-programming)
Pro Node.js:
* Sehr Funktionale-Programmiersprache, da viele sogenannte "Lambdas" verwendet werden. Trotzdem Prozedural.
* Performanz ist zum Glück bei vielen Anwendungen nicht notwendig.
==> Aufgrund der vielen Contras, entscheide ich mich doch für C++ mit Poco als Inter-Process-Communication (IPC) über TCP/IP und HTML/JSON
Angewandt heißt dies: Es benötigt ein Framework, welches MongoDB mit zusätzlicher verbesserter Availability, C++ in Kombination mit IPC über Poco und eine Versionierung mit AOP kombiniert.
Dabei muss Poco noch um Event-Driven Engineering erweitert werden. D.h. anstelle von Request-Response Schemas sollten Events in Poco eingeführt werden. Dies entspricht letztlich eher der Realität.
Auf dieser Struktur von C++ Poco und MongoDB kommt nun eine weitere Schicht Versionierung. Bei der Versionierung geht es darum für verschiedene Kunden verschiedene Versionen zu pflegen und dennoch eine gemeinsame Linie zu führen pro Produkt.
(Außerdem muss für die TCP Connection noch ein stabiles Messaging implementiert werden, in dem die Pakete mit und ohne Reliability verschickt werden können.)
[1] https://wiki.apache.org/couchdb/Technical%20Overview
folgender Text ist unausgereift und hier nur als Skizze zu sehen.
eigentlich ist es ja so: Mit jeder neuen Technologie stellt sich die Frage, ob man diese brauch. Auch ist es immer wieder fraglich, ob es vorteilhafter wird, ob es einfacher wird, oder nur komplexer. Es stellt sich die Frage, ob die Technologie eine gute Idee war.
Prinzipiell ist jede Technologie gut. Jedoch gibt es auch die Möglichkeit eine unnötige Technologie zu besitzen oder Zeit in diese zu investieren. Man stelle sich vor, man hätte eine Waschmaschine, in die man nur ein Teil jeweils rein machen kann, die trotzdem eine Stunde pro Teil brauch. Oder ein stylischen Tretroller (Scooter), der ganze 10 kg wiegt.
Und im Prinzip verhält es sich mit der Programmierung gleich. Es gibt komplizierte Programmierkonstrukte, die mehr Chaos als Ordnung in die Programmierung bringen. Es sieht so aus, als ob nicht jedes Programmierkonstrukt geeignet ist. Es sieht so aus, als ob es ein optimale Technik geben könnte. Ich weiß, dass manche ja behaupten, jede Programmiersprache habe seine Berechtigung. Klar, jeder Mensch und jede Menschensprache auch. Nur gibt es auch Mörder und Kaudawelsch.
Wollen wir wirklich mörderisches Chaos? Wollen wir wirklich Programmiersprachen als Kaudawelsch? Sicherlich sehr künstlerisch, und sicherlich auch sehr cool. Nur leider nicht zielstrebig um folgende Punkte zu lösen:
* Schnelles Auffinden von Code-Stellen.
* Leichtes Einarbeiten in neuen Code.
* Schnelles Implementieren von neuen Features.
* Zukünftige und andauernde Verwendung dieses Programmierkonstrukts.
Lösung
Deshalb gibt es hier die Lösung.Ziel ist es eine Programmierkonstrukt zu bekommen, welches die Punkte, wie oben beschrieben erfüllt:
Ziele:
* Schnelles Auffinden von Code-Stellen.
* Leichtes Einarbeiten in neuen Code.
* Schnelles Implementieren von neuen Features.
* Zukünftiges und andauerndes Verwenden des Programmierkonstrukts.
* Möglichst einfaches und fehlerfreies implementieren.
Das Programmierkonstrukt brauch eine hierarchische Ordnung. Es sollte folgende schon vorhandene und bewährte Hierarchien übernehmen.
Eigenschaften:
* Prozesse und Threads
* Memory Pages und Shared Memory
* Daten in JSON and Binary-Part in JSON
Im Prinzip ist ein Rechner eine Turing-Maschine. D.h. er besteht nur aus Einem Band, einem Schreib/Lese-Kopf und einem Alphabet mit Regeln.
Das Band sind Memory Pages und Shared Memory. Der Schreib-/Lese-Kopf sind die Prozesse und Threads. Das Alphabet sind die Daten und Programme. Und die Regeln sind die Rechenoperationen der CPU.
Im Prinzip lässt sich alles auf ein Netzwerk von Daten und Programminstruktionen reduzieren. In diesem Netzwerk verläuft man nun einen Weg. Um genauer zu sein, ist der Weg immer einen Round-Trip, sonst muss man die Maschine immer wieder neu-starten. Was dann auch einem Round-Trip entspricht.
Es bietet sich nun an einen Round-Trip immer im kürzesten Weg zu machen, denn wir wollen ja eine schnelle Maschine. Und nicht die Waschmaschine mit einem Teil.
D.h. der Programmierer ist immer dabei bei gegebenen Daten und Instruktionen den kürzesten Round-Trip zu formulieren, so dass am Ende das gewünschte Endprodukt entstanden ist, oder der gewünschte Prozess durchgeführt wurde.
Das Programmkonstrukt soll den Programmiere nun dabei unterstützen diese Round-Trips zu erschaffen und dabei die oben genannten "Ziele" zu berücksichtigen.
Man sieht sofort, es ist nicht möglich durch chaotische Programmkonstrukte einen kürzesten Round-Trip zu finden.
Ein Beispiel für einen gelungenen Round-Trip wäre:
Round-Trip A
1. warte auf User-Input
2. Lese User-Input
3. If (data x == 1) starte Round-Trip B
4. Drucke Information auf Bildschirm
5. Beginne wieder mit 1.
Round-Trip B
1. Drucke "Wie ist Dein name".
2. Warte auf User-Input
3. Drucke "Hallo " + Data y + " !"
4. Beginne mit Round-Trip A.1.
Wie man an dem Beispiel sieht sind mehrere Round-Trips auch miteinander Verknüpft. Jedoch wissen Informatiker, dass dabei nicht ein wildes umherspringen zwischen den Round-Trips passieren sollte, wie es z.B. mit Goto-Anweisungen früher der Fall war. Sonder, dass jeder Round-Trip auch einen klaren Pfad haben sollte, der einem "kurzen" Weg entsprechen sollte. "kurz" hier in dem Sinne von nützlich. Es ist z.B. nicht nützlich in B.2.5. einen Schritt "Warte auf User-Input" zu setzen und die Eingabe dann zu verwerfen. Denn, das wäre dann die Waschmaschine mit nur einem Teil.
Unter der Betrachtung von Daten und Instruktionen als Punkte-Menge, wäre das eine Abzweigung ohne zurück zu kommen. Demnach kein Round-Trip, demnach hier nicht gewünscht.
Aus der Lösung eines Travelling-Salesman-Problem (TSP) wissen wir, dass ein kürzester Round-Trip durch ein Devide-And-Conquer-Verfahren gelöst werden kann. D.h. der Raum wird in Teilräume unterteilt und jeder Teilraum löst wieder ein TSP.
Die Punkte im TSP ist das Turing-Maschine Alphabet mit Daten und Instruktionen. Jedes Datum ein Punkt und jede Instruktion ein Punkt. Auf diesen Knoten bilden wir nun die Struktur.
Aus dem TSP-Solver wissen wir, dass es eine hierarchische Baumstruktur seien sollte.
Vorhandene Struktur
Daten:Unterste Ebene: Binärdaten
zweite Ebene: Primitive Data-Types (float, int, double, long, char)
dritte Ebene: JSON oder binary JSON. Am besten beides.
JSON ist dann eine hierarchische Ordnung der Daten und damit das Ziel erreicht.
Instruktionen:
Unterste Ebene: Maschinencode
zweite Ebene: Assembler-Befehle
dritte Ebene: Konstrukte höherer Programmiersprachen
vierte Ebene: OOP
fünfte Ebene: Spring-Framework?
Bei OOP sind wir in der hierarchischen Ordnung für Daten angekommen.
Jetzt benötigen wir noch eine hierarchische Ordnung/Aufteilung dieser Daten/Instruktionen.
Das ist zum einen die OOP, die zugehörige Daten mit Instruktionen verbindet und zum anderen, unser gesuchtes Programmkonstrukt, welches Diese OOP's dann wieder in Bereiche einteilt.
Neues Konstrukt
Eigenschaften des neuen Konstrukts:
* Jeder Bereich sollte maximal und minimal einen Round-Trip enthalten.
* Die Round-Trips, welche ineinander gehen, liegen in der hierarchie nebeneinander.
* Der oberste Knoten in dem Konstrukt sollte Versionierung und Varianten enthalten. Versionierung um eine Zeitskala abzubilden und Varianten um die Frage "für wen" abzubilden. Also kundenspezifische Varianten.
* Die oberen Nodes im Baum sollten auf beliebige Tiefe laufen können um mehrdimmensionale Eigenschaften abzubilden. Z.b. erste Ebene ist der Kunde, zweite Ebene ist der Ort/die Maschine, und dritte Eben ist die Version.
* Aspect-Orientierte-Programmierung sollte durch die Hierarchie ermöglicht werden.
D.h. von dem ursprünglichen Zweig kann jeweils immer eine andere Variante abgezweigt werden, die nur eine Erweiterung des Code's vom Original enthält.
* Prozess-hierarchien wie sie bei Multiprozessor-Technologien erscheinen, sind durch die Hierarchie im Programmierkonstrukt ebenfalls abgedeckt. D.h. das Programmkonstrukt brauch noch festgelegte Struktur, bevor es in die oberste, freie Struktur der Varianten gehen kann.
Festgelegte Struktur, bevor der freien Struktur.
Daten und Instruktionen sind gut in OOP gekapselt.Threads sind gut in Prozesse gekapselt.
Memory ist gut in Pages und shared Memory eingeteilt.
Festplatten sind gut in Sektionen aufgeteilt.
Damit sind die Turing-Maschinen Features unterteilt.
Bleibt nur noch die Hierarchie für alle Komponenten zusammen.
Gewünscht ist:
* Mehrere Prozesse sollen miteinander Kommunizieren.
* Mehrere Daten und Instruktionen sollen miteinander Verbunden werden.
* Mehrere Zugriffsmöglichkeiten auf Memory und Festplattte sollen Verbunden werden.
Aktuelle Lösung:
* Prozesse kommunizieren über Inter-Process-Communication.
* Daten und Instruktionen sind in Bibliotheken miteinander verbunden.
* Zugriffsmöglichkeiten sind auf Memory und Festplatte über Datenbanken verbunden.
Gesucht ist also ein Konstrukte, welches:
* Inter-Process-Communication macht. Auf hierarchische Art-und-Weise.
* Bibliotheken und Versionierungssystem enthält.
* Und eine verteilte Datenbankanbindung nach dem CouchDB Prinzip enthält.
CouchDB:
Primitive Instructions einer Datenbank sind: query, edit, add und delete.
Eigenschaften sind: append-only updates, indizes as b-trees.
Pro CouchDB:
* Document-Based
* "Views are the method of aggregating and reporting on the documents in a database"[¹]
* "as many different view representations of the same data as you like"¹
Contra CouchDB:
* "When CouchDB documents are updated, all data and associated indexes are flushed to disk"[1]
MongoDB:
Neben CouchDB gibt es noch eine nach meiner Meinung geeignetere Datenbank.
Diese ist MongoDB. Sie ist insbesondere besser geeignet, da sie Consistency garantiert und nicht wie CouchDB zwischen verschiedenen Clients evtl. veraltete Daten besitzt. Die schnelle Erreichbarkeit ist eine andere Frage und kann einfacherweise später auf Consistency drauf gesetzt werden.
Pro MongoDB:
* Document-based,
* Consistency.
* typical find() method for queries.
Contra MongoDB:
* nicht so gute Availability.
Beide Datenbanken haben einen entscheidenden Nachteil. Ihre Basis sind nicht Elemente, sondern Documente. Es können so nur ganze Documente einen Index enthalten. Für das Union-Find Problem auf Datenbanken wäre ein Mengen-Orientierte Datenbank noch praktischer.
==> Entscheidung für MongoDB
Bleibt noch das Paketsystem.
Und bleibt noch die Inter-Process-Communication.
==> Das Paketsystem is mnu für JavaScript updater.
==> Die Inter-Process-Communication ist dann mit Events auf der Basis von Node.js
Contra Node.js:
* keine Typisierung im JavaScript - die Differenzierung der Daten geht verloren.
(z.B. wie kann man einen 64Int in JavaScript darstellen? - nur mit einer Hilfsbibliothek, was zu Performance-Einbusen führt)
* Es ist ein Interpreter kein Compiler. Manche Fehler werden erst nicht zur Compilezeit aufgedeckt. Alles muss intensiver getestet werden, gerade, da Typ-Converting-Fehler auftreten können. (z.B. ein String in einen Integer).
* Eine Variable kann die eine Sekunde Integer und die andere Sekunde ein String sein. Daher keine klare Trennung von Daten.
* Keine besonderen Features guter Programmiersprachen, wie
- exception-handling
- Generics/Templates
- kein AOP (aspect-oriented-programming)
Pro Node.js:
* Sehr Funktionale-Programmiersprache, da viele sogenannte "Lambdas" verwendet werden. Trotzdem Prozedural.
* Performanz ist zum Glück bei vielen Anwendungen nicht notwendig.
==> Aufgrund der vielen Contras, entscheide ich mich doch für C++ mit Poco als Inter-Process-Communication (IPC) über TCP/IP und HTML/JSON
Freie Struktur
Die hier als "freie Struktur" bezeichnete Programmstruktur beinhaltet die Aufgabe alle besonderen und zusätzlichen Strukturen zu einem gemeinsamen Konzept zu vereinen. D.h. die Programmstruktur bildet einen Baum mit beliebiger Anzahl von Kindern über den oben vordefinierten Strukturen.Angewandt heißt dies: Es benötigt ein Framework, welches MongoDB mit zusätzlicher verbesserter Availability, C++ in Kombination mit IPC über Poco und eine Versionierung mit AOP kombiniert.
Dabei muss Poco noch um Event-Driven Engineering erweitert werden. D.h. anstelle von Request-Response Schemas sollten Events in Poco eingeführt werden. Dies entspricht letztlich eher der Realität.
Auf dieser Struktur von C++ Poco und MongoDB kommt nun eine weitere Schicht Versionierung. Bei der Versionierung geht es darum für verschiedene Kunden verschiedene Versionen zu pflegen und dennoch eine gemeinsame Linie zu führen pro Produkt.
(Außerdem muss für die TCP Connection noch ein stabiles Messaging implementiert werden, in dem die Pakete mit und ohne Reliability verschickt werden können.)
Referenzen
[1] https://wiki.apache.org/couchdb/Technical%20Overview
Abonnieren
Kommentare (Atom)