www.linux-swt.de

Edwards JavaScript vom wohnungslosen Hartz-IV Empfänger Homepage

Vorerst noch sind mathematische Irrtümer und flüchtige Programm- und Tippfehler vorbehalten. ;-)

{recent}

syntax.js

Hat die naechsten Stunden Bugs, bis ich weitermache. Ich muss jetzt erstmal los, 8:15.

var binary1 = 0b1111;
var binary2 = 0B0000;
var hex = 0xFA34FF33;
var hex2 = 0XFF;
var dec1 = 10e6;
var dec2 = 10e+6;
var dec3 = 10e-7;
var dec4 = .77;
var dec5 = 6.77;
var dec6 = 5333.2542e+12;
var oct1 = 0o0555;
var oct2 = 0O333;

Neben der Fortsetzung des NumericLiteral, habe ich gleich die EscapeSequence auf dem Programm stehen. Aber eigentlich geht es um die gesamte Grammatik. Schrittchen für Schrittchen. Ich muss erstmal die Grammatik weiterlesen. Wenn man auch nur einen Schnipsel nicht kann, weiss man nicht, was man jetzt eigentlich mit dem naechsten Zeichen machen will.

HTML5 Entities

Um schneller nach Entities suchen zu koennen, habe ich unten im Footer einen Link hinzugefuegt. Die WhatWG hat zu Kapitel 12.5 Named Character References eine JSON Datei veroeffentlicht, die als Grundlage dient.

html5entitySearch.html.

Spidermonkey 17

Ein aktuellerer Spidermonkey Code als JS 1.8.5 (2011) ist am 25. März 2013 mit Firefox 17 veröffentlicht worden. Ich habe das 6.5MB grosse Paket gerade mit 6.6k runtergeladen und zur Zeit läuft nach dem Configure der make Prozess. Ich hatte zum Ende letzten Jahres bereits begonnen, Spidermonkey auszuprobieren. Auch wenn ich bislang nicht in den Genuss komme, die aktuelle Beta Version des EcmaScript.next Interpreters in die Finger zu bekommen, ich finde keinen Link und auch der Einblick in das Mercury Repository bei Mozilla gibt mir keine Gewissheit, ohne vorher nachzufragen, habe ich vor, SpiderMonkey mal wieder ein wenig Zeit zu spendieren. Ich möchte mein C und C++ schliesslich auffrischen.

Gestern Abend habe ich wieder Single Variable Calculus (18.01) geguckt und mich mit d/dt, du/dx und anderen Funktionen beschaeftigt. d steht fuer derivative und heisst Ableitung. Oder anders, das ist eine andere Notation als f(x), aber nichts anderes, als auf die Ableitungsform hinzuweisen, die man aus Tabellen lernen kann (muss). Ich denke, das mit den Ableitungen kriege ich hin, dass fuer jedes xn → nxn-1 gilt, konnte ich mir letztens ja schon merken. Ebenso, wie man zwei Funktionen im Graphen in Relation zueinander bringt. Das habe ich aus dem Big Picture of Calculus, dem Zusatzmaterial, was fuer Open Course Ware produziert wurde, gelernt. Da geht noch einiges.

Ich bin immernoch traurig, weil unser Hasi gegangen ist. Viele Stunden haben wir zusammen am PC verbracht, er war bestimmt besser in Computer Science und Mathematics als ich. Zum EE sind wir nicht mehr gekommen. Wenn ich liege, stelle ich mir vor, wie er auf meinem Bauch liegt, und ich ueber sein Fell streichel. So kann es manchmal gehen.

Persistence

Persistence ist eine Datenstruktur, die nicht vergisst. Besser eingeordnet sind die Versionen in einem Graphen, ich habe die Versionen gerade in einem Versions Objekt gespeichert und einen Versionszaehler inkrementiert. In einer folgenden Fortsetzung werde ich die Baeume in einem Graphen speichern. Der ist besser dazu geeignet, sowohl die Versionen zu verwalten, als auch Relationen aufzunehmen.

Bei jedem insert, remove oder rotate, wenn sich der Baum aendert, wird eine neue Version erstellt. Darum habe ich beim Einfuegen von 10 Nodes gleich 10 Versionen.

Ich finde die Kopierfunktion, Persistence vergisst nicht und jede Version ist unique, noch sehr aufwendig. Ich erzeuge erstmal alle Nodes neu, dann verpointer ich alle Nodes nochmals. Mit einer Rekursion kann man die Nodes beim Verpointern erzeugen und die erstmal verpointern, weil es aber in mehrere Richtungen geht und nicht nur ein Pfad in eine Richtung ist, kann ich mir keinen Loop vorstellen, sondern Rekursion.

Jedenfalls ist Persistence die erste Datenstruktur aus 6.851 Advanced Data Structures, die ich mal ausprobieren möchte. Die nächste ist Retroactivity. Die kann vorherige Zeitpunkte wieder herstellen. Mit besonderen Nebeneffekten, die mit dem Beispiel Priorityqueue und Remove Min gezeigt werden, dessen Min sich gerade noch geaendert hat. Das ist wie bei Back to Future in Retroactivity. Aendert man die Vergangenheit, aendert sich die Zukunft (der Struktur).

ready(function (e) {
    var bst = new PersistentBST();
    for (var i = 0; i < 13; i++) bst.insert(i, "satellite data");
    bst.draw({ el: "#p1" });
    for (var i = 2; i < 13; i+=2) bst.rotate(bst.recent.nodes[i]);
    bst.draw({ el: "#p2" });
    for (var i = 4; i < 13; i++) bst.remove(i);
    bst.draw({el: "#p3" });    
    bst.draw({el: "#p4", version: 3 });
    bst.draw({el: "#p5", ms: 1000 });
});

So einfach ist der Code, der vom PersistenBST ist noch einfacher. Dem BST2 habe ich die duplicate Funktion hinzugefuegt. Somit kann er tiefe Kopien von sich erzeugen, nach dem ersten Gedanken, der noch abwägt, kann ich die für dies und das noch gebrauchen.

    duplicate: function () {
	var bst = new BST2();
	for (var k in this.nodes) {
	    n = this.nodes[k];
	    if (n)
	    bst.nodes[k] = bst.createNode(n.key, n.value, /* Die Value muesste man ebenfalls noch deepCopien, der Schritt sei hier ausgespart. Wenn Value ein Objekt ist, und sich aendert, dann ueberall... */ 
		n.parent ? n.parent.key : null,
		n.left ? n.left.key : null,
		n.right ? n.right.key : null
	    );
	}
	for (k in bst.nodes) {
	    n = bst.nodes[k];
	    if (n) {
	    if (n.parent !== null) n.parent = bst.nodes[n.parent];
	    if (n.left !== null) n.left = bst.nodes[n.left];
	    if (n.right !== null) n.right = bst.nodes[n.right];
	    }
	}
	if (this.root) bst.root = bst.nodes[this.root.key];
	return bst;
    },

Bestimmte Versionen

Die PersistentBST Struktur, denke ich, werde ich durch einen modifizierten Graphen ersetzen. Der wiederum generischer gestaltet werden kann, dass ich Persistence fuer BSTs, Graphen, Listen, Hashes, Arrays, ... nutzen kann. Natürlich geht das nicht alles mit einem Befehl, aber mit wenigen. Die kann man dann in einem Persistence Graphen vereinigen. Dem Graphen uebrigens, darf ich als naechstes Separatoren beibringen. Ich habe da einige Stunden drueber nachdenken koennen. 6.889, von dem ich erst die ersten vier Lektionen sehen konnte, faengt damit an. Schade, wenn man keinen hat, mit dem man drueber reden kann. Aber ich krieg das auch so hin. Dauert nur die paar Informationen * Suchfaktor laenger.

Alle Versionen

Als ich die Struktur zuerst probierte, lief sie. Als ich sie uploadete, durfte ich sie gleich fuenfmal aendern, weil ich eigentlich im Content vergass, dass von 10 bis 17 keine Nodes removed werden koennen, wenn man nur 9 einfuegt, so drehte ich mich kurz im Kreis und reparierte dabei noch was, was mir sonst spaeter gekommen waere. Ich habe dazu noch draw das version Attribut hinzugefuegt, so kann man x-beliebige Versionen zeichnen. Wenn man die nacheinander malt, sieht der Baum bestimmt animiert aus ;-)

function PersistentBST () {
    this.recent = new BST2();
    this.version = 0; 
    this.versions = Object.create(null);
    this.versions[0] = this.recent;
}
PersistentBST.prototype = Object.freeze({
    constructor: PersistentBST,
    insert: function (k,v) {
	this.recent = this.versions[this.version].duplicate();
	this.versions[++this.version] = this.recent;
	this.recent.insert(k,v);
	
    },
    remove: function (k) {
	this.recent = this.versions[this.version].duplicate()
	this.versions[++this.version] = this.recent;
	this.recent.remove(k);
	
    },
    rotate: function (node) {
	this.recent = this.versions[this.version].duplicate()
	this.versions[++this.version] = this.recent;
	this.recent.rotate(this.recent.nodes[node.key]);
    },
    find: function (k) {
	return this.recent.find(k);
    },
    successor: function (k) {
	return this.recent.successor(k);
    },
    predecessor: function (k) {
	return this.recent.predecessor(k);
    },
    draw: function draw (options) {
	var context = document.querySelector(options.el).getContext("2d");
	var v = this.version;
	var that = this;
	function aside () {
	context.save();
	context.fillStyle = "green";
	context.strokeStyle = "darkgreen";
	context.lineWidth = 0.1;
	context.shadowColor = "black";
	context.shadowX = 2;
	context.shadowY = 2;
	context.shadowBlur = 0.2;
	context.strokeText("# versions = "+that.version, 10,10,100,10);
	context.strokeText("actual ver = "+v, 10,20,100,10);
	context.stroke();
	context.restore();
	}
	if (options.ms) {
	    v = 0;
	    function redraw() {
		context.clearRect(0,0,context.canvas.width, context.canvas.height);
		aside();
		that.versions[v].draw(options);
		++v;
		if (v > that.version) v = 0;
		setTimeout(redraw, options.ms);	
	    }
	    redraw();
	
	} else if (options.version) (v=options.version), aside(), this.versions[options.version].draw(options);
	else aside(), this.recent.draw(options);
    }
});

Ein wenig geschmiert. Aber noch besser waere ein Graph. Womit wir beim naechsten Thema, was schonmal dran war, waeren. Waelder.

Wenn man keinen Graphen nimmt, kann man die paar Modifikationen am BST2 vornehmen.

Der Artikel ist jetzt informal. Eine formale Definition von Persistence gibt es in 6.851 Advanced Data Structures Lecture 01, die es zu erreichen gilt.

Shift Operationen

In JavaScript ist ein Shift vielleicht nicht perfekt, da erst von Integer zu Float umgewandelt wird und dann wieder in Integer, und eine normale Multiplikation wohl weniger Zyklen braucht. Das habe ich, ich sage mal, vor einem Jahr, mal aufgeschnappt. Das hat mich nicht daran gehindert den Shift zu nutzen, ich hatte vor einem Jahr noch nichts zu berechnen. Jedenfalls ist ein Shift leicht zu verstehen, man schiebt alle Bits um die angegebene Anzahl von Stellen nach links (Zahl wird groesser) oder nach rechts (Zahl wird kleiner).

    >(0xFF).toString(2);
    11111111	// Eine einfache Zahl als binaerer String ausgegeben, dass man das mitverfolgen kann.
    

Mit dem right-Shift schiebt man die Bits nach rechts. Bits die nun "ueber die Kante" gehen, werden "abgeschnitten" (fallen weg).

    >(0xFF >> 2).toString(2);
    111111	// Die beiden 1en ganz rechts sind aus dem Wort rausgeschoben.
    

Mit dem left-Shift schiebt man die Bits nach links. Rechts wird dazu "mit Nullen aufgefuellt."

    >(0xFF << 2).toString(2);
    1111111100 // Das Wort wird laenger. Ich denke, wenn man die 2^53 ueberschreitet, wird der Ueberschuss links abgeschnitten.
    

Eine Bitstelle nach Links → mal 2 nehmen

    var n = 1;
    > n <<= 1;
    2
    > n <<= 1;
    4
    > n <<= 1;
    8
    > n <<= 1;
    16
    > n <<= 1;
    32
    > n <<= 1;
    64
    > n <<= 1;
    128
    > n <<= 1;
    256
    

Und so weiter. Wenn man nach links shiftet, wird die Zahl groesser. Wenn man nach rechts shiftet, wird die Zahl kleiner.

Eine Bitstelle nach rechts → durch 2 teilen

    var n = 256
    > n >>= 1;
    128
    > n >>= 1;
    64
    > n >>= 1;
    32
    > n >>= 1;
    16
    > n >>= 1;
    8
    > n >>= 1;
    4
    > n >>= 1;
    2
    > n >>= 1;
    1
    

So einfach ist ein Shift in der Anwendung. Man muss praktisch nur ein Gefuehl fuer kriegen. Und auch wenn es richtig ist, dass ein Shift in JavaScript mehr Zyklen braucht, ist es kein Grund, es nicht zu benutzen oder zu koennen. Eher platzt mir das Lachen darueber raus. Und ich gedenke, ich beweise mir das lieber durch ausprobieren.

Entscheidungstabellen

Ich dachte darueber nach, die Entscheidungstabellen mal herauszugreifen, und zur Visualisierung und zur Generierung herauszunehmen. Beim Wiederholen des Kapitels Logik machen sich aber natuerlich groessere Strukturen auf. Jetzt denke ich, werde ich in mehreren Etappen dieses Kapitel wiederholen, da ich mich mal hier, mal da befinde und nicht durchgehend fuer einen Tag an der Maschine.

Weil es schon keinen Sinn macht, die Tabelle hier zu zeichnen, bevor sie gezeichnet werden kann, ich dafuer aber den Stoff erstmal wiederholen wollte, mir aber das Kapitel Logik an sich dazwischen kam, habe ich beim Lesen weitergeschrieben und daher einen schlechten Guttenberg kreiert. Was heisst kreiert. Ich habe gerade erst damit angefangen. Bevor ich den Code schreib, bring ich mir mal kurz bei, was ich da schreiben will.

Das kann jetzt was dauern. Das Wetter ist schöm. Unser Hasi ist gone. Ich bin mit den Gedanken woanders. Die Entscheidungstabelle ist eine Auswertungshilfe fuer Regeln. Jetzt habe ich vor, die zu zeichnen. Die Wiederholung des Kapitels Logik ist aber etwas umfangreicher. Ich bin noch nichtmal bei den ET und habe die Grammatiken ein wenig ueberlesen, weil ich die so gerne lese. Dabei haben sich jetzt noch Details aufgetan, die ich noch weit vertiefen kann. Denn da stehen noch mehr von drin.

Requirements Engineering

Diese Woche hatte ich den Vormittag immer eine Stunde lang genutzt, in dem Lehrbuch der Softwaretechnik, 3. Band, 3. Auflage zu lesen. Dabei habe ich einige altbekannte Dinge aus der 2. Auflage wieder aufgeschnappt, aber auch bereits neues bemerkt und verstanden. Ich finde die Wiederholung der Basistechniken (Prinzipien und Methoden), die Reflexion ueber Software an sich (Warum ist Software so schwer zu entwickeln?) natürlich super wie eh und je. Habe bemerkt, dass ich mich an ein paar Dinge gar-nicht-mehr erinnern konnte. Finde die Basiskonzepte Statik, Dynamik und Logik ebenfalls klasse. Mit letzterem werde ich mich als erstes von einigen Projekten ausfuehrlicher beschaeftigen. Und zum Schluss kommt das Requirements Engineering. Das Hauptthema, dass ich in den kommenden Wochen intensiv einueben will. In der Anforderungsermittlung und der schriftlichen Definition meiner Programme habe ich zur Zeit ja die groesste von allen Schwaechen. Es gab mal eine Zeit, da konnte ich alles in Modellen ausdruecken, nur den Implementierer, den konnte ich mir nicht liefern, auch wenn ich mich fuer hielt, obwohl ich gar die Grundveranlagung hatte. Jetzt scheint alles in Balance zu kommen. Und wenn es Monate dauert. Der [Balzert09] hat nichts an Qualitaet verloren. Im Gegenteil, anders als in der zweiten Aufgabe ist man nun vom Vorgehensmodell losgeloest und und und.

Von uns gegangen

Am 26.6.2013 ist unser Freund und Kaninchen Gizmo verstorben. Magst du es im neuen Leben schöner haben als je zuvor. Danke für all die Zeit, die du mit uns verbracht hast. Wir lieben dich. In tiefer Trauer, Mama Micro, Papa Edward, Pünktchen und Racker.

Fibonacci

Hatte ich auch noch nie als Rekurrenz-Grafik ausgedrueckt. Fibonacci, das ist die Geschichte von den Kaninchen, die ein neues Kaninchen zeugen, naechstes mal dann ein zweites, und dann macht das erste mit, und dann das zweite, und zeugen neue, die dann auch wieder neue zeugen. Die Geschichte gibt es auch mit dem Professor, der jedes Jahr einen neuen Professor hervorbringt, der ab dem zweiten Jahr selbst jedes Jahr einen Professor hervorbringt. Eine Geschichte von linearen Rekurrenzen. In der Programmierung eine Geschichte von Rekursion oder Memoisation. In der Hardware gibt es Fibonacci on Board.

In der Tat sind es 1972 Nodes bei fib(15). Dadurch, dass ich den gleichen Abstand nach links und nach rechts zeichne, ueberzeichnen sich die Nodes. Das was dabei aber besonders interessant ist, ist, dass es immer exakt die gleiche Formel ist, die die andere nach links und rechts uebermalt. Ich hatte durch einen Trick die wahre Breite des Baumes sichtbar gemacht, finde es durch die Angabe der recursion nodes aber nachvollziehbar, und sauberer, dass sich die Ziffern genau uebermalen. In Wirklichkeit sind es 1972 nodes, 986 links und 986 rechts. Dadurch, dass sich durch T(n-1)+T(n-2) aber immer n-m uebermalt, sieht es einfach wie ein Netz, statt ein Baum aus. Der dickere blaue Teil wiederholt sich also noch ungefaehr 30 mal.

Achso, der Trick, wie ich es sichtbar machte war, bei (m%2==0) andere Koordinaten zu nutzen. Dadurch lagen die Striche nebeneinander und dick. Und wenn man den richtigen Baum richtig zeichnen will, dafuer ist der Bildschirm zu schmal, sollte man dessen Abstaende um einen log base b von n Faktor von oben nach unten verkleinern. Bedeutet, dass die obersten beiden Nodes weit auseinander ist. Für richtige Canvasprogrammierung heisst es, eine riesige Bitmap zu erzeugen, und nur einen Ausschnitt in den Viewport des Canvas zu projezieren. Es gibt noch viele Moeglichkeiten, die ich beim Canvas lernen kann. Als ich letztens die affinen Transformationen wegliess, ging es darum, dass ich gerade drauf und dran war, die Transformationsmatrizen und die Vector Objekte selbst zu entwickeln, fuer normale Canvasprogrammierung sollte man aber die vorhandenen Funktionen nutzen. Und nochwas, ich benutze zur Bequemlichkeit eine open() und close() Funktion, die sogar Farben und Linie setzt, Pfade kreiert und beim Schliessen stroke ruft, im Sinne der Farben und Linien nicht mal ausfuehrlich. Im Sinne von Performance ist es aber guenstiger, wenn man alles malt und dann stroke oder fill ruft. So habe ich es jetzt bei fib gemacht. Er saved einmal, rekurriert, malt Linien mit moveTo und lineTo, schreibt strokeTexts und nach der Rekursion stroke ich dann mal. Als die open Funktion noch beginPath gerufen hatte, nachdem jedesmal (vor jedem Objekt) die aktuelle Transformation auf dem Stack landete (save()), brauchte die Funktion einige Sekunden laenger.

Hailstone

Lektion 1 von 6.005 Elements of Software Constructions (kommt nach 6.004 Computation Structures) beginnt auf Seite 1 des Kursmaterials mit einer sogenannten Hailstone Sequenz. Die beginnt bei n und hoert bei 1 auf und geht mit n/2 weiter, ist die Zahl gerade oder mit 3n+1, ist sie ungerade. Wozu die gut ist, oder woher die kommt, weiss ich noch nicht. Bin gerade nur soweit gekommen, dann hatte ich diese Funktion schnell zum ausprobieren geschrieben.

Also, die Ziffer geht bei geraden runter und bei ungeraden rauf. Das laesst sie hoch- und runterhuepfen. Es wird vermutet, dass sie fuer alle n gilt und immer die 1 erreicht, das ist aber immernoch eine offene Frage.

Die hailstone Sequence heisst so, weil Hagelkoerner sich so rauf- und runterbouncend in den Wolken bilden, bis sie eventuell genug Gewicht haben und zur Erde fallen.

    function hailstone(n) {
    console.log("---- hailstone sequence ---- for n = "+n);
    var seq = ""+n;
    while (n > 1) {
	if (n % 2 == 0) n = n/2;
	else n = 3*n+1;
	seq += ", " + n;
    }
    console.log(seq);
}

hailstone(1000);
hailstone(333);
hailstone(10);

/*
---- hailstone sequence ---- for n = 1000
1000, 500, 250, 125, 376, 188, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
---- hailstone sequence ---- for n = 333
333, 1000, 500, 250, 125, 376, 188, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
---- hailstone sequence ---- for n = 10
10, 5, 16, 8, 4, 2, 1
*/

Rekursionsbaum

In Introduction to Algorithms oder Kurs 6.046j Design and Analysis of Algorithms (aktueller Name) lernt man, Rekurrenzen der Form T(n) = aT(n/b) + f(n) zu loesen. In der 1999er Auflage von 6.046j, die man ueber OpenCourseWare einsehen kann, wird unter anderem eine Rekurrenz der Form T(n) = 2T(n/2) + cn gelöst. In diesem Fall, um die Analyse von Divide and Conquer Sortieralgorithmen einzuleiten. Die Formel fuer diese Rekursion wiederholt sich durchaus wohl auch anderswo, und variiert. Ich wollte die mal zeichnen.

Das Problem mit n Items wird in 2 Rekursionsschritten (a) je in 2 Haelften (b) geteilt. Wenn die Problemchen auf 1 geteilt sind, geht es mit dem return den Baum wieder hoch. Jedesmal verrichtet die Funktion c Arbeit an n/b Items.

Hier koennen die unterschiedlichsten Dinge passieren. Diese Funktion hier malt auf dem Weg runter. Mergesort teilt sich runter und merged auf dem Weg hoch. Mergesort benoetigt aber einen Extra Array. (Ich habe gestern einen in-place probiert, wird zu komplex, weil ich alles nach dem einsortieren, wieder einsortieren kann. Da kann man auch direkt Insertion Sort nehmen, heh. Quicksort ist da die richtige Loesung.) Jeden Schritt muss T(n/b) Arbeit verrichtet werden, was als ∑ von links nach rechts summiert T(n) oder c*n entspricht. Auf dem Weg nach unten sind das c*n/2, c*n/4, ..., die Quersumme ist immer c*n.

Die Hoehe ist lg n, im englischen Lehrbuch wird lg n fuer Logarithmus zur Basis 2 von n notiert, und so im Sprachgebrauch genutzt, dass mache ich auch so. Um alle Probleme zu einem geloesten Problem zusammenzufuehren muss man n mal lg n Schritte machen (return inbegriffen). Diese Schritte kosten c*n/b bis c*n fier T(n).

Anmerkung: Das Programm ist noch nicht in der Lage, aT(n/b) zu zeichnen, und kann nur 2T(n/2) korrekt darstellen. b ist als a^1 definiert. Was nicht korrekt dem Master Theorem entspricht. Ich denke aber mal, das Programm noch zu korrigieren, da es interessant ist. Es sollte aber neben aT(n/b) auch Lineare Rekurrenzen oder Fibonacci koennen, ich denke, das passt gut in ein kleines Skriptchen..

ready(function (e) {
    new RecursionTree({ 
    el: "#rec1",
    a: 2,
    c: 10,
    n: 7
    });
});    

AVL Tree

Die folgende Zeichnung zeigt einen AVL Tree. Meine BST Codes habe ich als nächstes alle aufzuräumen. Sie sind alle dreckig. Im BST2 Listing bereits richtig, durch ausprobieren aufgefallen, in BST noch nicht upgedated: Die predecessor und successor Funktionen haben, wenn er nicht drunter liegt, zu gucken, ob es eine Parent Node ist. Die Suche laesst sich naemlich in beide Richtungen durchsetzen. Habe ich gemerkt, als ich eine O(n) Reihe eingefuegt hatte und dann Vorgaenger und Nachfolger suchte und den, da er ja drueber lag, Vorgaenger, nicht ermitteln konnte, er aber da war. Jetzt aber zum AVL Tree. Hier hat mir diesmal das Kursmaterial von 6.006 den entscheidenden letzten Nerv geschaltet. Ich hatte vorgestern Abend mal das Material durchgeblaettert und auf avl.py geklickt. Gestern mittag konnte ich den dann aus dem Kopf in einem durch schreiben. Musste mich aber erstmal damit abfinden lernen, dass man die Handschrift des Lehrers erkennen kann. Jedenfalls stammt die Idee mit der height Funktion nicht von mir.

Der AVL Baum. 1962 entwickelt. Anfangsbuchstaben der drei Namen [...]. Der Baum ueberwacht seine Hoehe. Sollten die Subtrees eine Differenz groesser 1 aufweisen, wird der Baum ausbalanciert.

ready(function (e) {
    var avl = new AVLTree();
    for (var i = 0; i < 20; i++) avl.insert(i, "avl");
    avl.remove(13);
    avl.draw({ el: "#avl1" });
});
    

Wie bei jedem augmentierten BST, werden die Operationen zum korrigieren und balancieren direkt nach den inserts und removes aufgerufen. Beim AVL Tree wird die AVL-Eigenschaft korrigiert. Zusaetzlich wird nach jeder Rotation auch das height-Feld upgedated. Da die Funktion nicht rekursiv ist und nur Node, Left und Right updated (man kommt von unten nach oben und hat den darunterliegenden Teil in dem Falle bereits upgedated), wird sie in konstanter Zeit ausgefuehrt. Sollte ein Subtree schwerer sein, als der andere, wird eine Node rausrotiert, das macht die Funktion, die die Eigenschaft korrigiert. Sollte das passieren, wird beim Parent das gleiche probiert, und ggf. repariert. Dadurch entsteht ein wunderbar balancierter Baum. Besonders interessant ist der Schritt, wenn ein Subtree schwerer ist, zu gucken, welche Seite dessen schwerer ist. Weil die Node also durch rotation nur den leichteren noch leichter machen wuerde, wird ggf. die Node von der gegenueberliegenden Seite (vom schwereren Subtree im bereits schwereren Subtree unserer Node) geholt, um sie dann ueber unsere Node rauszurotieren. Am Ende von Lektion 6 bekommt man das erklaert. Und ich hatte vorgestern abend beim Blaettern des Kursmaterials einfach mal auf avl.py geklickt gehabt. Der Rest ist selbsterklaerend, sowas kann ich mir einfach merken.

    /* Die BST-Node bekommt ein height Field */
    function Node(k,v,p,l,r,x,y) {
	return {
	    key: k,
	    value: v,
	    parent: p || null,
	    left: l || null,
	    right: r || null,
	    height: 0			// <--- statt der rekursiven height Funktion sind die updates konstant und nur auf Hoehe der jeweiligen Node.
	};
    }
    /* Dieses wird returnt. Oder -1 bei null Pointern. Das gibt mit +1 wunderbare 0 fuer die Hoehe (6006 Lecture 6. AVL Trees) */
    function height (node) {
	return node ? node.height : -1;
    }
    /* 6.006 Diese Funktion ist konstant statt rekursiv und rechnet nur node, links, rechts, und nicht runter. */
    function fix_node_height (node) {
	if (node)
	node.height = Math.max(height(node.left), height(node.right)) + 1;
    }
    /* Es wird gewogen. Aus dem schwereren Subtree wird aus dessen schwereren Subtree eine Node rausrotiert. Sollte sie auf
    der gegenueberliegenden Seite liegen, wird sie erst rueber rotiert. Und dann raus. In 6006 wird das so aehnlich gemacht. */
    function fix_avl_property (node) {
	var c, h;
	if (!node) return null;
	fix_node_height(node);
	h = height(node.left) - height(node.right);
	if (h > 1) { 
	    if ((c=node.left) && (height(c.left) < height(c.right))) rotate(c.right);
	    rotate(c);
    	} else if (h < -1) { 
	    if ((c=node.right) && (height(c.right) < height(c.left))) rotate(c.left);
	    rotate(c);
	}
	fix_avl_property(node.parent);
	return true;
    }
    /* Nach der Rotation werden die heights upgedated. Nur ein Teil des Baums ist ueberhaupt betroffen.*/
    function rotate (x) {
	if (!x) return null;
	var y, z, B, left, r;
	var y = x.parent;
	if (!y) return null;
	r = y === root;
	z = y.parent;
	if (z) left = z.left === y;
	if (y.left === x) {
	    B = x.right;
	    x.right = y;
	    y.parent = x;
	    y.left = B;
	} else if (y.right === x) {
	    B = x.left;
	    x.left = y;
	    y.parent = x;
	    y.right = B;
	} 
	if (B) B.parent = y;
	x.parent = z;
	if (z) {
	    if (left) z.left = x;
	    else z.right = x;
	}
	if (r) root = x;
	fix_node_height(y);
	fix_node_height(x);
	return true;
    }
    /* Das Ergebnis kann sich sehen lassen. Mit einer definitiven Hoehe von O(lg n). */

Referenzen: Lecture 6, AVL-Trees in MIT OCW 6.006 Introduction to Algorithms (2010), aus dem OCW Kursmaterial avl.py (am Abend vorher ueberflogen).

Offene Forschung am BST: "dynamische Optimalitaet" (6.851/spring12) Lectures 5 und 6.

Gestern abend hatte ich hier noch einen ausfuehrlichen Artikel gepostet mit Ideen von Gut bis Maessig, um einen kompletten Baum zu erzwingen und um mir klar zu machen, dass mir avl.py diesmal geholfen hatte und ich unverkennbar die height Idee nicht selbst hatte. Ich hoffe, den jetzt durch einen besseren Abschnitt ersetzt zu haben.

Als naechstes werde ich unter anderem den RedBlackTree, den ich letzten Monat nach dem ersten Versuch mit einem recoloring-Bug stehen liess, korrigieren. Besonders aber werde ich das BST Skelett von function BST nochmals ueberarbeiten. Mir sind in den zwei, fast drei Wochen, die es das schon gibt, natuerlich noch allerhand Schoenheitsfehler aufgefallen, wie man ihn verbessern kann. Und wie oben genannt, Successor und Predecessor hatten, wie bei BST2 auffiel noch einen Bug. Sie guckten nur unterhalb von sich selbst. Was nicht sein muss, wenn man selbst im Intervall irgendwo zwischengeordnet ist und "die naechste Zaehl irgendwo oben links einen rechts" liegt.

Schönes Wetter draussen

Aufgrund des schönen Wetters gibt es diesen Monat nicht soviel Output, auch wenn meine Kapazitäten stetig wachsen. Ich gehe lieber raus. Ich gucke jeden Tag eine Lektion oder hoere sie im MP3 Player. Oder schreibe mal was, das ist sicher. Aber jetzt ist erstmal der Sommer dran. Ausserdem sind die neuen Lektionen, Advanced Data Structures (19 von 22), Planar Graphs and Beyound (7 von 22) und Geometric Folding Algorithms (1/2 Lektionen von vor dreineinhalb Wochen) diesen und naechsten Monat die, die mich nur langsam voranbringen, da ich 350MB mit 6.6k ueber 12 Stunden laden muss, um sie dann auf 220k und 20fps mpeg zu konvertieren, damit ich sie auf dem 933Mhz Pentium III mit 512MB (ohne 3D Grafikkarte) gucken kann. Darum werde ich diesem Monat etwas weniger Lectures machen. Ich gehe auch gleich wieder raus. Es ist warm draussen.

Open Course Ware

Aufgrund der Lernerfolge mit den Videos wird es Zeit, endlich mehr mit dem Kursmaterial zu machen und auch wissenschaftliches Schreiben einzuueben. Das gilt auch fuer meine Homepage, dass ich nicht mehr zwischendurch von mir rede, sondern nur von der Sache, von der Herkunft, bis zur Schritt fuer Schritt Dokumentation bis zum Ausblick, unter Nennung aller Quellen (das Einzige was ich laengst immer mache). Wissenschaftliches Schreiben, wie z.B. am MIT mit Scribe oder LaTeX verlangt wird, das muss ich mir beibringen. Blind bin ich ja auch nicht, mein Alltag ist voll von normalen Arbeiten auf dieser Schiene.

Workflow

Ich hab mich selbst zu kritisieren, ist mir verschaeft aufgefallen. Ich schreibe was. Ich poste das, weil ich denke, das so zu lassen. Ich lese es dann nochmal. Es hat Fehler?! Ich poste es nochmal. Das wiederholt sich dann zwanzig Minuten lang. Ich entferne den ganzen Artikel wieder und mache ohne den Post weiter. Wenn ich alle stehen gelassen haette, waere die Seite noch ein vielfaches laenger. Jedenfalls, auch wenn es nur ein Klick ist, der Transfer geht und dann noch ein Klick und wieder der Transfer und das ein Dutzend mal, das ist kein korrekter Arbeitsfluss, nicht ergonomisch und hat nur einen Hintergrund: ich haette mir vorher durchlesen sollen, was ich geschrieben habe. Dann haette ich alle Fehler auf einmal machen koennen. - Das ist mir aufgefallen und das ist dringend zu aendern von mir. Wenn ich mein Log auswerten wuerde, koennte ich mir das sogar beweisen.

Binary Search Tree 2

Ein anderer BST. Die Variante, die auf dem Canvas malt, ist gleichzeitig gekapselt. Man kann nicht auf die Nodes zugreifen. Da ich in den fortgeschrittenen Lektionen aber den BST oefter mal brauche, ist ein geschlossener Tree wie der andere eher inpraktikabel. Ich kann dann weder den Canvas gebrauchen, noch die Tatsache, dass ich ihn nicht als Prototype verwenden kann, der er gekapselte Member enthaelt, die nicht mehr von erbenden Objekten benutzt werden koennen. Zur Demonstration ist er fantastisch und den Constructor habe ich perfekt als Closure genutzt, koennte man sagen. Der hier ist garantiert schneller (konstruiert). Wie man sieht, gibt es keine Hilfsfunktionen in der Constructor-Closure, sondern viel this.* Auch wenn ich die andere Variante, JavaScript zu schreiben, prinzipiell besser finde. Aber wie man sieht, muss man auch hier balancieren. Ich brauche beide.

function BST2 () {
    "use strict";
    this.root = null;
    this.nodes = Object.create(null);
}
BST2.prototype = Object.freeze({
    constructor: BST2,
    createNode: function (k,v,p,l,r) {
	if (typeof k !== "number") throw "invalid key";
	return Object.seal({
	    key: k,
	    value: v,
	    parent: p||null,
	    left: l||null,
	    right: r||null
	});
    },
    insert: function (k, v) {
	var node;
	if (!this.root) {
	    node = this.createNode(k,v);
	    this.root = node;
	    this.nodes[k] = node;
	    return node;
	} else {
	    node = this.root;
	    for (;;) {
		if (k < node.key) {
		    if (!node.left) {
			node.left = this.createNode(k, v, node, null, null);
			this.nodes[k] = node.left;
			return node;
		    } else node = node.left;    
		} else if (k > node.key) {
		    if (!node.right) {
			node.right = this.createNode(k, v, node, null, null);
			this.nodes[k] = node.right;
			return node;
		    } else node = node.right;
		} else if (k === node.key) {
		    node.value = v;
		    return node;
		}
	    }
	}
    },
    find: function (k) {
	return this.nodes[k];
    },
    rotate: function (node) {
	var y, z, b, left, r;
	var y = node.parent;
	if (!y) return null;
	r = y === this.root;
	z = y.parent;
	if (z) left = z.left === y;
	if (y.left === node) {
	    b = node.right;
	    node.right = y;
	    y.parent = node;
	    y.left = b;
	} else if (y.right === node) {
	    b = node.left;
	    node.left = y;
	    y.parent = node;
	    y.right = b;
	}
	if (b) b.parent = y;
	node.parent = z;
	if (z) {
	    if (left) z.left = node;
	    else z.right = node;
	}
	if (r) this.root = node;
	return true;
    },
    predecessor: function (k) {
	var node = this.find(k);
	if (!node) return null;
	if (node.left) {
	    node = node.left;
	    do {
		if (!node.right) return node;
	    } while (node = node.right);
	} else if (node.parent) {
	    do {
		if (node.parent.right === node) return node.parent;
	    } while ((node = node.parent) && node.parent);
	}
	return null;
    },
    successor: function (k) {
	var node = this.find(k);
	if (!node) return null;
	if (node.right) {
	    node = node.right;
	    do {
		if (!node.left) return node;
	    } while (node = node.left);
	} else if (node.parent) {
	    do {
		if (node.parent.left === node) return node.parent;
	    } while ((node = node.parent) && node.parent);	
	} 
	return null;
    }, 
    remove: function (k) {
	var p, l, r, v, s;
	var node = this.find(k);
	if (node) {
	    p = node.parent;
	    v = node.value;
	    if (!node.left && !node.right) {
		if (p) {
		    if (p.left === node) p.left = null;
		    else if (p.right === node) p.right = null;
		} else this.root = null;
	    } else if (node.left && node.right) {
		s = this.remove(this.successor(k).key);
		node.key = s.key;
		node.value = s.value;
		this.nodes[s.key] = node;	
	    } else {
		if (node.left) {
		    if (p) {
			if (p.left === node) {
			    p.left = node.left;
			    p.left.parent = p;
			} else {
			    p.right = node.left;
			    p.right.parent = p;
			}
		    } else {
			node.left.parent = null;
			this.root = node.left;
		    }    
		} else if (node.right) {
		    if (p) {
			if (p.right === node) {
			    p.right = node.right;
			    p.right.parent = p;
			} else {
			    p.left = node.right;
			    p.left.parent = p;
			}
		    } else {
			node.right.parent = null;
			this.root = node.right;
		    }    
		}
	    }
	    if (!s) {
		node.parent = undefined;
		node.left = undefined;
		node.right = undefined;
		node.key = undefined;
		node.value = undefined;
	    }
	    this.nodes[k] = undefined;
	    return { key: k, value: v };
	}
    },
    minimum: function () {
	var node;
	if (node = this.root)
	do {
	    if (!node.left) return node;
	} while (node = node.left);
	else return null;
    },
    maximum: function () {
	var node;
	if (node = this.root)
	do {
	    if (!node.right) return node;
	} while (node = node.right);
	else return null;
    },
    removeMin: function () {
	if (this.root)
	return this.remove(this.minimum().key);
	else return null;
    },
    removeMax: function () {
	if (this.root)
	return this.remove(this.maximum().key);
	else return null;
    },
    height: function (node) {
	if (!node) return -1;
	return Math.max(this.height(node.left), this.height(node.right)) + 1;
    },
    depth: function (node) {
	if (!node) return -1;
	var depth = 0;
	while (node = node.parent) depth += 1;
	return depth;
    },
    inorder: function (node, f) {
	if (f && node) {
	    if (node.left) this.inorder(node.left, f);
	    f(node);
	    if (node.right) this.inorder(node.right, f);	
	}
    }, 
    print: function () {
	this.inorder(this.root, function (node) { console.log("k="+node.key, "v="+node.value); });
    }
});

/* Ein kleiner Testfall */

var tree = new BST2();
for (var i = -8; i < 20; i+=2) tree.insert(i, "value");
for (i = 1; i < 20; i+=2) tree.insert(i, "value");
tree.remove(2);
tree.remove(1);
tree.remove(-4);
tree.remove(12);
tree.remove(15);
tree.rotate(tree.find(10));
tree.rotate(tree.find(10));
tree.rotate(tree.find(10));
tree.rotate(tree.find(10));
tree.rotate(tree.find(4));
tree.rotate(tree.find(4));
tree.rotate(tree.find(4));
tree.rotate(tree.find(4));
tree.removeMin();
tree.removeMax();
tree.print();
console.log(tree.height(tree.root));
console.log(tree.depth(tree.root));
console.log(tree.depth(tree.root.right));

/*
k=-6 v=value
k=-2 v=value
k=0 v=value
k=3 v=value
k=4 v=value
k=5 v=value
k=6 v=value
k=7 v=value
k=8 v=value
k=9 v=value
k=10 v=value
k=11 v=value
k=13 v=value
k=14 v=value
k=16 v=value
k=17 v=value
k=18 v=value
7
0
1
*/

Ich denke, den werde ich oefter in den anderen Strukturen benutzen, der andere, mit dem Canvas, der ist dafuer ungeeignet.

Splay Tree

Nach dem fünften mal oder so, habe ich es endlich geschafft, mir den Algorithmus mal zu Ende anzuhoeren, hehe. Die Rotationsoperation ist an sich super einfach. Ich war aber mit RedBlackTree, AVL-Tree und Splay Tree erstmal durcheinander gekommen. So merkte ich gestern, dass ich mir den noch gar nicht gemerkt hatte.

Der Splay Tree ist ein BST, der bei find Operationen das Element an die Wurzel holt. Das geschieht durch Rotation. ‐ ‐ Wenn das Element nicht gefunden wird, wird das Element, wo die Suche stoppte, nach oben rotiert. ‐ ‐ Wird ein Node removed, wird dessen Parent nach oben rotiert. ‐

Die Rotationen sind einfache Links- oder Rechts-Rotationen. Die sind in den anderen Trees gleich. Man hat x, y mit den Subtrees a,b,c und der Teilbaum b (in der Mitte) verschiebt sich, waehren a und c an den beiden nodes bleiben. x und y tauschen die Plaetze. b liegt durch den Tausch aber weiterhin im richtigen Zahlenintervall.

Es gibt mehrere Faelle wie zu rotieren ist: Man ist entweder "das linke Kind eines rechten Kindes" oder "das rechte Kind eines linken Kindes". Dazu rotiert man dann erstmal die Node durch ihren Parent. Und dann rotiert man die Node durch den neuen Parent in die andere Richtung. Das sind die zig Operationen

Dann gibt es noch den Fall: Man ist das rechte Kind eines rechten Kindes. Oder halt links. Man rotiert in dem Fall erstmal den Parent durch den Grandparent. Und dann die Node durch dessen Parent. Effekt: Die Grandparent Nodes ruecken seitwaerts aus und der Baum balanciert sich quasi. Das sind die zig-zig Operationen.

Ich hab mir gestern abend CS61B Splay Trees (Uni von Berkeley, z.B. auf YouTube) nochmal angeguckt, bzw. gehoert, bevor ich eingeschlafen bin. Meine Frau schlief da schon. Ich bin dann am Rechner eingeschlafen. Ich hab mir das Prinzip jetzt gemerkt. Jetzt muss ich den Code noch schreiben. Ich hoffe, das gleich hier stehen zu haben, bevor ich wieder gehe.

ready(function (e) {
    var splay = new SplayTree();
    for (var i = 1; i < 21; i++) splay.insert(i, "val="+i);
    splay.remove(10);
    splay.find(19);
    splay.find(18);
    splay.draw({ el: "#splay1" });
});    
    

Drei Tage spaeter...Samstag um halb drei schreibe ich die Funktion. Als ich den Baum zeichne erscheint die Node 1 an der Spitze und alles was dran haengt. Es ist bereits rotiert. Und ich habe keine Ahnung, wo der Fehler ist, suche aber auch nicht danach. Ich habe das dann so gepostet, wie es war. Ich bin dann raus, Flaschen sammeln, weil wir kein Geld haben und draussen ein Stadtfest war. Das war genug, was ich da eingesammelt habe. Die Kaninchen sind gluecklich und wir auch. Auf dem Weg zur Haltestelle wusste ich bereits, was es war. Ich hatte nach dem Splay den root-Pointer (var root aus dem BST) nicht neu gesetzt. Ich hatte dann bereits vermutet, dass 1 ein left child einer Node ist. Die 10 entfernt wurde, die 18 und 19 gesplayed wurden, ich aber den Baum ab var root, also Node mit Key 1 zeichne. Als ich nach Hause kam, habe ich die Funktion kurz um die eine Zeile root = node; erweitert. ‐das schwirrte mir die ganze Zeit im Kopf rum, am liebsten haette ich es erraten und begruenden lassen ‐ Die folgenden Funktionen sorgen neben den BST Funktionen fuer die Splay Operation, die ich nach find aufrufe, und nach remove. Wenn eine Node nicht gefunden wird im nodes = {} Cache, dann rufe ich extra die BST-find Routine auf, um die letzte Node auf dem Pfad zu splayen. Wenn die Node entfernt wird, wir dessen Parent gesplayed. Nach der 10 haette wohl das die 9 sein muessen. Ich werde nun wohl mal einige Experimente machen koennen. Hat mich gefreut, dass ich mit der Vermutung, dass nur die eine Zeile fehlt, richtig lag. node = root am Ende von Splay. Darum wurde nach remove und find weiterhin ab 1 gemalt. Um zehn nach Acht hatte ich die Zeile dann zuhause kurz nach dem ich zurueckkam, ich musste den Rechner noch einschalten, aufgeschrieben.


    function rotate (x) {
	var y, z, B, left;
	var y = x.parent;
	if (!y) return null;
	z = y.parent;
	if (z) left = z.left === y;
	if (y.left === x) {
	    B = x.right;
	    x.right = y;
	    y.parent = x;
	    y.left = B;
	} else if (y.right === x) {
	    B = x.left;
	    x.left = y;
	    y.parent = x;
	    y.right = B;
	} 
	if (B) B.parent = y;
	x.parent = z;
	if (z) {
	    if (left) z.left = x;
	    else z.right = x;
	}
	return true;
    }
    function splay (node) {
	var p, g;
	if (!node || node === root) return null;
	while ((p = node.parent) !== null) {
	    if (p) g = p.parent;
	    if (g && p) {
		if ((g.left === p && p.left === node) 
		    || (g.right === p && p.right === node)) {
		    rotate(p);
		    rotate(node);
		} else {
		    rotate(node);
		    rotate(node);
		}
	    } else rotate(node);
	}
	root = node;
    }

Graph

Da der Array wirklich lahm ist, und ein Array.indexOf immer O(n) bietet, und das fuer das Durchsuchen der Vertices oder der Edges viel zu komplex wird, weil das Suchen eines Vertex oder einer Edge immer O(|V|) oder O(|E|->v) beansprucht, habe ich gestern abend bereits das Basiskonzept der Datenstruktur geaendert. Anstelle eines adjacents Array (der eine Adjacency List emuliert) gibt es nun zwei Objekte, die mit dem gleichen Key adressiert werden. v.edges[u] und v.weights[u] geben in konstanter Zeit alle Informationen raus, die man braucht. So sind Suchen praktisch konstant und Iterationen nur noch O(n) statt O(n²) oder aehnlich komplexer Stoff. Ich denke, die Algorithmen werden nun alle schneller fertig sein. Ich hatte den Source Code nach dem ersten Edit gestern abend hier gepostet. Ich muss ihn aber noch schoen schreiben, jetzt kann ich ihn nochmal von oben nach unten verbessern, ich mache das immer in einem kompletten Durchgang, oder gar nicht, und dann poste ich ihn nochmal an dieser Stelle.

	
	// statt mit O(n) einen Vertex zu suchen
	v.adjacents = []; 
	v.adjacents.push({ v: vertex, w: 12 });
	v.adjacents.some(function (e) {
	    if (e.v === u) {
		u = e.v;
		w = e.w;
		return true;
	    } else return false;
	});
	// oder aehnliches wie .indexOf, .every, .forEach
	// selbst mit for () oder for..in
	
	// lieber mit O(1) einen Vertex suchen
	v.adjacents = Object.create(null); 
	v.weights = Object.create(null);
	v.adjacents[vertex.key] = vertex;
	v.weights[vertex.key] = 23;
	u = v.adjacents[key];
	w = v.weights[key];
    

Man sieht den Unterschied kaum. Aber im naechsten Beitrag kann man eine kurze Messung lesen, wo der gravierende Unterschied zwischen Array.indexOf und dem [Subscript-Key] des Objekts direkt sichtbar wird. Und das ist die ganze Zeit so...Den object[key] muss man nur einmal computen. Einen Array zu durchsuchen aber mehrmals. Gehoert ja auch zu den Grundlagen, gell?

Hier nochmal kurz mein Edit.

function Graph (options) {
    "use strict";

    var me = this;
    var vertices = Object.create(null);
    
    function isKey (k) { return typeof k === "string" || typeof k === "number"; }
    function isFunction (x) { return typeof x === "function"; }

    function Vertex(key, value) {
	return {
	    key: key,
	    value: value || null,
	    edges: Object.create(null),
	    weights: Object.create(null),
	    cursor: { x: 0, y: 0 }  
	};
    }
    
    function unwrap (v) {
	return { key: v.key, value: v.value };
    }
    
    function forEach (S, f) {
	for (var s in S) {
	    f(S[s], s);	
	}
    }
    function forEach2 (v, E, f) {
	for (var e in E) {
	    f(v, E[e], v.weights[e]);	
	}
    }
    
    function get (u) {
	if (isKey(u)) return vertices[u];
	else throw "wrong type of key for vertex";
    }
    
    function connect(u, v, w) {
	var a, b;
	a = get(u);
	b = get(v);
	if (a && b) {
	    a.edges[v] = b;
	    a.weights[v] = w;
	    return true;
	}
	return null;
    }
    
    function disconnect(u, v) {
    	var a, b;
    	a = get(u);
    	b = get(v);
	if (a && b) {
	    a.edges[v] = undefined;
	    a.weights[v] = undefined;
	}
	return null;
    }
    
    function insert(k, v, u, w) {
	var a;
	if (a = get(k)) return null;
	a = new Vertex(k,v);
	vertices[k] = a;
	if (u) connect(k, u, w);
	return true;
    }
    
    function find(k) {
	var a;
	if (a = get(k)) return unwrap(a);
	else return null;
    }
    
    function remove(k) {
	var a, key;
	if (a = get(k)) {
	    for (key in vertices) disconnect(key, k);
	    vertices[k] = undefined;
	    return unwrap(a);
	}
	return null;
    }
    
    function update(k,v) {
	var old, a;
	if (!(a = get(k))) return null; 
	old = unwrap(a); 
	a.value = v; 
	return old; 
    }

    function indegree (u) {
	var deg = 0;
	if (!(u = get(u))) return null;
	forEach(vertices, function (v) {
	    if (v.edges[u.key]) ++deg;
	});
	return deg;
    }
    
    function outdegree (u) {
	if (!(u = get(u))) return null;
	return Object.keys(u.edges).length;
    }
    
    function dfs (v, f) {
    	var visited = Object.create(null);
	v = get(v);
	if (!v || !isFunction(f)) return null;
	f(v.key, v.value, null);
	visited[v.key] = true;
	traverse(v.edges);
	function traverse (adj) {
	    for (var a in adj) {
	        if (!visited[a]) {
	    	    v = vertices[a];
		    f(v.key, v.value);
		    visited[a] = true;
		    traverse(v.edges);
		}
	    }
	}
    }


    function bfs (v, f) {
    	var nodes = [];
	var visited = {};
	var level, data;
	v = get(v);
	if (!v || !isFunction(f)) return null;
	nodes[0] = [{ v: v, e: null, o: null, w: null }];
	visited[v.key] = true;
	summarize(v, 1);
	for (var i = 0, j = nodes.length; i < j; i++) {
	    level = nodes[i];
	    for (var k = 0, l = level.length; k < l; k++) {
		data = level[k];
		f(data.v.key, data.v.value, data.o, data.w);
	    }
	}
	function summarize (v, depth) {
	    var o = v.key,
		E = v.edges,
		e, k;
	    if (!nodes[depth]) nodes[depth] = [];
	    for (k in E) {
		if (!visited[k]) {
		    e = E[k];
		    nodes[depth].push({ v: e, o: o, w: v.weights[k] });
	    	    visited[k] = true;
		    summarize(e, depth+1);
		}
	    }
	}
    }

    
    function shortest_path (u,v) {
	var a = get(u);
	var b = get(v);
	var Q = [];
	var S = {};
	var d = {}; 
	var s, path = [];
	function search (o, v, w) {
	    var dist = d[o.key] + w;
	    var visited = d[v.key] !== undefined;
	    if (!d[v.key] || dist < d[v.key]) { 
		d[v.key] = dist; 
		S[dist] = { v:v, w:w, o:o, d: dist, p: d[o.key] }; 
	    }
	    if (v.key === b.key) Q.push(dist);
	    else if (!visited) forEach2(v, v.edges, search);
	}
	if (!a || !b) throw "there is no u or no v";
	d[a.key] = 0;
	forEach2(a, a.edges, search);
	Q.sort(function (a, b) { return a < b; });
	s = S[Q.pop()]; 
	path = [];
	if (s) {
	    do {
		path.push({ key: s.v.key, w: s.w, d: d[s.v.key] });
	    } while (s = S[s.p]);
	    return path.reverse();
	} else return null;
    }
    
    function print () {
	Object.keys(vertices).forEach(function (v, i) {
	    console.log((i+1)+". vertex: "+v+", "+vertices[v].value);
	    Object.keys(vertices[v].edges).forEach(function (e,j) {
		console.log((i+1)+".; edge ("+(j+1)+"): to="+e+", w="+vertices[v].weights[e]);
	    });
	});
    }

    function open (context, s,f,l) {
        context.save();
        context.beginPath();
        context.strokeStyle = s||"black";
        context.fillStyle = f||"beige";
        context.lineWidth = l||0.5;
    }
	
    function close (context) {
        context.closePath();
	context.stroke();
	context.restore();
    }

    function draw (context, options) {
	"use strict";

	/* Ich sollte lieber Cluster suchen, und die Grueppchen malen */

	var x = 35, y = 35, w = context.canvas.width - 20, h = context.canvas.height - 20;
	var size = vertices.length;
	var cols = w / 100;
	var rows = size / cols;
	var r = (options && options.r) || 15;
	var n = 1;
	var fontSize = 10;
	
	forEach(vertices, function (v) {
	    var s1, s2, s3;
	    ++n;
	    if (n > cols) {
		x = 30;
		y += 100;
		n = 0;
	    } else x += 100;
	    v.cursor.x = x;
	    v.cursor.y = y;
	    open(context,"lightgrey", "beige", 0.1);
	    context.arc(x,y, r, 0, 360);
	    context.fill();
	    close(context);

	    open(context);
	    context.strokeText(""+v.key, x-r, y-20, 100, 25);
	    close(context);
	    s3 = v.value || "";
	    if (s3.length*5 > 2*r) {
		s3 = s3.substr(0, 2*r-1);
		s1 = s3.substr(0, Math.floor(s3.length / 2)) + "-";
		s2 = s3.substr(Math.floor(s3.length / 2)) + "...";
		context.strokeText(""+s1, x-35, y, 100, 10);
		context.strokeText(""+s2, x-35, y+15, 100, 10);		
	    } else {		
		context.strokeText(""+s3, x-35, y, 100, 25);
	    }
	    close(context);
	});
	
	
	/* ich sollte lieber planar embedding lernen... */
	
	forEach(vertices, function (v) {
	    forEach(v.edges, function (d, k) {
		var vx = v.cursor.x;
		var vy = v.cursor.y;
		var dx, dy;
		dx = d.cursor.x; 
		dy = d.cursor.y;
		var a = dx - vx;
		var b = dy - vy;
		var i=Math.floor(dx - a/1.2);
		var j=Math.floor(dy - b/1.2);
		var x1,y1,x2,y2;	
			
		open(context,"blue", "blue", 0.5);
		context.moveTo(vx, vy);
		context.lineTo(dx, dy);
		context.globalCompositeOperation = "destination-over";
		close(context);
		
		open(context,"green", "lightgreen", 1);
		context.strokeText(""+v.weights[k], i, j, 25, 15);
		close(context);
	    });
	});
    
    }
    
    function draw_shortest (u, v, context, options) {
	var path = shortest(u,v);
	path.forEach(function (key,i) {
	        var u = get(key);
		var v = get(path[i+1]);
		if (u && v) {
		    open(context,"red", "red", 1);
		    context.moveTo(u.cursor.x, u.cursor.y);
	    	    context.lineTo(v.cursor.x, v.cursor.y);
		    close(context);
		}
	});
    }
    
    function animate (context, options) {
	var data = options.data;
	var i = 0;
	function paint () {
	    var node = data[i];
	    if (node.type === "insert") {
		insert();
		draw(); // quickly: draw whole graph
	    }
	    if (node.type === "remove") {
		remove();
		draw();
	    }
	    if (node.type === "connect") {
		connect();
		draw();
	    }
	    if (node.type === "disconnect") {
		disconnect();
		draw(); // spaeter mal schrittchen dazu und weg
	    }
	    if (i === data.length) {
		i = 0;
	    }
	    setTimeout(paint, 1000);
	}
	setTimeout(paint);
    }
    var me = this;
    if (me instanceof Graph === false) return new Graph(options);
    me.insert = insert;
    me.find = find;
    me.remove = remove;
    me.update = update;
    me.connect = connect;
    me.disconnect = disconnect;
    me.indegree = indegree;
    me.outdegree = outdegree;
    me.bfs = bfs;
    me.dfs = dfs;
    me.shortest_path = shortest_path;
    me.print = print;
    me.draw = draw;
    return Object.freeze(me);
}

/* Einfacher Testfall */

var g = new Graph();
g.insert("Edward1","Start");
g.insert("Edward2","B");
g.insert("Edward3","C");
g.insert("Edward4","D");
g.insert("Edward5","E");
g.insert("Edward6", "Ziel");
g.connect("Edward1", "Edward2",5);
g.connect("Edward2", "Edward5",2);
g.connect("Edward3", "Edward2",1);
g.connect("Edward1", "Edward6",1);		
g.connect("Edward3", "Edward4",7);
g.connect("Edward3", "Edward5",3);	
g.connect("Edward2", "Edward3",5);
g.connect("Edward2", "Edward4",2);
g.connect("Edward1", "Edward1",-1);

console.log("---");
g.print();
console.log("---");
g.bfs("Edward1", function () { console.dir(arguments); });
console.log("---");
g.dfs("Edward1", function () { console.dir(arguments); });
console.log("---");
console.dir(g.shortest_path("Edward1", "Edward6"));
console.log("---");
console.log(g.shortest_path("Edward2", "Edward5"));
console.log("---");
console.dir(g.shortest_path("Edward2", "Edward6"));
console.log("---");
console.log(g.shortest_path("Edward3", "Edward5"));

console.log("---");
console.log(g.indegree("Edward3"));
console.log(g.outdegree("Edward3"));
g.insert("ABC");
g.insert("DEF");
g.insert("GHI");
g.insert("JKL");
g.connect("ABC", "DEF", 1);
g.connect("DEF", "GHI", 1);
g.connect("GHI", "ABC", -2);
g.connect("GHI", "JKL", 1);

/*
---
1. vertex: Edward1, Start
1.; edge (1): to=Edward2, w=5
1.; edge (2): to=Edward6, w=1
1.; edge (3): to=Edward1, w=-1
2. vertex: Edward2, B
2.; edge (1): to=Edward5, w=2
2.; edge (2): to=Edward3, w=5
2.; edge (3): to=Edward4, w=2
3. vertex: Edward3, C
3.; edge (1): to=Edward2, w=1
3.; edge (2): to=Edward4, w=7
3.; edge (3): to=Edward5, w=3
4. vertex: Edward4, D
5. vertex: Edward5, E
6. vertex: Edward6, Ziel
---
{ '0': 'Edward1', '1': 'Start', '2': null, '3': null }
{ '0': 'Edward2', '1': 'B', '2': 'Edward1', '3': 5 }
{ '0': 'Edward6', '1': 'Ziel', '2': 'Edward1', '3': 1 }
{ '0': 'Edward5', '1': 'E', '2': 'Edward2', '3': 2 }
{ '0': 'Edward3', '1': 'C', '2': 'Edward2', '3': 5 }
{ '0': 'Edward4', '1': 'D', '2': 'Edward3', '3': 7 }
---
{ '0': 'Edward1', '1': 'Start', '2': null }
{ '0': 'Edward2', '1': 'B' }
{ '0': 'Edward5', '1': 'E' }
{ '0': 'Edward3', '1': 'C' }
{ '0': 'Edward4', '1': 'D' }
{ '0': 'Edward6', '1': 'Ziel' }
---
[ { key: 'Edward6', w: 1, d: 1 } ]
---
[ { key: 'Edward5', w: 2, d: 2 } ]
---
null
---
[ { key: 'Edward2', w: 1, d: 1 },
  { key: 'Edward4', w: 2, d: 3 } ]
---
1
3
*/

Sichere Benchmark

Ich hatte die Vermutung, dass ein Regulaerer Ausdruck bis zu kubischer exponentieller Komplexitaet besitzt, ohne darueber was gehoert zu haben. Es ist nur eine Vermutung. Aber fuer jedes Zeichen muss der gesamte Ausdruck neu probiert werden. Das heisst jedes | wird einmal abgefragt, wird der Ausdruck komplizierter, wird es komplexer. Pro Zeichen versteht sich, das Pattern wird von vorne probiert. Anders koennte ich die auch nicht schreiben. Was ich syntax.js uebrigens noch beibringen muss. Denn ich hab die Grammatik vom RegularExpressionLiteral noch nicht drin. Meine andere Vermutung war, dass die Zugriffe auf Objektschluessel quasi konstant sind. Beziehungsweise intern doch ein Hashtable genutzt wird, der konstante Zugriffe bringt. Bei den Arrays lass ich auf Stackoverflow mal, dass sie amortisierte O(1) bis O(n) haben. Je nach Operation. Was bei einem indexOf aber O(n) ausmacht. Zum Schluss habe ich noch einen konstanten Vergeleicht gemacht, weil ich mir dachte, dass er mithalten kann. Und das kommt zum Glueck noch hin. Ich habe bei groesserer Auslastung des Rechners, gerade spielte ein Video aber bereits staerkere Unterschiede gesehen, und sogar var liegt weiter hinten, wenn man var ich, var bin, usw. mit ihrem Stringwert prueft, was aber auch logisch ist. Aber so kann es gehen.


var str = "ich bin ein absolut toller mensch";
var reg = /ich|bin|ein|absolut|toller|mensch/;
var obj = {
    ich: true,
    bin: true,
    ein: true,
    absolut: true,
    toller: true,
    mensch: true
};
var arr = str.split(" ");
var test = str.split(" ");


var start = Date.now();
for (var a = 0, b = 1000; a < b; a++) {
for (var i = 0, j = test.length; i < j; i++) {
    if (reg.test(test[i])) {}
    else {}
}
}
var stop = Date.now();
console.log("regex: "+(stop-start)+"ms");

start = Date.now();
for (a = 0, b = 1000; a < b; a++) {
for (i = 0, j = test.length; i < j; i++) {
    if (obj[test[i]]) {}
    else {}
}
}
stop = Date.now();
console.log("obj: "+(stop-start)+"ms");


start = Date.now();
for (a = 0, b = 1000; a < b; a++) {
for (i = 0, j = test.length; i < j; i++) {
    if (arr.indexOf[test[i]] > -1) {}
    else {}
}
}
stop = Date.now();
console.log("arr: "+(stop-start)+"ms");


var x;
start = Date.now();
for (a = 0, b = 1000; a < b; a++) {
for (i = 0, j = test.length; i < j; i++) {
    x = test[i];
    if (x === "ich") {}
    else if (x === "bin") {}
    else if (x === "ein") {}
    else if (x === "absolut") {}
    else if (x === "toller") {}
    else if (x === "mensch") {}
    else {}
}
}
stop = Date.now();
console.log("var: "+(stop-start)+"ms");

/*
linux-qc69:~ for i in `seq 10`; do node benchmark.js >> results.txt; done

regex: 8ms
obj: 2ms
arr: 17ms
var: 2ms
regex: 8ms
obj: 1ms
arr: 18ms
var: 2ms
regex: 7ms
obj: 1ms
arr: 18ms
var: 2ms
regex: 8ms
obj: 1ms
arr: 18ms
var: 2ms
regex: 8ms
obj: 1ms
arr: 18ms
var: 2ms
regex: 8ms
obj: 2ms
arr: 44ms
var: 2ms
regex: 8ms
obj: 2ms
arr: 17ms
var: 2ms
regex: 16ms
obj: 2ms
arr: 51ms
var: 8ms
regex: 9ms
obj: 2ms
arr: 17ms
var: 2ms
regex: 8ms
obj: 1ms
arr: 33ms
var: 2ms
*/

Speeding up the BST

Ich denke, die O(lg n) Zugriffe fuer find kann man in JavaScript mit einem einfachen Trick loesen. Man nimmt ein Objektliteral var cache = {} und addet die Nodes wie folgt. Einfach mit cache[node.key] = node; und auslesen kann man sie mit node = cache[k]. Damit duerfte der Zugriff nun praktisch konstant O(1) sein. Zumindest wird intern nur noch der Hashkey computed. Loeschen kann man mit cache[k] = undefined;. Darf man nicht vergessen.

Beim Graphen habe ich das schon ausprobiert, so die Suche durch den Vertices Index abzukuerzen. Voraussetzung war, dass die Keys Strings waren. Hier kann man das ebenso machen. Wichtig ist aber, keinen Array zu nutzen, weil der anders als das Objektliteral sich auf die Groesse der groessten Zahl einstellt, was Counting Sort und Bucket Sort geradezu unertraeglich lahm bei grossen Zahlen macht.

k-tes Element

Es gibt andere Methoden, das k-te Element zu finden, aber um es in einem BST zu finden, kann man aber auch die inorder Funktion nutzen. Man muss mit O(lg n) O(h) (height) runter zum ersten Element, zaehlt bei jedem Visit mit und stoppt beim k-ten Element. Denn inorder beginnt beim kleinsten. Fiel mir gerade ein.

    function find_kth(k) {
	var i = 0;
	var kth = null;
	var cont = true;
	function inorder (node, f) {
	    if (cont && node.left) inorder(node.left, f);
	    if (cont) f(node);
	    if (cont && node.right) inorder(node.right, f);
	}
	inorder(root, function (node) {
	    ++i;
	    if (i === k) {
		kth = node;
		cont = false;
	    }
	});
	return kth;
    }
    

Um die Inorder Routine dann sofort zu stoppen, sollte man find-kth eine eigene Routine goennen, oder inorder generell eine Condition hinzufuegen, die man setzen kann, damit die Rekursion stoppt und man nicht die vollen O(n) bis zur letzten Node durchlaeuft (was keinen Sinn macht um was rauszuholen).

    function find_kth(k) {
	var i = 0;
	var kth = null;
	(function inorder (node) {
	    if (/*!kth &&*/node.left) inorder(node.left);
	    if (!kth && ++i === k) kth = node;
	    if (!kth && node.right) inorder(node.right);
	}(root));
	return kth;
    }
    

Update: So sieht das dann nochmal gekuerzt aus. Ich habe ueberlegt, ob ich das erste !kth nicht sogar loeschen kann. Ich vermute ja. Es wird einmal ausgefuehrt und rennt bei jeder node.right dann auch komplett durch, aber wir muessen das erste, oder das zweite kleinste Element dann erst gefunden haben, usw.

BST

Vom Binary Search Tree kann man nicht genug kriegen. Es gibt auch genuegend Applikationen fuer ihn. In einigen fortgeschrittenen Datenstrukturen hat man es mit ganzen Waeldern und querverbundenen Baeumen (in Graphen, Baeumen, oder Arrays gespeichert) zu tun. Zugriffe auf Elemente hat man in O(lg n) Zeit, was man auf einen sortierten Array mit Binary Search uebertragen kann. Man teilt in der Mitte. Guckt ob k groesser oder kleiner der Mitte ist und geht nach links oder rechts und wiederholt mit der Partition den gleichen Schritt. Das ergibt dann nur noch Bruchteile von n und im Berechnen den 2er-Logarithmus.

Preorder besucht erst die Node und dann rekursiv den linken und dann den rechten Subtree.


// Pre-Order Traversierung

ready(function (e) {
    var bst = new BST();
    bst.insert(7,"Sieben");
    bst.insert(5,"Funf");
    bst.insert(3,"Drei");
    bst.insert(1,"Eins");
    bst.insert(12,"Zwolf");    
    bst.insert(31,"Einunddreissig");
    bst.insert(13,"Dreizehn");
    bst.insert(14,"Vierzehn");
    bst.insert(17,"Siebzehn");
    bst.insert(4,"Vier");
    bst.remove(14);
    for (var i = 2; i < 20; i+=3) { bst.insert(i, "i="+i); }
    for (i = 8; i < 20; i+=3) { bst.remove(i); }
    bst.insert(40, "Vierzig");
    bst.insert(30, "Dreissing");
    bst.insert(11, "Eleven");
    bst.insert(15, "Fuffzehn");
    bst.draw({ el: "#bst1", type: "preorder" });
});

Inorder: Beginne zum Beispiel bei der Wurzelnode. Besuche erst die linke Node (*), dann die Node selbst, dann die rechte Node (*). (*) Wiederhole den Schritt beim besuchen der Node. Nutzt man die Traversierung zum Ausgeben der Zahlenschluessel, werden sie in sortierter Reihenfolge ausgegeben. Die Traversion sollte O(n) benoetigen, wobei n der gesamte Baum ist, oder ab die Wurzel bei der wir beginnen.


// In-Order Traversierung

ready(function (e) {
    var bst = new BST();
    bst.insert(7,"Sieben");
    bst.insert(5,"Funf");
    bst.insert(3,"Drei");
    bst.insert(1,"Eins");
    bst.insert(12,"Zwolf");    
    bst.insert(31,"Einunddreissig");
    bst.insert(13,"Dreizehn");
    bst.insert(14,"Vierzehn");
    bst.insert(17,"Siebzehn");
    bst.insert(4,"Vier");
    bst.remove(14);
    for (var i = 2; i < 20; i+=3) { bst.insert(i, "i="+i); }
    for (i = 8; i < 20; i+=3) { bst.remove(i); }
    bst.insert(40, "Vierzig");
    bst.insert(30, "Dreissing");
    bst.insert(11, "Eleven");
    bst.insert(15, "Fuffzehn");
    bst.draw({ el: "#bst2", type: "inorder" });
});

Postorder ist nutzlich im SibTree, der im DOM zum Einsatz kommt, so besucht man erst die Kinder (rekursiv) und dann die Node.


// Post-Order Traversion

ready(function (e) {
    var bst = new BST();
    bst.insert(7,"Sieben");
    bst.insert(5,"Funf");
    bst.insert(3,"Drei");
    bst.insert(1,"Eins");
    bst.insert(12,"Zwolf");    
    bst.insert(31,"Einunddreissig");
    bst.insert(13,"Dreizehn");
    bst.insert(14,"Vierzehn");
    bst.insert(17,"Siebzehn");
    bst.insert(4,"Vier");
    bst.remove(14);
    for (var i = 2; i < 20; i+=3) { bst.insert(i, "i="+i); }
    for (i = 8; i < 20; i+=3) { bst.remove(i); }
    bst.insert(40, "Vierzig");
    bst.insert(30, "Dreissing");
    bst.insert(11, "Eleven");
    bst.insert(15, "Fuffzehn");
    bst.draw({ el: "#bst3", type: "postorder" });
});

Levelorder: die trickreichste, aber ebenso einfache Variante. Man besucht jeden Level (Reihe) des Baumes vollstaendig und dann erst den naechsten Level. Das geht so: Man nimmt einen Queue (FIFO) und wirft die root-Node rein. Und jetzt wiederholen wir folgende Schritte. Wir holen das erste Element aus der Warteschlange. Wir besuchen sie. Ihr linkes und rechtes Child werfen wir in die Warteschlange. Dann nehmen wir uns das linke Child vor in dem wir das naechste Elemente aus der Schlange entfernen. Dessen Kinder kommen hinten in die Schlange. Dann entfernen wir das rechte (erste) aus der Schlange und werfen dessen Kinder rein. Jetzt haben wir root, links, rechts besucht und vier weitere in der Schlange (die 3. Reihe). Dann arbeiten wir das naechste ab, werfen dessen Kinder in die Schlange, so dass wir nach den 4 Kindern deren 8 in der Schlange haben, danach die 16, 32, usw. So wird der Baum fuer jede Etage abgebaut.


// Level-Order Traversion

ready(function (e) {
    var bst = new BST();
    bst.insert(7,"Sieben");
    bst.insert(5,"Funf");
    bst.insert(3,"Drei");
    bst.insert(1,"Eins");
    bst.insert(12,"Zwolf");    
    bst.insert(31,"Einunddreissig");
    bst.insert(13,"Dreizehn");
    bst.insert(14,"Vierzehn");
    bst.insert(17,"Siebzehn");
    bst.insert(4,"Vier");
    bst.remove(14);
    for (var i = 2; i < 20; i+=3) { bst.insert(i, "i="+i); }
    for (i = 8; i < 20; i+=3) { bst.remove(i); }
    bst.insert(40, "Vierzig");
    bst.insert(30, "Dreissing");
    bst.insert(11, "Eleven");
    bst.insert(15, "Fuffzehn");
    bst.remove(31);
    bst.draw({ el: "#bst4", type: "levelorder" });
});

Update: BST-remove. Ich hatte schnell rausgefunden, dass ich den Predecessor oder den Successor einsetzen kann. Ich habe dann einen Bug entdeckt, als ich die pruefen wollte. Der hat mich dazu gebracht, das nochmal zu schreiben. Die Nodes links und rechts waren nicht korrekt neu verlinkt. Darauf hin habe ich die komplette Funktion nochmal geschrieben. Dadurch lernt man sie auch verstehen. Ich haette das nicht gebraucht. Aber. Jetzt hatte ich noch kurz CS61B angemacht und die remove Funktion war bestaetigt und in einer Minute auf ein Minimum (4 Zeilen) refaktoriert. Ich brauche die ganzen Pointer nicht neu zu verlinken (die Node nicht umsetzen), sondern nur den Inhalt der Node neu zu setzen. Den Nachfolger habe ich mit den 4 Zeilen von vorher entfernt. Der Professor hat beim Zeigen an der Tafel nochmal gesagt, dass man den Successor entfernt und dessen Inhalt in die andere (eigentlich zu entfernende) Node setzt.. Ich weiss sofort was zu tun ist. Meine remove Funktion gibt den alten Inhalt der Node (nicht die Node) raus. Die habe ich bereits intern benutzt. Und die Predecessor Idee brauche ich nicht. Obwohl die zu 100% symmetrisch funktionieren wird. Und nochmal vergessen werde ich die Funktion auch nicht. Wie eine leckere Pizza. Man moechte gerne noch eine. Und noch eine und noch eine. Der Baum ist naemlich noch nicht balanciert. Und das ist noch gar nichts. In den fortgeschrittenen Strukturen werden die fuer alles moegliche eingesetzt.

function BST () {
    "use strict";
    var me = this;
    var root = null;
    var size = 0;
    
    var utils = { r: 15, a: 30, b: 4, d: 10 };

    /* Node */
    function Node (k,v,p,l,r, x, y) {
	if (typeof key !== "number") throw "invalid key";
	++size;
	return {
	    key: k,
	    value: v,
	    parent: p || null,
	    left: l || null,
	    right: r || null,
	    pos: { x: x||0, y: y||0 }
	};
    }
    function isNode (n) {
	return typeof n === "object" && n.key;
    }
    
    /* Insert */
    function insert(k,v) {
	var node;
	if (!root) {
	    root = Node(k,v);
	    return true;
	} else {
	    node = root;
	    while (node) {
		if (k === node.key) return false;
		if (k < node.key) {
		    if (!node.left) { node.left = Node(k,v,node); return true; }
		    else node = node.left; 
		} else if (k > node.key) {
		    if (!node.right) { node.right = Node(k,v,node); return true; }
		    else node = node.right;
		}
	    }
	}
	return false;
    }
    
    /* Search */
    function find (k) {
	var node = root;
	while (node) {
	    if (k == node.key) return node;
	    else if (k < node.key) node = node.left;
	    else if (k > node.key) node = node.right;
	}
	return null;
    }
    
    /* Left or Right Child ? */
    function position(n) {
	if (!n) return null;
	else if (!n.parent) return 0;
	else if (n.parent.left === n) return -1;
	else if (n.parent.right === n) return 1;
    }
    
    /* Remove */
    function remove (k) {
	var pos, left, right, suc, p, l, r, node, rval;
	if (!k) return;
	node = isNode(k) ? k : find(k);
	if (node) {
	    rval = { key: node.key, value: node.value };
	    p = node.parent;
	    l = node.left;
	    r = node.right;
	    pos = position(node);
	    left = pos === -1;
	    right = pos === 1;
	    if (!l && !r) {
		if (node != root) {
		    if (left) p.left = null;
		    else if (right) p.right = null;
		} else {
		    root = null;
		}
	    } else {
		if (l && !r) {
		    if (node !== root) {	
			if (left) p.left = l;
			if (right) p.right = l;
			l.parent = p;
		    } else {
			l.parent = null;
			root = l;
		    }
		} else if (!l && r) {
		    if (node !== root) {
			if (left) p.left = r;
			if (right) p.right = r;
			r.parent = p;
		    } else {
			r.parent = null;
			root = r;
		    }
		} else if (l && r) {
		    suc = successor(node);
	    	    suc = remove(suc);
		    node.key = suc.key;
		    node.value = suc.value;
		    return rval;
		}
	    }
	    node.parent = null;
	    node.left = null;
	    node.right = null;
	    node.key = null;
	    node.value = null;
	    node.pos = null;
	    --size;
	    return rval;
	}
	return null;
    }
    
    /* Vorgaenger, Nachfolger */
    function predecessor (k) {
	var node = isNode(k) ? k : find(k);
	if (!node.left) return null;
	node = node.left;
	do {
	    if (!node.right) return node;
	} while (node = node.right);
	return null;
    }
    function successor (k) {
	var node = isNode(k) ? k : find(k);
	if (!node.right) return null;
	node = node.right;
	do {
	    if (!node.left) return node;
	} while (node = node.left);
	return null;
    }
    
    /* Traversal */
    function inorder (k, f) {
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	if (node.left) inorder(node.left, f);
	f(node);
	if (node.right) inorder(node.right, f);
    }
    function preorder (k, f) {
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	f(node);
	if (node.left) preorder(node.left, f);
	if (node.right) preorder(node.right, f);
    }
    function postorder (k, f) {
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	if (node.left) postorder(node.left, f);
	if (node.right) postorder(node.right, f);
	f(node);
    }
    function levelorder (k, f) {
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	var q = [];
	q.push(node);
	while (q.length) {
	    node = q.shift();
	    f(node);
	    if (node.left) q.push(node.left);
	    if (node.right) q.push(node.right);
	}
    }
    
    /* Canvas */
    function open (context, s, f, l) {
	context.save();
	context.beginPath();
	context.lineWidth = l || 0.5;
	context.strokeStyle = s || "black";
	context.fillStyle = f || "beige";
    }
    function close (context) {
	context.stroke();
	context.closePath();
	context.restore();
    }
    function draw_node(context, node, s, f, l) {
	var x = node.pos.x;
	var y = node.pos.y;
	var r = utils.r;
        var a = utils.a;
        var b = utils.b;
        open(context, s, f, l);
        context.moveTo(x,y);
	context.arc(x,y,r,0,360);
	context.fill();
	context.strokeText(""+node.key,   x- r+b, y-r+b, a-2*b, r-b);
	context.strokeText(""+node.value, x- r+b, y,     a-2*b, r-b);
	close(context);
    }    
    function draw_line (context, x, y, px, py) {
        open(context);
        context.globalCompositeOperation = "destination-over";
        context.moveTo(px,py);
        context.lineTo(x,y);
        close(context);
    }
    function drawerse (context, node, x, y, px, py, row) {
	var r = utils.r;
	var d = utils.d;
        var a = utils.a;
        var b = utils.b;
	var w = utils.w;
	var c = ((w/3)/row)/2;
	if (px && py) draw_line(context, x, y, px, py);
	if (node) {
	    node.pos.x = x;
	    node.pos.y = y;
	    draw_node(context, node);
	    if (node.left)  drawerse(context, node.left,  x-c-d, y+a+d, x, y, row+1);
	    if (node.right) drawerse(context, node.right, x+c+d, y+a+d, x, y, row+1);
	}
    }
    function anim (context, data) {
	var i = -1;
	var ms = 1000;
	var node, last;
	function next() {
	    ++i;
	    if (i < data.length) {
	        last = node;
	        node = data[i];
	        if (last) draw_node(context, last, "black", "beige", 0.5);
	    	if (node) draw_node(context, node, "brown", "yellow", 0.5);
	    } else {
		i = -1;
	    }
	    setTimeout(next, ms);
	}
	if (data) setTimeout(next, ms);
    }
    function draw(context, options) {
	var type, el;
	if (arguments.length === 1 && context.el) options = context;
	else if (!options) options = {};
	type = options.type;
	if (el=options.el) context = typeof el === "string" ? document.querySelector(el).getContext("2d") : el;
	utils.w = context.canvas.width;
	utils.h = context.canvas.height;

	var x = Math.floor((utils.w-20) / 2) + 15;
	var y = utils.r + 15;
	
	drawerse(context, root, x, y, null, null, 1);
	switch (type) {
	case "inorder":
	case "preorder":
	case "postorder":
	case "levelorder":
	    draw_traversal(context, type);
	    break;
	default: break;
	}
    }
    function draw_traversal(context, type) {
    	var data = [];
    	var push = data.push.bind(data);
    	if (type === "inorder") inorder(root, push);
    	else if (type === "preorder") preorder(root, push);    	
    	else if (type === "postorder") postorder(root, push);    	
    	else if (type === "levelorder") levelorder(root, push);    	
    	if (data.length) anim(context, data);
    }
    
    /* Init */

    if (!(me instanceof BST)) return new BST;
    me.insert = insert;
    me.remove = remove;
    me.draw = draw;
    return Object.freeze(me);
}

Hier gibt es jetzt viel zu tun. Ich habe gestern Mittag gut eine Stunde damit verbracht. Ich hatte Animationen addiert und die BST-Remove Operation neu geschrieben. Und vorgestern ungefaehr 20 Minuten, da stand das erste Geruest des BSTs.

Wenn man nicht aufpasst, hat man schnell viele Funktionen zusammen. Oder wenn man aufpasst hat man schnell einen sehr guten Baum zusammen. Dieser hier ist zur Visualisierung gedacht. Ich denke mir, die Strukturen alle mal zeichnen zu wollen und auch das muss man erstmal lernen. Ein paar der Funktionen, die ich gestern noch schnell in zehn Minuten runterschrieb nochmal im folgenden.

bst / priority queues / heaps

Die Funktionen habe ich gerade in zehn Minuten geschrieben, ich weiss aber nicht, ob ich sie so einsetze. remove_min und remove_max sind bekannt, sie entfernen das kleinste oder groesste Element im Baum. Und die anderen Funktionen sind die Heapify Funktionen, die aus dem Baum den Array und wieder umgekehrt machen. Ich weiss aber nicht, ob ich sie drinlassen will. Min und Max und remove_min und remove_max vielleicht. Die kann jeder BST gebrauchen. Aber auch den Heap muss man vernuenftig ankoppeln. Darum.. Ich werds rausfinden.


    /* mir selbst gerade eingefallen. geht doch auch andersrum, oder? */
    function reverse_inorder (k, f) {
    	if (!k) return;
	var node = isNode(k) ? k : find(k);
	if (node.right) reverse_inorder(node.right, f);
	f(node);
	if (node.left) reverse_inorder(node.left, f);
    }
        
    /* Min und Max */
    function maximum (node) {
	node = node || root;
	do { 
	    if (!node.right) return node;
	} while (node = node.right);
    }
    function minimum (node) {
	node = node || root;
	do { 
	    if (!node.left) return node;
	} while (node = node.left);
    }
    /* priority queues / min- und maxheaps */
    function remove_min () {
	var node = minimum();
	if (node) return remove(node.key);
	return false;
    }
    function remove_max () {
	var node = maximum();
	if (node) return remove(node.key);
	return false;
    }
    /* BST to Heap */
    function min_array () {
	var array = [];
	inorder(function (node) {
	    array.push(node);
	});
	return array;
    }
    function max_array () {
    	var array = [];
	reverse_inorder(function (node) {
	    array.push(node);
	});
	return array;
    }
    /* Heap to BST (relink nodes in neuer reihenfolge) */
    function relink_nodes (array) {
	var j = Math.floor(array.length / 2);
	for (var i = 1; i <= j; i++) {
	    var node = array[i-1];
	    node.left = array[2*i-1] || null;
	    if (node.left) node.left.parent = node;
	    node.right = array[2*i] || null;
	    if (node.right) node.right.parent = node;
	}
	array[0].parent = null; // root
	return array;
    }
    /* heap: bst-property getter und setter */
    function getnode(array, i)	 { return array[i]; }
    function getparent(array, i) { return array[Math.floor(i/2)]; }
    function getleft(array, i)   { return array[2*i]; }
    function getright(array, i)  { return array[2*i+1]; }
    function setnode(array, i, node)   { return array[i] = node;  }
    function setparent(array, i, node) { return array[Math.floor(i/2)] = node; }
    function setleft(array, i, node)   { return array[2*i] = node; }
    function setright(array, i, node)  { return array[2*i+1] = node; }
    
    

Bei den remove_min (PRIORITY QUEUE) und minimum Funktionen bin ich mir sicher, dass ich sie uebernehme. Das verwandeln in einen Array hingegegen, was als HEAPIFIZIERUNG bekannt ist und mit der Datenstruktur BINARY HEAP (ein Array, der die BST Eigenschaften hat) eng verbunden ist, das sollte ich ohne get-/set- Operationen machen und mir eine bessere Verwandlung (min_array/max_array) und Rueckverwandlung (relink_nodes) einfallen lassen. Auch ein Uebungsbaum fuer den Canvas sollte nicht mit nutzlosem Zeugs ueberladen sein.

cp>Bereits ueberladen ?

/* 2. (weiter oben ist die einfachere Fassung. Ich bin noch skeptisch, ob das hier nicht bereits zuviel Schrott enthaelt.) */

function BST () {

    "use strict";
    var me = this;
    var root = null;
    var size = 0;
    var fastcache = Object.create(null);
    var min, max;

    var utils = { r: 15, a: 30, b: 4, d: 10 };

    /* Node */
    function Node (k,v,p,l,r, x, y, z) {
	++size;
	return {
	    key: k,
	    value: v,
	    parent: p || null,
	    left: l || null,
	    right: r || null,
	    pos: { x: x||0, y: y||0, z: z||0 }
	};
    }
    
    /* Help */
    function isNode (n) { return typeof n === "object" && n.key !== undefined; }
    function isKey (k) { return typeof k === "number" }
    function set (node) { fastcache[node.key] = node; }
    function get (k) { return fastcache[k]; }
    function del (node) { fastcache[node.key] = undefined; }
    function val (node) {  return node ? { key: node.key, value: node.value } : null; }
    
    /* Insert */
    function insert(k,v) {
	var node;
	if (!root) {
	    root = Node(k,v);
	    set(root);
	    return true;
	} else {
	    node = root;
	    while (node) {
		if (k === node.key) return false;
		if (k < node.key) {
		    if (!node.left) { 
			node.left = Node(k,v,node); 
			set(node.left); 
			return true; 
		    }
		    else node = node.left; 
		} else if (k > node.key) {
		    if (!node.right) { 
			node.right = Node(k,v,node); 
			set(node.right); 
			return true; 
		    }
		    else node = node.right;
		}
	    }
	}
	return false;
    }
    
    /* Search */
    function find (k) {
	var node;
	if (node = get(k)) return node;
	else node = root;
	while (node) {
	    if (k == node.key) return node;
	    else if (k < node.key) node = node.left;
	    else if (k > node.key) node = node.right;
	}
	return null;
    }
    
    function rank (k) {
	if (!isKey(k) || k > size) return null;
	var i = 0;
	var kth = null;
	var cont = true;
	function find (node, f) {
	    if (cont && node.left) find(node.left, f);
	    if (cont) f(node);
	    if (cont && node.right) find(node.right, f);
	} 
	find(root, function (node) {
	    ++i;
	    if (i === k) {
		cont = false;
		kth = node;
	    }
	});
	return kth;
    }
    
    
    /* Left or Right Child ? */
    function position(n) {
	if (!n) return null;
	else if (!n.parent) return 0;
	else if (n.parent.left === n) return -1;
	else if (n.parent.right === n) return 1;
    }
    
    /* Remove */
    function remove (k) {
	var pos, left, right, suc, p, l, r;
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	var rval;
	if (node) {
	    rval = val(node);
	    p = node.parent;
	    l = node.left;
	    r = node.right;
	    pos = position(node);
	    left = pos === -1;
	    right = pos === 1;
	    if (!l && !r) {
		if (node != root) {
		    if (left) p.left = null;
		    else if (right) p.right = null;
		} else {
		    root = null;
		    size = 0;
		}
	    } else {
		if (l && !r) {
		    if (node !== root) {
			if (left) p.left = l;
			if (right) p.right = l;
			l.parent = p;
		    } else { 
			l.parent = null;
			root = l;
		    }
		} else if (!l && r) {
		    if (node !== root) {
			if (left) p.left = r;
			if (right) p.right = r;
		        r.parent = p;
		    } else {
			r.parent = null;
			root = r;
		    }
		} else if (l && r) {
		    suc = successor(node);
	    	    suc = remove(suc);
		    del(node);
		    node.key = suc.key;
		    node.value = suc.value;
		    set(node);
		    return rval;
		}
	    }
	    del(node);
	    node.parent = null;
	    node.left = null;
	    node.right = null;
	    node.key = null;
	    node.value = null;
	    node.pos = null;
	    --size;
	    return rval;
	}
	return null;
    }
    
    /* Vorgaenger, Nachfolger */
    function predecessor (k) {
	var node = isNode(k) ? k : find(k);
	if (!node.left) return null;
	node = node.left;
	do {
	    if (!node.right) return node;
	} while (node = node.right);
	return null;
    }
    
    function successor (k) {
	var node = isNode(k) ? k : find(k);
	if (!node.right) return null;
	node = node.right;
	do {
	    if (!node.left) return node;
	} while (node = node.left);
	return null;
    }

    /* Min und Max */
    function maximum (node) {
	if (node && isKey(node)) node = find(node);
	else node = node || root;
	do {
	    if (!node.right) return node;
	} while (node = node.right);
    }
    function minimum (node) {
	if (node && isKey(node)) node = find(node);
	else node = node || root;
	do {
	    if (!node.left) return node;
	} while (node = node.left);
    }
    
    /* priority queues / min- und maxheaps */
    function remove_min () {
	return remove(minimum());
    }
    function remove_max () {
	return remove(maximum());
    }    
    
    /* Traversal */
    
    function inorder (k, f) {
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	if (node.left) inorder(node.left, f);
	f(node);
	if (node.right) inorder(node.right, f);
    }
    function preorder (k, f) {
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	f(node);
	if (node.left) preorder(node.left, f);
	if (node.right) preorder(node.right, f);
    }
    function postorder (k, f) {
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	if (node.left) postorder(node.left, f);
	if (node.right) postorder(node.right, f);
	f(node);
    }
    function levelorder (k, f) {
	if (!k) return;
	var node = isNode(k) ? k : find(k);
	var q = [];
	q.push(node);
	while (q.length) {
	    node = q.shift();
	    f(node);
	    if (node.left) q.push(node.left);
	    if (node.right) q.push(node.right);
	}
    }
    function reverse_inorder (k, f) {
    	if (!k) return;
	var node = isNode(k) ? k : find(k);
	if (node.right) reverse_inorder(node.right, f);
	f(node);
	if (node.left) reverse_inorder(node.left, f);
    }


    /* Canvas */
    function open (context, s, f, l) {
	context.save();
	context.beginPath();
	context.lineWidth = l || 0.5;
	context.strokeStyle = s || "black";
	context.fillStyle = f || "beige";
    }
    function close (context) {
	context.stroke();
	context.closePath();
	context.restore();
    }
    function draw_node(context, node, s, f, l) {
	var x = node.pos.x;
	var y = node.pos.y;
	var r = utils.r;
        var a = utils.a;
        var b = utils.b;
        open(context, s, f, l);
        context.moveTo(x,y);
	context.arc(x,y,r,0,360);
	context.fill();
	context.strokeText(""+node.key,   x- r+b, y-r+b, a-2*b, r-b);
	context.strokeText(""+node.value, x- r+b, y,     a-2*b, r-b);
	close(context);
    }    
    function draw_line (context, x, y, px, py) {
        open(context);
        context.globalCompositeOperation = "destination-over";
        context.moveTo(px,py);
        context.lineTo(x,y);
        close(context);
    }
    function drawerse (context, node, x, y, px, py, row) {
	var r = utils.r;
	var d = utils.d;
        var a = utils.a;
        var b = utils.b;
	var w = utils.w;
	var c = ((w/3)/row)/2;
	if (px && py) draw_line(context, x, y, px, py);
	if (node) {
	    node.pos.x = x;
	    node.pos.y = y;
	    draw_node(context, node);
	    if (node.left)  drawerse(context, node.left,  x-c-d, y+a+d, x, y, row+1);
	    if (node.right) drawerse(context, node.right, x+c+d, y+a+d, x, y, row+1);
	}
    }
    function anim (context, data) {
	var i = -1;
	var ms = 1000;
	var node, last;
	function next() {
	    ++i;
	    if (i < data.length) {
	        last = node;
	        node = data[i];
	        if (last) draw_node(context, last, "black", "beige", 0.5);
	    	if (node) draw_node(context, node, "brown", "yellow", 0.5);
	    } else {
		i = -1;
	    }
	    setTimeout(next, ms);
	}
	if (data) setTimeout(next, ms);
    }
    function draw(context, options) {
	var type, el;
	if (arguments.length === 1 && context.el) options = context;
	else if (!options) options = {};
	type = options.type;
	if (el=options.el) context = typeof el === "string" ? document.querySelector(el).getContext("2d") : el;
	utils.w = context.canvas.width;
	utils.h = context.canvas.height;
	var x = Math.floor((utils.w-2*utils.d) / 2) + utils.r;
	var y = 2*utils.r;
	drawerse(context, root, x, y, null, null, 1);
	switch (type) {
	case "inorder":
	case "preorder":
	case "postorder":
	case "levelorder":
	case "reverse_inorder":
	    draw_traversal(context, type);
	    break;
	default: break;
	}
    }
    function draw_traversal(context, type) {
    	var data = [];
    	var push = data.push.bind(data);
    	if (type === "inorder") inorder(root, push);
    	else if (type === "preorder") preorder(root, push);    	
    	else if (type === "postorder") postorder(root, push);    	
    	else if (type === "levelorder") levelorder(root, push);    	
    	else if (type === "reverse_inorder") reverse_inorder(root, push);    	
    	if (data.length) anim(context, data);
    }
    
    /* Init */

    if (!(me instanceof BST)) return new BST;
    me.insert = insert;
    me.remove = remove;
    me.remove_min = remove_min;
    me.remove_max = remove_max;
    me.successor = function (k) { if (isKey(k)) return val(successor(k)); };
    me.predecessor = function (k) { if (isKey(k)) return val(predecessor(k)); };
    me.min = function (k) { if (isKey(k)) return val(minimum(k)); };
    me.max = function (k) { if (isKey(k)) return val(maximum(k)); };
    me.size = function () { return size; };
    me.find = function (k) { if (isKey(k)) return val(find(k)); };
    me.rank = function (k) { if (isKey(k)) return val(rank(k)); };
    me.root = function () { return val(root); };
    me.draw = draw;
    return Object.freeze(me);
}
/*
var b = new BST();
b.insert(4);
b.insert(5);
b.insert(3);
b.insert(6);
b.insert(1);
console.log(b.size());
console.log(b.min());
console.log(b.max());
console.log(b.remove_min());
console.log(b.remove_max());
console.log("min="+b.min());
console.log("max="+b.max());
console.log("size="+b.size());
console.dir(b.find(3));
console.log(b.rank(2));
5
{ key: 1, value: null }
{ key: 6, value: null }
{ key: 1, value: null }
{ key: 6, value: null }
min=[object Object]
max=[object Object]
size=3
{ key: 3, value: null }
{ key: 4, value: null }
*/

Audio Files

Weil man OpenCourseWare nicht nur gucken kann, sondern auch hoeren, nehme ich die mir wichtigsten Themen auch als mp3 mit. Mit "ffmpeg -i lecture01.mp4 lecture.mp3" kann man sich den Audiotrack ohne Schwierigkeiten fuer den MP3 Player sichern.

Mit "ffmpeg -i L01_360p.mp4 -b:v 220k -r 20 L01-persistence.rm" kriege ich die modernen Aufnahmen im HD Format auf eine dem Computer angepasste Groesse runter. So kann ich mir die neuen Lektionen bald reinziehen. Mit dem USB-Stick brauche ich zwar drei Monate, bis ich sie komplett habe, aber in drei Monaten kann man auch eine Menge lernen.

Single Source Shortest Path

Ich erlaeutere den Algorithmus unterhalb. Ich speichere Gewicht und Distanz sowie Parent ab um den Pfad leicht zusammenzuzaehlen und zurueckerfolgen zu koennen. Ist nicht der beste Algorithmus, aber er tut schonmal seine erste Arbeit.

    function shortest_path (u,v) {
	
	var a = get(u);
	var b = get(v);
	var Q = [];
	var S = {};
	var d = {}; 
	var s, path = [];
 	
	function search (e) {
	    var v = e.d;
	    var o = e.o;
	    var w = e.w;
	    var dist = d[o.key] + w;
	    var visited = d[v.key] !== undefined; 
	    if (!d[v.key] || dist <= d[v.key]) { 
		d[v.key] = dist; 
		S[dist] = { v:v, w:w, o:o, d: dist, p: d[o.key] }; 
	    }
	    if (v.key === b.key) Q.push(d[v.key]);
	    else if (!visited) v.adjacents.forEach(search); 
	}
	
	if (!a || !b) throw "there is no u or no v";
	d[a.key] = 0;
	a.adjacents.forEach(search);
	Q.sort(function (a,b) { return a < b; });
	s = S[Q.pop()]; 
	if (s) {
	    do {
		path.push({ key: s.v.key, w: s.w, d: d[s.v.key] });
	    } while (s = S[s.p]);
	    return path.reverse();
	} else return null;
    }

Es ist mein eigener. Es ist ein einfacher Shortest-Path Algorithmus. aus dem errechnet, was ich bislang raus gelernt und lose behalten habe. Mein Algorithmus geht so. Ich hole mir den Start- und den Zielvertex raus O(1). Ich durchsuche die Edges des Startvertex. O(|E|->v) Ich addiere die Distanz zur bislang zurueckgelegten Distanz und speichere die Distanz zum Vertex mit einem kleinen Record in der Menge S ab. Achso und die Distanz zum Vertex speichere ich in d. Ein paar O(1).

Ist ein Eintrag in d schon vorhanden und der gefundene Pfad kuerzer , ueberschreibe ich ihn. (kleiner oder gleich steht da...es speichert den letzten gleichkurzen. Will jemand alle Wege wissen, muss er den Code editieren und alle Ergebnisse einen Array oder eine Liste speichern, ich ueberschreibe, das von Vertex zu einem anderne auf der Strecke liegenden Vertex auch immer der kuerzeste Weg uebrig bleibt.) Ist der Vertex === dem ZielVertex pushe ich die Zieldistanz in Q O(1).

Sollte der Vertex nicht der gesuchte Zielvertex sein, probiere ich von ihm aus alle Edges. Mit der gleichen function search (edge) {} und wieder O(|E|->v) und ein paar konstanten Termen zum Lesen und speichern der S[dist] Distanzen, einem Vergleich und entweder weiteren O(|E|->v) bei den naechsten Vertices. Q, das ist ein Priority Queue, den braucht man spaeter beim Dijkstra, ich fand die Idee mit dem sortierten Q anstelle einer min-Variable ganz cool, also Q, das ist ein Priority Queue,

simuliert durch einen JavaScript Array und einen nachfolgenden Q.sort O(n lg n) Funktionsruf, aus dem man den Key fuer den kleinsten Pfad mit pop() O(1) statt mit shift() O(n) dann auslesen kann. Den Key nutze ich dazu um anhand der Distanzen und den darunter gespeicherten Keys die Parents wiederherzustellen mit O(|S|). Dann drehe ich den Rueckwaerts zusammengebauten Pfad p nochmal um mit O(p).

Punkte in der Ebene

Bevor ich die kurze Rechnung entwickel, um zu gucken, ob ein Punkt in einer Ebene zwischen den Punkten ± Vektoren liegt, den ich in 18.02 auch schon mathematisch gesehen hatte, denke ich doch, muss ich erstmal einige Vorbereitungen treffen. Die Berechnung wird auch etwas laenger. Aber nicht zu lang.

    ready(function (e) {
    	var canvas = document.querySelector("#poly1");
	var context = canvas.getContext("2d");
	
	var q = new Polygon({ ss:"blue", fs:"maroon" });
	q.insert(80,84);
	q.insert(40,20);
	q.insert(10,3);
	q.insert(4,60);
	q.insert(2,73);
	q.insert(4,74);
	q.insert(3,84);
	q.insert(1,90);
	q.draw(context);
	q.isinplane(33,24, context);
	
	var p = new Polygon({ ss:"brown", fs:"yellow"});
	p.insert(30,10);
	p.insert(10,30);
	p.insert(30,50);
	p.insert(60,40);
	p.insert(22,60);
	p.insert(50,20);
	p.insert(77,44);
	p.insert(40,30);
	p.draw(context);
	p.isinplane(47,55, context);
    });
    

Um zu gucken, wieviele Punkte in einem Rechteck liegen, brauche ich glaube ich nur das Intervall der Box zu pruefen. Weil es nicht perfekt ist, fuer Paralellograme, denke ich, es ist einfacher, Vektoren zu nehmen, so kann ich auf jeder Zeile den korrekten Abstand ermitteln, weil ich die korrekte Steigung habe. Für das Polygon gilt das gleiche. Ich rechne zwischen den Punkten noch die Steigung jede Zeile drauf. Und wenn ich mich da noch naehern kann um nicht das ganze Polygon zu vergleichen, sollte ich erstmal die naechsten benachbarten Punkte finden.

Btw, ich hab aus 6.851 bereits Orthogonal Range Search gesehen. Hier prueft man mit vertikalen Strahlen (man projeziert zwei Achsen von dreien jeweils auf eine Ebene und prueft ob unsere Objekt durch die Strahlen, die vom Punkt nach oben laufen gehen. Das ist eine Konstante, die es da zu pruefen gibt. Die Zahl auf der Achse ist konstant, also immer gleich. Das fiel mir schnell auf. Das ganze laesst sich verbessern, geht die Stunde, in dem man ein wenig partitioniert.

Kommentar: Interessanter ist, wenn ich zwei, fast drei Wochen spaeter ein anderes Rechteck und andere Punkte gefunden habe. Dabei geht es um dynamische Optimalitaet von Binaerbaeumen in Lektion 5 und 6 in 6.851. Und ein talk.pdf bei der Suche nach Wilber 2 von dem Professor auf der Seite, da werden diese Node Access Punkte nochmal besprochen. Scheint ein interessantes Ding zu sein. Das zu zeichnen interessiert mich, vielleicht verstehe ich es dann auch (ganz). --


Mai

Habe ich unter Mai archiviert. Ich gedenke, mit den nicht fertig gestellten Aufgaben auch im Juni fortzufahren.

Ausblicke Juli

Was ich mal wieder üben sollte, anstatt JavaScript. C/C++. Das Arbeiten mit Typen, Macros und Templates. Was mir dabei auffaellt, syntax.js parsed die Raute vor dem include weg. Das kann mit auf die Liste.

♯include <iostream> 
♯include <string>
using namespace std;
int main () {
    string source("function main() {}");
    string token("");
    int i = 0;
    do {
	if (source[i] == 0x20) cout << token << endl, token = "";
	else token += source[i];
	i++;
    } while (source[i] != 0x0);
    cout << token << endl;
}

/*
linux-qc69:~ g++ a.cpp
linux-qc69:~ ./a.out

function
main()
{}

*/

Bis die Keywords (function), Identifier (main), ArgumentsList (()), Block/FunctionBody ({}) vermerkt sind, oder die FunctionDeclaration (function main() {}) an sich, ist es noch ein weiter Weg. Aber zu Fuss erreichbar.

Das Schönste ist, alles andere darf ich auch von vorne beginnen, hehe.

#include 
using namespace std;

class ListNode {
public:
    ListNode *prev;
    ListNode *next;
    void *item;
    ListNode (void *item) {
	this->item = item;
    }
    void print () {
	cout << "item: " << (const char *)item << endl;
    }
};

class List {
private:	
    ListNode *list;
public:
    List () {
	this->list = new ListNode(NULL);
	this->list->prev = this->list;
	this->list->next = this->list;
    }
    void insert(void *item) {
	ListNode *l = new ListNode(item);
	l->prev = this->list->prev;
	l->next = this->list;
	this->list->prev->next = l;
	this->list->prev = l;
    } 
    void print () {
	ListNode *l = list;
	while ((l=l->next) != list) {
	    l->print();
	} 
    }
};

int main () {
    List *L = new List;
    L->insert((void *)"hallo");
    L->print();
}

/*
item: hallo
*/

Das hat jetzt fuenf Minuten gedauert, mit dem void* Pointer das geht. Zumindest bis hier. Ich bemerke aber meine Unsicherheit beim Tippen gegenueber JavaScript. Ausserdem ist meine Architektur nicht so gut. Ich denke, hier erstmal die C/C++ Unterlagen aus der OCW Reihe durchzublaettern. Denn meine letzten C++ Referenzen hatte ich vor zehn Jahren mal auswendig (!) gelernt. Letztes Jahr, als ich libuv machen wollte, hatte ich schon geschwaechelt.