[social buttons]

Datenstrukturen und Algorithmen in JavaScript

Sowie Komplexitätsanalyse für Anfänger

JavaScript für Hartz IV Empfänger [die ersten Zeilen]

MDN logo.js

Status: Noch recht dürftig.

Juni: Aufgrund verschiedener Lernerfolge kann ich alles nochmal von vorne schreiben...

Dieses Dokument sollte man nicht mehr ganz so ernst nehmen.

(Auch wenn selbst hier natuerlich und sowieso einige gute Code-Beispiele drin sind.)

Irrtümer zu Beginn vorbehalten.

Das Dokument ist von Februar, Anfang/Mitte Maerz, bis auf das naechste Kapitel, was ich kurz andeute. Ich habe das Dokument aber so auf dem Schirm, dass ich es irgendwann wirklich vollende. Die Sachen sammeln sich weiter.

Designtechniken

Ich schreibe mir schonmal eine Notiz, das genauer zu erlaeutern. Ebenfalls kompakt, aber hier als Kaptiel. Die paar wichtigten Techniken, die ich kennengelernt habe.

Der Kurs

Die Ziele von CS61B sind:

Das Objekt

Lektion 2

Das Objekt ist ein Datencontainer.

In JavaScript ist ein Objekt eine dynamische Sammlung von Key-Value Paaren (*), die zur Laufzeit erzeugt und geändert werden können. Es ist keine Definition einer Klasse notwendig. Man kann dennoch einen Prototypen angeben, dessen Attribute und Methoden geerbt werden, der wiederum eigene Prototypen haben kann.

(*) Intern werden Hash Tables genutzt. Darueber und ueber eine neue Strukturierung meiner Argumentation, wie ein JavaScript Objekt _intern_ gespeichert wird, in einigen Wochen. Wenn ich das kann, mehr von mir. Solange muesst ihr mir glauben, aus .js-Entwicklersicht (kann die internen Details dabei nicht sehen, und habe eine fertige Sprache vor mir).


// Das sind vier Konstruktoren, die nacheinander aufgerufen werden,
// das zuerst erzeugte Objekt (mit D begonnen) wird dem naechsten 
// als Prototyp zugewiesen, was dann zurueckgegeben wird und beim
// naechsten Aufruf als Prototyp dient

    var abcd_obj = 
    [ function A() { this.a = true; },
      function B() { this.b = true; },
      function C() { this.c = true; },
      function D() { this.d = true; }
    ].reduceRight(function (A, B) {
	if (typeof A === "function") {
	    A = new A();
	} 
	if (typeof B === "function") {
	    B.prototype = A;
	    return new B();
	} else {
	    B.__proto__ = A;
	    return B;
	}
    }, {});

In JavaScript kann man Objekte mit einer Konstruktorfunktion und dem new Operator, mit einem Objektliteral als Zuweisung an eine Variable oder als Parameteruebergabe, oder mit der Methode Object.create erzeugen.

function Constructor (name) {
    this.name = name;
}
var edward = new Constructor("Edward");
edward.name;

Constructorfunctions kann man am Grossbuchstaben erkennen, und nur an dem. Oder, wenn man reingucken kann daran, dass der ThisExpression (this) etwas zugewiesen wird. Problematisch war in ES3 der Scope von Funktionen, hatte man das new vergessen, trat "window" an Stelle des this Objekts, was dazu fuehrte, dass man sich unbeabsichtigt globale Variablen erzeugte. In ES5 im "strict mode" wird bei einem normalen Funktionsaufrufen undefined statt "window" eingesetzt, dass sowas nicht passieren kann. Im Falle einer Zuweisung an this-undefined wird ein ReferenceError vom System geworfen.


// Ein Objekt in Literalform einem Identifier zugewiesen, es hat Attribute und Methoden

var obj = { 
    me: "I am an Object as { ObjectLiteral }" ,
    f: function (g) {
	return g(this.me);
    }
};

// Die JSON Notation verlangt hingegenlinks vom Doppelpunkt Anfuehrungszeicehn

var json = {
    "me": "Das Attribut steht in doppelten Anführungszeichen. Und JSON Objekte haben keine Funktionen."
};

Dieses Objekt objobj erbt me und f von obj. Object.create hat als zweiten Parameter eine Propertydescriptormap, womit man die Properties des neuen Objekts mitdefinieren kann, eine Propertydescriptormap fuer je eine Property wird ein Descriptorobjekt uebergeben. Dieses Descriptorobjekt enthaelt Accessor oder Dataproperties mit allen moeglichen Feldern, und ist ein weiteres Objektliteral, was eine genaue Beschreibung der Property enthaelt.

var objobj = Object.create(obj, { "p": { value: "property", enumerable: false, writeable: false, configurable: true } }); objobj.p; // ergibt "property" // Diese Methode der Funktion Object ermittelt den Prototypen eines Objekts. if (Object.getPrototypeOf(objobj) === obj) { console.log("obj ist ein Prototyp von objobj"); } if (objobj.__proto__ === obj) { console.log("Der inofizielle Link zum Prototypen geht über __proto__. Der Bezeichner soll aber nun standardisiert werden. Damit man __proto__ bedenkenlos verwenden kann."); }

Keys eines Objekts werden in der Reihenfolge gespeichert, in der sie erzeugt werden, sie sind also nicht alphabetisch sortiert, oder aehnliches, das muss man spaeter selbst programmieren.

Methoden des Object Konstruktors

Speziell in JavaScript gibt es das Object-Objekt. Dieses Object ist nicht nur der Prototyp jedes Objekts, und hat nicht nur einige Basisfunktionen, wie Object.prototype.hasOwnProperty. Es hat auch ein paar intelligente Funktionen am Konstruktor, wie Object.keys, oder Object.defineProperties.


// Objekt.keys(obj) ermittelt alle Schluessel, alle Bezeichner, in einem Objekts.
// Die .keys() Funktion gibt einen Array zurueck, so dass man hier .map, .forEach, etc. anwenden kann.

var obj = { a: 1, b: 2, c: 3, d: 4, e: function e() { return e; } };
Object.keys(obj).forEach(console.log);

var obj2 = {};
Object.keys(obj).forEach(function (p) {
    obj2[p] = obj[p];
});

Object.keys kann man als folgenden Algorithmus implementieren.

    Object.keys = function (object) {
	var keys = [];
	for (var p in object) {
	    if (object.hasOwnProperty(p)) {
		keys.push(p);
	    }
	}
	return keys;
    };

Object.getOwnPropertyNames ermoeglicht es, auch nicht enumerable Properties aufzuzeigen, die for (var p in object) zum Beispiel nicht anzeigen wird.

Object.getOwnPropertyNames(this);

Damit konnte ich zum Beispiel das global Object untersuchen, als ich das erste mal mit der Spidermonkey API eine eigene Shell startete, und das globale Objekt noch nicht kannte. Wenn man eine eigene Shell startet hat man keine Autovervollständigung und so weiter, die muss man erst probieren. Da ist dieser Befehl sehr nützlich.

    var obj = { a: 1, b: 2 };
    if (obj.hasOwnProperty("a")) {
	"yes";
    }

Mit hasOwnProperty kann man sehen, ob die Property zum Objekt gehoert. for (var p in object) schliesst auch den Prototype mit ein.

Linked Lists I

Lektion 7

I. little knowledge

Vorab, ich muss die Lektion noch machen, ich weiss zwar was Listen sind, und wie viele tausend male sie im Linux Kernel vorkommen, aber ich habe da bereits eine Idee, wo ich Listen mal wieder einsetzen kann:

Die Prototype Kette. (Als einseitige verkettete Liste, da Prototypen ihre Subclass ja nicht kennen (oder?)).

Hier eine vereinfachte Liste (ich hab den Kopf vergessen, von dem z.B. der Loop ausgehen kann, ich will die Lektion erstmal gucken, ok?)

// Den ListenKopf habe ich noch nicht beruecksichtigt. 
// Ich hab den vergessen und kann mich nicht mehr an die Regel erinnern (10 Jahre her)
// Den werde ich ergaenzen, wenn ich die Lektion wiederholt habe
// Die CS61B Lektion habe ich noch _nicht_ geguckt, darum nur das hier
// .item und .next habe ich aus Lektion 8 Stackframes (wo ne Liste auf dem Stack drankommt und .item und .next hat)
    
	function ListNode (item, next) {
	    this.item = item;
	    this.next = next || null;
	}
	
// Die Funktion insertAfter ist kein Standard,
// aber so eine fiel mir jetzt abrupt ein.
	
	ListNode.prototype = {
	    insertAfter: function (place) {
		// speichere next des ortes wo wir einfuegen
		var placedotnext = place.next;
		// setze uns dorthin
		place.next = this;
		// verlinke uns mit dem nachfolge
		this.next = placedotnext;
		// und wir sind in der liste, nach place, 
		// vor dessen altem nachfolger
	    }
	};
	
// Das ist in etwa, was ich noch von Listen behalten habe, was ich vor Jahren
// mal kennengelernt hatte. Haetten meine Eltern mich mal lieber gefoerdert 
// anstatt zu ruinieren.

    
    // Diese schwache Erinnerung an vor 10 Jahren 
    // nun auf die Prototypegeschichte angewandt.
    
    // function inherit(object, proto)
    var proto = { a: "a" };
    var object = { b: "b" };
    var list = new ListNode(object, new ListNode(proto));
    // return list
    
    function getPrototypeOf(o) {
	// Ich denke getPrototypeOf gibt den naechsten Eintrag
	// und daher ist jeder Loop oder aehnliches ueberfluessig
	if (o === object) {
	    // fixcoded fuers beispiel
	    var prototype = list.next;
	    return prototype.item;
	} else {
	    // andere Liste
	}
    }
    
    var proto_ref = getPrototypeOf(object);
    if (proto_ref === proto) console.log("the prototype of object is proto");
    
// Was hier jetzt uebersprungen werden muss ist das Listen und Objekte
// intern zusammen verwaltet werden muessen, ich greife jetzt auf list zu, die
// fixcoded ist, und ich weiss dass list zu object gehoert.

    

Also indirekt schonmal bewiesen: Verkettete Listen lassen sich gut dafuer einsetzen, eine Prototype Chain aufzubauen, jedes Objekt bekommt intern eine dazugehoerige Liste. Was ich mir wiederum fuer meinen Syntaxhighlighter merke, der ja nun eine AST-eval Funktion bekommt. Dafuer muss man wirklich die ganze API der Engine reproduzieren, und so kommt die interne Darstellung der Prototypenreihe natuerlich auch vor.

Den Beweis, dass ich dafuer so eine Liste nehmen werde, trete ich dann spaeter, nach der Lektion und vielen Tagen, wo ich viel zu tun habe, an.

II. now the cs61b lecture. to improve the situation much.

Linked Lists I

Oha, zuerstmal habe ich einen Teil davon vorweggenommen.

Der Listenkopf, den ich oben vergass. Also das ist so, anstelle der ListNode gibt es eine List (SList), die einen Head (die erste Node) und eine size Variable (Anzahl der Nodes in der Liste) hat. Die List hat die Methoden und ueber die Anzahl der Nodes dabei zu wachen (was ja gleich for free ist.) Meine insertAfter Methode kommt dann vom ListNode.prototype zur List.

    
function ListNode (item, next) {
    if (!(this instanceof ListNode)) return new ListNode(item, next);
    this.item = item;
    this.next = next || null;
}
//
    
function SList (head) {
    if (!(this instanceof SList)) return new SList();
    this.head = head || null;
    this.size = 0;
    if (head ? this.count(head) : 0;
}

// Diese Funktionen sind nicht aus CS61B 
// Ich bin gerade wieder abgelenkt gewesen, weil meine Frau nach Hause kam,
// und habe noch den Projektor mit dem SList Konstruktor erblickt
// Da habe ich frei raus das hier kurz geschrieben. Mache spaeter mit dem
// richtigen Inhalt weiter.

SList.prototype.count = function (node) {
    var count = 0;
    if (!node) return this.size;
    else {
	var l = node;
	do {
	    ++count;
	} while (l = l.next);
	return count;
    }
}

SList.prototype.insertItem = function (after, item) {
    var afternext = after.next;
    after.next = node;
    node.next = afternext;
    this.size += 1;
}

SList.prototype.removeItem = function (item) {
    var node = this.head;
    do {
	if (node.next.item === item) {
	    var oldnode = node.next;
	    var node.next = node.next.next;
	    this.size -= 1;
	    return oldnode;
	}
    } while (node = node.next);
}
SList.prototype.removeNode = function (node) {
    var node = this.head;
    do {
	if (node.next === node) {
	    var oldnode = node.next;
	    var node.next = node.next.next;
	    this.size -= 1;
	    return oldnode;
	}
    } while (node = node.next);
}

SList.prototype.removeAfter = function (node) {
    if (node.next) {
	var oldnode = node.next;
	node.next = node.next.next;
	this.size -= 1;
	return oldnode;
    }
}

SList.prototype.findItem = function (item) {
    var index = 0;
    var l = this.head;
    do {
	if (l.item === item) return index;
	else ++index;
    } while (l = l.next);
};
SList.prototype.findNode = function (node) {
    var index = 0;
    var l = this.head;
    do {
	if (l === node) return index;
	else ++index;
    } while (l = l.next);
};
SList.prototoype.findAt = function (index) {
    var l = this.head;
    for (var i=0, j = index; i < j; i++) {
	if (!(l = l.next)) return null;
    }
    return l;
};

// Die letzten drei Funktionen kann man auch zu einer Funktion zusammenfassen.
// Ich rufe jetzt die oberen Funktionen, man kopiert den Code der drei zu einer
// Funktion zusammen und loescht die drei.

SList.prototype.find = function (what) {
    if (what instanceof ListNode) {		// wir suchen einen index per node 
	return this.findNode(what);
    } else if (typeof what === "object") {	// wir suchen einen index per node.item
	return this.findItem(what);    
    } else if (typeof what === "number") {	// wir kregen die node an stelle what
	return this.findAt(what);
    } else {
	return null; 
    }
};

Nochmal umschreiben (neu schreiben):

Dann habe ich abends die Lektion durchgespult, in Lektion II werden die SList Properties private deklariert. Das bedeutet fuer mich, die .prototype Formulierung umzuformen in ein Closure Pattern (wo private Variablen im Konstruktor definiert werden und ich alle Methoden mit this...= im Konstruktor assigne, das ist ein Closure Constructor Pattern). Ausserdem kann ich die Funktionen nochmal zusammenfassen, weil sich die Funktionen mit ListNodes, Indexnummer und Item auskennen lernen sollen.

(fortsetzung mit besserer SList folgt)

[volle, richtige, impl der slist in ein paar stunden oder tagen hier]

Linked Lists II

Lektion 8

WUNDERBAR: Das was ich hier schreibe passt zu ENCAPSULATED LISTS --- ich hatte das wohl schon unterbewusst aufgenommen, dass die richtige Einkapselung der Liste ein Thema der Listenlektionen ist --- Ich werde das Kapitel umbewegen --- Zum anderen kommt hier das Kapitel doubly linked lists sowie der Sentinel (node mit item==null, um Anfang und Ende in eine zirkulaere Liste zu verbinden)

Hier kommen dann die DLists hin

Und die zirkulaere Liste mit der Sentinel DListNode.

Das Encapsulation Kapitel 18 muss ich nochmal halbieren und wieder schreiben, weil ich die Verkapselung besser erklaeren kann. Das kann ich viel genauer und kompakter, dass man es lesen kann.

Ok, hier erstmal die DLists, wenn ich die fertig habe.

Gut, Eddie, hier ist schonmal eine mit Sentinel als head (ist head und tail) statt mit head und tail.

function DList () {
    var size = 0;

    var head = new DListNode(null);

    function DListNode (item) {
	var me = this;
	if (!(me instanceof DListNode)) return new DListNode(item);
	me.item = item;
	me.next = null;
	me.prev = null;
	return Object.seal(me);
    }
    function size_ () {
	return size;
    }
    function nth (i) {
	var sentinel = head;
	var node = head;
	var pos = -1;
	do {
	    ++pos;
	    if (node.next) node = node.next;
	    if (pos === i) return node;
	} while (pos < i && node !== sentinel && node && node.next);
	if (node == sentinel) {
	    return -1; // nur mal gucken
	}
    }
    function insertFront (item) {
	size += 1;
	var node = new DListNode(item);
	var first = head.next;
	if (size > 1) {
	    first.prev = node;
	    node.prev = head;
	    node.next = first;
	    head.next = node;
	} else if (size === 1) {
	    node.prev = head;
	    node.next = head;
	    head.prev = node;
	    head.next = node;
	}
    }
    function insertBack (item) {
    	size += 1;
	var node = new DListNode(item);
	var tail = head.prev;
	if (size > 1) {
	    tail.next = node;
	    node.prev = tail;
	    head.prev = node;
	    node.next = head;
	} else if (size === 1) {
	    node.prev = head;
	    node.next = head;
	    head.prev = node;
	    head.next = node;
	}
    }
    function visit ( visitor ) {
	var node = head;
	var num = 0;
	do {
	    ++num;
	    node = node.next;
	    if (node !== head) {
		if (typeof visitor === "function") {
		    visitor(node, num);
		}
	    }
	} while (node && node !== head);
    }
    function visitReverse ( visitor ) {
	var node = head;
	var num = 0;
	do {
	    ++num;
	    node = node.prev;
	    if (node !== head) {
		if (typeof visitor === "function") {
		    visitor(node, size - num);
		}
	    }
	} while (node && node !== head);
    }    
    var me = this;
    if (!(me instanceof DList)) return new DList();
    me.node = function (item) { return new DListNode(item); };
    me.nth = nth;
    me.insertFront = insertFront;
    me.insertBack = insertBack;
    me.size = size_;
    me.visit = visit;
    me.visitReverse = visitReverse;
    return Object.freeze(me);
}


var dlist = new DList();
dlist.insertFront("schoen");
dlist.insertFront("ist");
dlist.insertFront("Edward");
dlist.insertBack("intelligent");

dlist.visit(function (node, num) {
    console.log(num+": "+node.item);
});
console.log("und rueckwaerts");
dlist.visitReverse(function (node, num) {
    console.log(num+": "+node.item);
});

/*
1: Edward
2: ist
3: schoen
4: intelligent
und rueckwaerts
3: intelligent
2: schoen
1: ist
0: Edward
*/

Das ist eine Zirkulaere Liste, wenn man will. Zur Zeit wird die Referenz des Sentinels verglichen, um zu bestimmen, das Anfang oder Ende der Liste erreicht ist.

Stack Frames

Lektion 9

Immer wenn eine neue Funktion aufgerufen wird, wird ein Stackframe erzeugt.

Der Stack waechst mit jedem Aufruf und schrumpft, wenn die Funktion zurueckkehrt.

Ein Stackframe haelt Pointer zum Heap, wo die Objekte gespeichert werden, die Pointer umfassen Funktionsargumente und das komplette Arguments Objekt, sowie lokale Variablen, sowie ein this Zeiger, der wiederrum auf das Objekt zeigt, dessen Methode gerufen wird.

    function f2() {
	console.log("Auf dem Stack liegen jetzt unten f1() und dann darueber f2()");
    }
    function f1() {
	console.log("Auf dem Stack liegt jetzt f1()");
	f2(); 
    }
    f1(); // Die Engine erzeugt nun einen neuen Stackframe fuer die Funktion f1();
var stack = [];
var frame = {};

function Call(func) {
// save the frame
    stack.push(frame);
// create a new
    frame = new StackFrame();
// do all on this stackframe,
// arguments, localvariables
    /* ..func... */
    frame.arguments = getArguments(func);	// returns an arguments object
    frame.localvars = getLocalVars(func);	// returns an object with pointers to the heap (named by key)
// restore the frame
    frame = stack.pop();
}

Ich sehe, ich muss das Zeichenprogramm starten, um Stack und Heap wie der Professor an der Tafel zu zeichnen.

// Auf dem Heap speichern (pseudocode)
// Weil sich Variablennamen ueberlagern, wenn man nur einen Heap hat,
// der nicht wie der Stack waechst, muss man sich IDs einfallen lassen
// (die SpiderMonkey API hat auch extra IDs fuer JSObject und JSFunction etc.,
// ich vermute mal, das wird sowas sein, pruefen werde ich das im Laufe der Zeit.)

function JSObject() {
    var object = new JSClass(); 
    object.id = storeOnHeap(object);
    // es folgt eine interne Repraesentaion eines Objekts
    object.values = {};
    object.identifiers = {};
    object.types = {};
    object.astnodes = {};
    // Die Struktur zurueckgeben.
    return object;
}

function storeOnHeap (object) {
    var id = Math.random ();
    heap[id] = object;
    return id;
}

// Ich erzeuge ein Objekt
// Intern wird es auf dem Heap gespeichert.
var object = new JSObject();

Die Lektion in CS61B handelt nicht nur vom Stackframe, sondern ist komplett und handelt von Stacks und Heaps. Ich muss die Folge aber mehrmals gucken (bislang ca. 1 1/2 mal nebenbei), um das richtig wiederzugeben. Bei der ersten Notiz hatte ich nur noch den Frame im Kopf, aber den Heap nicht mehr. Als ich die Folge sah, das Dokument aber bereits begonnen hatte, dachte ich "Mist". :-) Den Text habe ich natuerlich geloescht.

Heap (Halde)
Der Heap speichert alle Objekte, Klassen, Variablen an sich
Stack (Keller)
Der Stack speichert lokale Variablen und Parameter.

Der Stack (der Keller) macht Rekursion und unendliche Calltiefe moeglich. In JavaScript nehme ich einen [] als Stack, weil er identische push() und pop() Funktionen bieten, die das LIFO (Last in, first out) Prinzip bieten, das auch der Stack verwendet.

Der Heap (die Halde) speichert die Variablen, Objekte, Arrays, Numbers, Strings, RegularExpressions, Funktionen in ihren entsprechenden Strukturen. [Die Basis-Struktur in JavaScript ist da ja das Objekt, alle sind da ja Objekte, in diesem Fall ist der type JSClass, von dem JSObject, JSFunction, etc. abgeleitet sind, gemeint..Vermute ich fuer SpiderMonkey, wie es in der ECMA Spezifikation aussieht, das muss ich noch lesen und herausfinden.]

Der Stackframe speichert Pointer (Zeiger) auf den Heap, nicht die Objekte, sondern die Referenzen dorthin.

Der Stack waechst mit jedem Funktionsaufruf und schrumpft, wenn die Funktion zurueckkehrt.

-

Garbage Collection fuer den Heap kommt erst in Lektion 38 dran.

Exceptions, die ueber mehrere Stackframes geworfen werden, kommen in Lektion 14 dran.

Testing

Lektion 10

Es gibt in Java eine Methode equals(), die jede Klasse hat. Wenn man keine explizite equals() Methode implementiert, defaultet r1.equals(r2) zum Vergleich, ob die beiden Referenzen r1 und r2 zum gleichen Objekt zeigen (r1 == r2).

Viele Klassen in Java definieren equals(), um den Inhalt von zwei Objekten zu vergleichen. Sie sind dann equal, wenn sie das gleiche enthalten, auch wenn es zwei unterschiedliche Objekte sind.

Das gibt es in JavaScript nicht, aber ich hoffe, mal eine Brücke bauen zu koennen.

[Zeichnung mit s1, s2, ...]

Der Referenztest funktioniert soweit gleich.

	
	    var s1 = new String("yes");
	    var s2 = new String("yes");
		
	    s1 === s2; // false	 - die Referenzen zeigen auf zwei Objekte
	    s1 == s2; // false
	    
	    s1.valueOf() === s2.valueOf(); // true (== auch)
	    
	    var s3 = s2;
	    s3 === s2; // true	- hier zeigen die Referenzen auf das gleiche Objekt
	    
	

Es gibt vier Grade von Gleichheit (equality).

  1. Reference equality; === Beide Seiten vom === zeigen aufs gleiche Objekt
  2. Shallow (flache) structural equality, die Properties (o[p].valueOf()) sind ===
  3. Tiefe strukturelle Gleichheit: Die Properties sind "equals()".
  4. Logische Gleicheit: a) 1/3 und 2/6 sind "equals()". b) Mengen (Set) Objekte sind equals, wenn sie die gleichen Element (auch in unterschiedlicher Ordnung) enthalten.

In JavaScript gibt es == und ===. == wandelt den Typen der rechten Seite in den Typen der linken Seite um und vergleicht. === erwartet auf beiden Seiten den gleichen Typen und den gleichen Wert.

[es folgt eine Implementation von equals() fuer die SListNode]

Testen

  1. Modultests: Test drives & stubs

    a) Test Driver rufen den Code, vergleichen die Ergebnisse, normalerweise in main()

    b) Stubs: Teile des Codes werden vom getesteten Code gerufen i) Stubs sind ein fill-in fuer eine fehlende Methode ii) Herausfinden, ob der Bug in der rufenden Methode, oder der aufgerufenen Methode (callee) liegt. Durch ersetzen des Callees mit einem Stub. iii) ..

Bin noch nicht fertig...Unterbrechung.

Exceptions

Lektion 14

Exceptions werden dann geworfen, wenn das Programm ausser Kontrolle geraten würde, durch falsche Eingabe oder Handhabung. (Sonst nicht!) Der Programmteil, der die Exception auffaengt, zum Beispiel das Hauptprogramm, kann dann entscheiden, ob es den Ausfall ausgleichen kann, oder selbst abbricht, was grundsätzlich der Fall ist, wenn man die Exceptions nicht fängt.

In JavaScript gibt es seit 1999 try/catch/finally. Es gibt anders als in Java nur einen Catch Block, der nur einen Parameter enthaelt, und zwar die entsprechende Exception, die mit dem throw Befehl geworfen wurde.

Anders als return, was nur zur naechsten Funktion auf dem Stack zurueckkehrt, kann man eine Exception ueber alle Stackframes, ueber alle auf Rueckkehr wartenden Funktionen, hinweg werfen.

	function f3() {
	    throw new Error("Catch me if you can");
	}
	
	function f2() {
	    f3();
	}
	
	function f1() {
	    f2();
	}
	
	(function main() {
	    try {
		f1();
	    } catch (ex) {
		ex.stacktrace = (""+ex.stacktrace).split("\n");
		ex.stack = (""+ex.stack).split("\n");
		console.log(JSON.stringify(ex, null, 4))
	    } finally {
		/* finally wird in beiden Faellen ausgefuehrt */
		// AUCH, wenn im catch ein "return" kommt!
	    }
	}());

OFF-TOPIC (dont study):

Weitwurf von rvals (return values)

Mir faellt dabei auf, dass man, da man in JavaScript alles throwen kann,
dass vielleicht auf die Art auch ueber mehrere Frames normale Werte anstatt Fehler "returnen" kann.

    function f17() {
	throw result;
    }

    /* ... f1 - f16 */
    
    var rval;
    try {
	rval = f1()
    } catch (ex) {
	if (!ex instanceof Error) {
	    rval = ex;	// Korrekter Weitwurf
	} else {
	    throw ex; // Absturz
	}
    } finally {
	console.log(rval);
    }

Game Trees

Lektion 16

Hier lernt man, wie man einen Gametree aufstellt, also die Züge vorausberechnet, und sie auswertet, in dem man ihnen Scores gibt. Es gibt da zum Schluss dann sogar vereinfachungen

Grundsatz: Man nimmt an, dass der Gegenspieler perfekt ist, und immer den besten Zug auswaehlt.

Algorithmus: Darum macht das unser Algorithmus auch. Er probiert alle moeglichen Zuege aus, fuer Mensch und Computer.

Game tree (cpu-mensch-cpu-mensch v.o.n.u. je 1 level): In der Baumstruktur ist ein Level der Mensch, der naechste Level der Computer, der naechste Level wieder der Mensch (immer abwechselnd) bis zum Sieg oder zur Niederlage, bewertet die entstandene Struktur, und sucht dann den besten naechsten Zug aus.

1 Baum je moeglicher naechster Zug (top-level): Man wertet nicht nur einen Baum, sondern gleich mehrere Baeume aus, der fuer jeden moeglichen naechsten Zug ein eigener Baum benoetigt wird, um die Folgezuege zu berechnen.

Wahl des besten Zuges: Hat man bereits ein optimales Ergebnis, braucht man die anderen nicht mehr zu berechnen und kann dem Computer damit ein paar ms Kalkulationen einsparen. Wenn man eine klassische Win-Situation im naechsten Zug hat, braucht man nicht erst zu berechnen, was nach den anderen passieren kann und nimmt direkt den siegenden Zug.

Scoring: Zum Auswerten der Baeume geht man von unten nach oben zurueck, guckt, ob man im letzten Zug gewinnt, oder verliert, gibt im Sieg 1, in der Niederlage -1 und bei unentschieden 0 Punkte. Hat man verloren, und noch eine Moeglichkeit, werten man die aus. Hat man gewonnen, braucht man die nicht mehr auswerten und kann mit der zurueckkehren. Wenn die aber nach sagen wir 5 Zuegen erst gewonnen ist, und wir andere Zuege haben, und zum Beispiel nach 3 Zuegen gewinnen koennen, nutzen wir den Zug.

Der Professor erklaert das besser (das war jetzt aus dem Kopf, ich habe die Folge bislang einmal so geguckt) und ich werde das wiederholen um es besser zu schreiben, aber ich hoffe, ihr koennt mir folgen.

Spiel

Dazu wird das Spiel Tic-Tac-Toe gewaehlt. Gluecklicherweise habe ich vor einer Weile mal angefangen, Tic-Tac-Toe zu schreiben. Mehr, um ein CSS Sprite zu testen. Und habe vor der Game Logic aufgehoert. Wahrscheinlich, damit ich hier weitermachen kann, hehe.

Dieses Spiel kann ich nun fortsetzen mit der GameTree Theory, und ich denke, das passt auf diese Seite, oder auf eine extra Seite, je nachdem.

Das Program zum Bearbeiten:

Vorher

tic tac toe - wo man nur abwechselnd x + o klicken kann, aber kein computer spielt und es kein ende und anfang des spiels gibt, irgendeinen Vormittag mal in einer halben Stunde oder so gemacht. Laenger habe ich nie gebraucht..Habe es nur wieder vergessen gehabt, weil ich ja die Dokumente-zu-bearbeiten-Liste voll habe..

Das Spiel muss noch mit der Funktion chooseMove() programmiert werden. Aber dahin wird das fuehren. Dann kann dieses TicTacToe Spiel gegen einen spielen :-)

Nachher

Ich habe ein Spiel hingekriegt. Die Funktion waehleZug(spieler, feld, tiefe) ist eine Variante von chooseMove, der Minimax-Variante aus dem CS61B Kurs. Ob ich den jetzt richtig oder falsch gemacht habe, kann ich nicht beurteilen. Aber ich denke, ein Spiel habe ich hingekriegt. :-)

Die Schwierigkeitsgrade sind durch ausprobieren und spielen entstanden. Weil ich merkte, bei welcher Aenderung was passiert, dachte ich, klammere ich was ein oder aus, je nach Schwierigkeitsgrad.

Spielanleitung: Ins Feld klicken. Wenn alle Felder voll sind, oder wenn das Spiel gewonnen oder verloren ist, erscheint ein Button zum neu starten.

Der Source Code

(function () {
"use strict";

var COMPUTER = false;
var MENSCH = true;
var WIN = 1;
var DRAW = 0;
var LOSS = -1;
var CONTINUE = null;
var LEICHT = 0;
var MITTEL = 1;
var SCHWER = 2;
var container;
var canvas;
var context;
var messages;
var X; 
var O;
var spieler = COMPUTER;
var WERX = COMPUTER; 
var stufe = SCHWER;
var board;
var spielfeld = [];
var zug = 0; 
var kodierteZuege = {
    0:{ x:0, y:0 },
    1:{ x:1, y:0 },
    2:{ x:2, y:0 },
    3:{ x:0, y:1 },
    4:{ x:1, y:1 },
    5:{ x:2, y:1 },
    6:{ x:0, y:2 },
    7:{ x:1, y:2 },
    8:{ x:2, y:2 }
};

var schwierigkeitsGrade = ["leicht", "mittel","schwer"];
var lock = false;
var letzteErgebnisse = [];
var neustartButton;
var stufenButtons;
var wCanvas = 150;
var hCanvas = 150;
var wSpieler = 50;
var hSpieler = 50;

function zeichneSpieler (spieler, spalte, reihe) {
    var x = spalte*wSpieler;
    var y = reihe*hSpieler;
    var index;
    index = (3* (+reihe)) + (+spalte);
    if (spielfeld[index] === null) {
	var element = spieler === WERX ? X.cloneNode(true) : O.cloneNode(true);
	element.style.top = y + "px";
	element.style.left = x + "px";
	board.appendChild(element);
	spielfeld[index] = spieler;
    } else {
	messages.innerHTML += "Feld "+index+" ist belegt!";
	spieler = !spieler;
	--zug; 
    }
};

function testeAufSieg (feld) {
    if (feld[0] === COMPUTER && feld[1] === COMPUTER && feld[2] === COMPUTER) return WIN;
    else if (feld[3] === COMPUTER && feld[4] === COMPUTER && feld[5] === COMPUTER) return WIN;
    else if (feld[6] === COMPUTER && feld[7] === COMPUTER && feld[8] === COMPUTER) return WIN;
    else if (feld[0] === COMPUTER && feld[3] === COMPUTER && feld[6] === COMPUTER) return WIN;
    else if (feld[1] === COMPUTER && feld[4] === COMPUTER && feld[7] === COMPUTER) return WIN;
    else if (feld[2] === COMPUTER && feld[5] === COMPUTER && feld[8] === COMPUTER) return WIN;
    else if (feld[0] === COMPUTER && feld[4] === COMPUTER && feld[8] === COMPUTER) return WIN;    
    else if (feld[2] === COMPUTER && feld[4] === COMPUTER && feld[6] === COMPUTER) return WIN;        
    else if (feld[0] === MENSCH && feld[1] === MENSCH && feld[2] === MENSCH) return LOSS;
    else if (feld[3] === MENSCH && feld[4] === MENSCH && feld[5] === MENSCH) return LOSS;
    else if (feld[6] === MENSCH && feld[7] === MENSCH && feld[8] === MENSCH) return LOSS;
    else if (feld[0] === MENSCH && feld[3] === MENSCH && feld[6] === MENSCH) return LOSS;
    else if (feld[1] === MENSCH && feld[4] === MENSCH && feld[7] === MENSCH) return LOSS;
    else if (feld[2] === MENSCH && feld[5] === MENSCH && feld[8] === MENSCH) return LOSS;
    else if (feld[0] === MENSCH && feld[4] === MENSCH && feld[8] === MENSCH) return LOSS;    
    else if (feld[2] === MENSCH && feld[4] === MENSCH && feld[6] === MENSCH) return LOSS;        
    else {
	for (var i = 0; i < 9; i++) {
	    if (feld[i] === null) return CONTINUE;
	}
	return DRAW;
    }
};

// Der Mensch sucht den niedrigsten Score
// Der Computer sucht den hoechsten Scrore.
function waehleZug (spieler, spielfeld, tiefe) {
    var feld = spielfeld.slice(); 
    var best = { tiefe: 99, punkte: spieler === COMPUTER ? -99 : 99 }, reply, m;
    for (var i = 0, j = 9; i < j; i++) {

        if (feld[i] === null) {
	    if ((tiefe === 1 || tiefe === 2 /* || tiefe === 3 || tiefe === 4 */) && spieler === COMPUTER) {
    		if (Math.floor((Math.random() * 1000) % 10) > 5) continue;
    	    }     	    
	    m = {};
	    m.zug = kodierteZuege[i];
	    m.tiefe = tiefe;
	    
	    if (stufe !== LEICHT) {
	    
	    if (spieler === COMPUTER && zug === tiefe) {
		feld[i] = !spieler;
	        if (testeAufSieg(feld) === LOSS) {
	    	    return m;
		}
	    }
	    
	    }
	    
	    feld[i] = spieler;
	    m.punkte = testeAufSieg(feld);
	    if (m.punkte === CONTINUE) m.punkte = 0; 
	    if ((tiefe === zug && spieler === COMPUTER && m.punkte === WIN) || (tiefe === zug + 1 && spieler === MENSCH && m.punkte === LOSS)) {
		return m;
	    }
	    
	    reply = waehleZug(!spieler, feld, tiefe+1);
	    if (spieler === COMPUTER && tiefe === zug && reply.punkte === LOSS) return reply;
            if (((spieler === COMPUTER) && (reply.punkte > best.punkte || (reply.punkte === best.punkte && reply.tiefe < best.tiefe ) || (stufe === SCHWER && tiefe === zug && m.punkte >= best.punkte) ))
        	|| ((spieler === MENSCH) && (reply.punkte < best.punkte || (reply.punkte === best.punkte && reply.tiefe < best.tiefe ) || (stufe === SCHWER && tiefe === zug && m.punkte >= best.punkte)))) { 
        	best = m;
	    }
        }
    }
    return best;
};


function berechne (e) {
var x, y, spalte, reihe, i, best;
if (!lock && zug < 10) {
    ++zug;
    if (zug > 9) {
	return beendeMitUnentschieden();
    }
    messages.innerHTML = "Zug: "+(zug+1)+", Spieler: "+(spieler === COMPUTER? "Computer":"Mensch")+"<br>\n";
    spieler = !spieler;	
    if (spieler === COMPUTER) {
	best = waehleZug(spieler, spielfeld, zug);
	zeichneSpieler(spieler, best.zug.x, best.zug.y);
    } else if (spieler === MENSCH) {
	    e = e || event;
    	    x = e.offsetX;
	    y = e.offsetY;
	    for (i = 0; i < 3; i++) {
		if (x>=i*wSpieler && x<=(i+1)*wSpieler) {
	        spalte = i;
	    }
	    if (y>=i*hSpieler && y<=(i+1)*hSpieler) {
		reihe = i;
	    }
	}
	zeichneSpieler(spieler, spalte, reihe);
    }
    
    switch (testeAufSieg(spielfeld)) {
    case WIN:
	beendeMitSieg();
	break;
    case LOSS:
	beendeMitNiederlage();
        break;
    case DRAW:	
    	beendeMitUnentschieden();
	break;
    default:
        if (spieler === MENSCH) {	
	    // trigger computer zug
	    lock = true;
	    setTimeout(function () {
		lock = false;
		berechne();
	    }, 200);
	}
    }
} // lock    
};

function beendeMitSieg () {
    messages.innerHTML = "Der Computer gewinnt im "+zug+". Zug!<br>\n";
    erfrageNeuStart();
}

function beendeMitNiederlage () {
    messages.innerHTML = "Der Mensch gewinnt im "+zug+". Zug!<br>\n";
    erfrageNeuStart();
}

function beendeMitUnentschieden () {
    messages.innerHTML = "Das Spiel endet unentschieden.<br>\n";
    erfrageNeuStart();
}

function erfrageNeuStart () {
    var button;
    if (!stufenButtons) {
	stufenButtons = document.createElement("div");
	stufenButtons.className = "tictactoe-stufe";
	for (var i=0, j=3; i < j; i++) {
	    button = document.createElement("button");
	    button.className = "tictactoe-stufe-button";
	    button.innerHTML = schwierigkeitsGrade[i];
	    button.onclick = (function (neueStufe) {
		return function (e) {
		    stufe = neueStufe;
		    stufenButtons.parentNode.removeChild(stufenButtons);
		    neuesSpielFeld();
		};
	    }(i));
	    stufenButtons.appendChild(button);
	}
    }
    if (!neustartButton) {
	neustartButton = document.createElement("button");
	neustartButton.className = "tictactoe-neustart-button";
	neustartButton.innerHTML = "Das Spiel neu starten";
	neustartButton.onclick = function () {
	    neustartButton.parentNode.removeChild(neustartButton);
	    neuesSpielFeld();
	};
    }
    messages.appendChild(neustartButton);
    messages.appendChild(stufenButtons);	
}

function zeichneGitter (context) {
    var i, g;
    for (i = 1; i < 3; i++) {
	context.save();
	context.moveTo(wSpieler*i, 0);
	context.lineTo(wSpieler*i, hCanvas);
	context.stroke();
	context.restore();
    }
    for (i = 1; i < 3; i++) {
	context.save();
	context.moveTo(0, hSpieler*i);
	context.lineTo(wCanvas, wSpieler*i);
	context.stroke();
	context.restore();
    }    
};

function ersteWorte (spieler) {
	messages.innerHTML = WERX === COMPUTER ? "X: Computer. O: Mensch.<br>\n" : "X: Mensch, O: Computer.<br>\n" + "Stufe: "+schwierigkeitsGrade[stufe] + "<br>\n";
}

function neuesSpielFeld () {
    board.innerHTML = "";
    zug = 0;
    spielfeld = [
	null, null, null,
	null, null, null,
	null, null, null
    ];
    if (Math.floor((Math.random() * 16) % 2) === 1) {
	spieler = COMPUTER; 
	WERX = MENSCH;
	ersteWorte(!spieler);
    } else {
	spieler = MENSCH;
	WERX = COMPUTER;
	ersteWorte(!spieler);
	lock = true;
	setTimeout(function () {
	    lock = false;
	    berechne();
	}, 200);
    }
};

function init () {
    container = document.querySelector(".tictactoe");
    messages = document.createElement("div");
    messages.className = "tictactoe-messages";
    canvas = document.createElement("canvas");
    canvas.className = "tictactoe-canvas";
    canvas.width = wCanvas;
    canvas.height = hCanvas;
    canvas.className = "background";
    canvas.onclick = function (e) {
	berechne(e);
    };
    context = canvas.getContext("2d");
    zeichneGitter(context);
    container.appendChild(canvas);
    board = document.createElement("div");
    board.className = "foreground";
    container.appendChild(board);
    container.appendChild(messages);
    O = document.createElement("div");
    O.className = "sprite o figur";
    X = document.createElement("div");
    X.className = "sprite x figur";
    neuesSpielFeld();
};

window.addEventListener("DOMContentLoaded", function (e) { init(e); }, false);

}());

Lektion 17

Encapsulated Lists

Lektion 18

Der folgende Text ist von Kapitel Linked Lists II hierhin bewegt worden. Ich habe eins der Kapitel mit den Listen verwechselt, oder das Thema aufgegriffen, weil das in II schon angesprochen wurde --- der folgende Text handelt von der Einkapselung. Ist aber noch nicht fertig. Dennoch beschreibe ich hier, wie man das Closure Pattern einsetzt, um eingekapselte Listen mit privaten (integren) Properties zu ermoeglichen...Das Prinzip wird im momentanen Dokumen in "Binaere Suchbaeume" fuer BinaryTree und BinaryNode angewandt, so kapselt man in JavaScript richtig ein.

--- Das ist jetzt alles bis zum Ende des Kapitels das, was ich in Linked Lists II geschrieben hatte, was nicht das eigentliche Thema davon ist, das sind DLists und Sentinels, das hier ist aber passend fuer das Interface Quality Thema in Kapitel 18.

In Lektion II zu Linked Lists werden zum einen die ListNode und SList Properties (aehm, Attribute im Java-Conventional-Slang) private deklariert.

RICHTIG: Das bedeutet in JavaScript Umformung in ein Closure-Constructor-Pattern, wo man in der function SList () { var size = 0; } die privaten Variablen deklariert und die Methoden mit this.getSize = function () { return size; } in die Closure schreibt und nicht auf den Prototypen.

	function SList () {
	    if (!this instanceof SList) return new SList();
	    var head;
	    var size;
	    this.getHead = function getHead () {
		return head;	// beachte: kein this, private ist in js mit local vars zu regeln.
	    }
	    this.getSize = function getSize () {
		return size;
	    }
	}
	
	// Das beste Pattern fuer private Variablen,
	// wenn man mehr als eine  Objektinstanz haben will (ab genau 2 bis n).
    

Die andere Methode, einen Prototype zu nutzen, ist ein "Module Pattern" zu benutzen und die private Variablen in die var SList = (function () { var size, head; function SList () {...} SList.prototpe = { /* use head, size, etc. */ }; return SList; }()); zu schreiben und SList und SList.prototype innerhalb des Module Patterns zu definieren. (Das Module Pattern gilt in ES6 als Grundlage fuer eine Class-Declaration. Intern wird das in ein Module Pattern mit internem Constructor und Prototype verwandelt und nur die Referenze zum Constructor an var SList zugewiesen. PROBLEM: Die selbstausfuehrende Funktion verschwindet zwar, die Variablen werden private, aber jede SList greift auf die gleichen size und head Variablen zu

Loesung Wenn man mit dem (function () {}()); Pattern arbeiten will, muss man dafuer sorgen, dass diese Closure jedesmal neu erzeugt wird. Das geschieht dadurch, dass man sie in eine Funktion steckt, die jedesmal eine neue Erzeugung bewirkt.

Anstatt...

	var SList = (function () {
	    var head, size;
	    
	    function SList () {
	    }
	    return SList;
	}());
	
	var l1 = new SList();	// benutzt head und size.
	var l2 = new SList();	// benutzt den gleichen head und die gleiche size.
	
	// fuegt man jetzt in l1 ein Element ein,
	// is bei l2 size auch == 1. Darum geht das nicht so (in JavaScript speziell).
    

...muss man das so machen...

    function SList () {

	var SList = (function () {
	
	    var size, head;
	
	    function count (node) {
		var l = node, num;
		do {
		    ++num;
		} (while l = l.next);
		return num;
	    }
	
	    function SList (head) {
		size = 0;
		head = head || null;
		if (head) head = count(head);
	    }
	    SList.prototype.getHead = function () {
		return head;
	    };
	    
	    SList.prototype.getSize = function () {
		return size;
	    };	    
	    
	    // ...
	    
	}());

	return new SList();
    }	
    

In diesem Fall wird, wenn man new SList; (oder SList(); ruft, erst eine neue Closure um head und size und die Memberfunktionen erzeugt. Dann wird der neue Constructor zurueckgegeben, den wir in der ausseren Funktion dann rufen, um das neue ListenObjekt zurueckzugeben. O.K.

(Ich denke mal, der Mechanismus wird auch beim neuen Class Pattern angewandt, aber in optimierter Form.

Kommen wir zum zweiten Teil, Doubly Linked Lists.

Wie man an einseitigen Listen sofort feststellen kann ist es einfach, was nach einer node einzufuegen, aber schwierig wird es, wenn man es umgekehrt machen will.

Man muss die Liste dann von vorne an bis zu der Node durchgehen, an deren Stelle man was einfuegen will. Das geschieht in linearer Zeit.

Aufwand = Vom head aus n nodes vorwaerts gehen, bis man die nth node erreicht hat, oder wenn man irgendwo mittendrin anfangen kann, von dort bis zu dem Punkt, wo man einfuegen will.

Doppelt verkettete Listen machen es einfacher, zum Beispiel das Element 5,000,000 einzufuegen. Sie haben anstelle eines Kopfes auch einen Fuss (oder Tail oder Schwanz).

    function DList () {
    
	// Erzeuge jedesmal neue Closure (weil die Variablen sonst geshared werden)    
	
	// return new (function () {	// kann jetzt wegfallen;
	
	    var size = 0;
	    var head = null;	// Pointer auf das erste Element der Liste
	    var tail = null; 	// Pointer auf das letzte Element der Liste
	    
	    function count () {
		// wie oben...
	    }
	    function DList() {
		// ..
	    }
	    
	    DList.prototoype.getSize = function () {
		return size;
	    }
	
	//    return DList; // <-- return "new DList" und entferne die (IIFE());
	
	
	// }());	// <--- kann jetzt wegfallen (!!!)

	return new DList; // function DList kann damit sogar ohne new gerufen werden :-)

    }	
    
// Erzeugt erstmal eine neue DList (innen), gibt die an Funktion DList (aussen),
// aus der wir eine new DList (die von innen rausgegeben wird) returnen
    

Weil ich das etwas unschoen finde, werde ich in Zukunft das Closure Constructor Pattern nutzen und damit auch DList und SList fertig schreiben. Das ist das Pattern:

    function DList () {
	var dList;
	var size, head, tail;
	if (!(this instanceof DList)) {
	    dList = new DList();
	} else {
	    dList = this;
	    dList.getSize = function () {
		return size;
	    };
	    dList.getHead = function () {
		return head;
	    };
	    dList.getTail = function () {
		return tail;
	    };
	}
	return dList;
    }

// In der IIFE    
// Ein Prototype ist nicht mehr noetig, insofern man fuer head, tail oder size functions will.
// weil der nun immer neu erzeugt wird (was wiederrum noetig ist)
// Wenn man ihn ebenfalls in die Klammer bewegt, kann man ihn auch weglassen und auf
// das __proto__ verzichten, es macht das Objekt nicht besser, wenn man ihn nutzt.

Wie gesagt, Nachteil dieses Patterns: Der Prototype faellt weg, was aber keiner ist, denn der Prototype muesste eh jedesmal neu erzeugt werden, so kann man ihn auch direkt in das Closure Pattern integrieren. Bei Privaten Variablen kommt man in JavaScript um diese "Extra-Kosten" nicht herum, was aber kein Problem sein sollte.

Jetzt habe ich viel zu private variables in JavaScript geschrieben.

Nun die Implementation der DList, um die Lektion abzuschliessen.

[hier]

Muss das nochmal gucken, damit ich formal auch die richtigen Funktionen nehme und keine neuen (fast gleichen) erfinde..

Aus Lektion I und II: Vor- und Nachteile gegenueber Array-Lists:

Arrays haben eine bestimmte Laenge. Wenn man in einen Array was einfuegen will, muss man alle Elemente einzeln einen weiter versetzen.

In einer Liste muss man nur den Pointer veraendern. Ausserdem ist die Groesse unbegrenzt.

(Das sind noch nicht alle, ich muss mir das einmal ganz angucken, um die wiederzugeben.)

Vorübergehend:


// SListNode
// Eine Node in der SList
function SListNode (item, next) {
    if (!(this instanceof SListNode)) {
	return new SListNode(item, next);
    }
    this.item = item || null;
    this.next = next || null;
}
SListNode.prototype.insertAfter = function (item) {
    this.next = new SListNode(item, this.next);
}


// SList
// Eine Singly Linked List
function SList (head) {
    this.head = head || new SListNode();
    this.size = this.countSize();
}

SList.prototype.countSize = function (node) {
    var size = 0;
    node = node || this.head;
    do {
	if (node) ++size;
    } while (node = node.next);
    return size;
}

SList.prototype.insertAt = function (pos, item, node) { // O(pos+1)
    var at = -1;
    node = node || this.head;
    do {
	++at;
	if (at === pos) { 
	    node.insertAfter(item);
	    this.size += 1;
	    break;
	} 
    } while (node = node.next && at < pos);	
}

SList.prototype.visitAll = function (visitor, node) { // O(n)
    var pos = -1;
    if (typeof visitor === "function") {
	node = node || this.head;
	do {
	    ++pos;
	    visitor(node.item, pos);
	} while (node = node.next);
    }
    return pos;
};


/* Linked Lists II */

// DListNode
// Eine Node in der DList mit prev pointer
function DListNode (item, next, prev) {
    if (!(this instanceof DListNode)) {
	return new DListNode(item, next, prev);
    }
    this.item = item || null;
    this.next = next || null;
    this.prev = prev || null; 
}
DListNode.prototype.insertAfter = function (item) {
    this.next = new DListNode(item, this.next, this);
}
DListNode.prototype.insertBefore = function (item) {
    if (this.prev)
	this.prev.insertAfter(item);
    else 
	this.prev = new DListNode(item, this, this.prev);
}

// DList
// Eine Doubly Linked List mit head und tail
function DList (head, tail) {
    this.head = head || new DListNode();
    if (head) {
	this.tail = tail || this.findTail()
    } else {
	this.tail = tail || this.head;
    }
    this.size = this.countSize();
}
DList.prototype = SList.prototype;
DList.prototype.visitReverse = function (visitor, node) {
    var pos = this.size;
    if (typeof visitor === "function") {
	node = node || this.tail;
	do {
	    --pos;
	    visitor(node.item, pos);
	} while (node = node.prev);
    }
    return pos;
}
DList.prototype.findTail = function (node) {
    node = node || this.head;
    do {
	if (node.next === null) {
	    this.tail = node;
	    return node;
	}
    } while (node = node.next)
}

lists-prg.js - hier probiere ich das aus.


// require("./lists").*
exports.SListNode = SListNode;
exports.DListNode = DListNode;
exports.SList = SList;
exports.DList = DList;
exports.CList = CList;var L = require("./lists");
var SList = L.SList;
var DList = L.DList;
var CList = L.CList;
var SListNode = L.SListNode;
var DListNode = L.DListNode;

/* SLists */

// Manuell erzeugte Nodes
var l1 = new SListNode("Eddie");
var l2 = new SListNode("Ede");
var l3 = new SListNode("Edward");
// Manuell verlinkt (public next ptr)
l1.next = l2;
l2.next = l3;
l3.next = null;
// Eine Liste mit l1 als head erzeugt.
var slist = new SList(l1);

function loggingVisitor (item, num) {
    console.log("item #"+num+": "+item);
}

// ausgabe 1
console.log("---");
slist.visitAll(loggingVisitor);

// ausgabe 2
console.log("---");
// l2.insertAfter fuegt eine neue node nach l2 ein und verlinkt den alten next pointer dahinter
l2.insertAfter("Einschub");
slist.visitAll(loggingVisitor);


/*
---
item #0: Eddie
item #1: Ede
item #2: Edward
---
item #0: Eddie
item #1: Ede
item #2: Einschub
item #3: Edward
*/


/* DLists */

var d1 = new DListNode("Edward");
d1.insertAfter("ist");
var d2 = d1.next;
d2.insertAfter("ein toller Kerl");
var d3 = d2.next;
var dlist = new DList(d1);

console.log("---");
dlist.visitAll(loggingVisitor);
console.log("---");
dlist.visitReverse(loggingVisitor);
console.log("---");

d3.insertBefore("schon lange");
dlist.visitAll(loggingVisitor);


/*
---
item #0: Edward
item #1: ist
item #2: ein toller Kerl
---
item #2: ein toller Kerl
item #1: ist
item #0: Edward
---
item #0: Edward
item #1: ist
item #2: schon lange
item #3: ein toller Kerl
*/

Die Listen habe ich direkt am ersten Tag geschrieben gehabt und sind mittlerweile neu zu schreiben.

Asymptotische Analyse

Lektion 19

T(n), die Arbeit, die eine Funktion zu tun hat.

Abbildung f(x) => x oder auch O(1) konstant.

Asymptotische Anylse.

Eine Methode um Funktionen zu messen.

Der Professor faengt an mit einem Beispiel, ein Inventory, was 10,000ms braucht um von Disk zu lesen, und dann 10ms pro Transaktion braucht. Für n Transaktionen braucht man (10,000 +10n)ms. Wenn n nun eine grosse Zahl ist, ist sie natuerlich wichtiger als die 10,000. Je groesser sie wird, um so wichtiger ist sie. Jetzt sucht man nach einer formalen Methode, um das auszuwiegen. Und dafuer ist die asymptotische Analyse da.

Big-oh Notation. Ist dazu gedacht, um die Obergrenze einer Funktion zu bestimmen. Und sie ist dabei eine genaue und keine ungefaehre Notation.

In der Big-oh Notation ist n die Anzahl der Eingabe (number of input).

Dann gibt es eine Funktion T(n), eine richtige Funktion, T ist die Arbeit auf n Elementen, die sie verrichtet.

Die versucht man nun auf eine vernuenftige Abstraktion zu bringen, und alles, was man wirklich nicht braucht, zusammenzufassen.

Dann gibt es f(n), eine andere Funktion. Moeglichst simpel. Die braucht man zum Vergleich.

Jetzt sagt man zum Beispiel T(n) ∈ O(f(n)) wenn und nur wenn T(n)&LessEqual;cf(n) wenn n gross genug fuer eine grosse Konstante c ist. Gross ist hierbei so gross, dass T(n) unter f(n) passt. Wie gross muss c sein? Ebenso, dass T(n) unter f(n) passt.

[[image]: Hier jetzt das Koordinatensystem, mit dem 10,000ms + 10ms Beispiel. Beispiel c = 20 (ueberholt, d.h. braucht laenger, ab n=1000,20000)]

In dem Beispiel ist c = 20; O(n) = return c * T(n).

Die Konstante findet man durch ausprobieren. Man setzt ein und zeichnet zum Beispiel den Graphen und guckt, ob die Konstante ausreicht. Sobald f(n) die Kurve von T(n) einholt, ist es gelungen. Das ist zum Beispiel eine Moeglichkeit, zu gucken.

Bei dem Beispiel kommt raus, das "FüR alle n ⩾ 1000 T(n) ⩽ c*f(n), darum T(n) ∈ O(f(n)) gegen Unendlich".

Big-oh (O von) Formale Definition

O(f(n)) ist die Menge ALLER Funktionen T(n) für die gilt, "es existieren positive Konstanten c und N in der Art, für alle n ⩾ N, T(n) ⩽ c*f(n)."

Omega Ω (best-case)

Omega ist die Untergrenze einer Funktion. Sie ist formal genau das Gegenteil von O.

O(f(n)) ist die Menge alle Funktionen T(n) für die gilt, "es existieren positive Konstanten c und N in der Art, für alle n ⩽ N, T(n) ⩾ c*f(n)."

Also genau umgekehrt.

f(n) selbst liegt im Koordinatensystem genau zwischen O(f(n)) und Ω(f(n))

Theta Θ (beides)

Θ(f(n)) ist die Menge aller Funktionen, die sowohl in O(f(n)) als auch in Ω(f(n)) sind.

Analyse von Algorithmen

Lektion 20

Geht gleich weiter mit O, Ω und Θ

Lektion 21

Hash Tables

Hashing ist einfach. Man berechnet aus einem Wort eine Zahl zwischen 0 und N. N ist die Anzahl der Buckets (Felder). Dort wird gespeichert. Es gibt verschiedene Algorithmen, die Zahl kleiner zu machen. Und Algorithmen um einen weiteren Slot zu nehmen, wenn ein Bucket (Slot) belegt ist. In diesem Beispiel ist die HashCode Funktion hashCode und die Compressionfunktion h.


/* Hat bereits eine Compression Function mit Trial Count. Geht aber noch 
weiter als das ausgeben des loadfactors() oder allocaten eines new Array(2N). */

function Hash (N) {
    var me, hashTable, n;
    
    function Item (k, v) {
	return {
	    __proto__: Item.prototype,
	    constructor: Item,
	    key: k,
	    value: v
	};
    }
    
    function num () {
	return n;
    }
    function loadfactor () {
	return (n / N).toFixed(2);
    }
    function resize (toN) {
	var oldTable = hashTable;
	hashTable = new Array(toN);
	for (var i = 0, j = oldTable.length; i < j; i++) {
	    me.insert(oldTable[i]);
	}
    }
    
    function insert (w, d) {
	var trial = 0;
	var code;
	var entry = w instanceof Item ? w : Item(w,d);
	while (1) {
	    code = h(hashCode(w), trial);
	    if (!hashTable[code]) {
		hashTable[code] = entry;
	        ++n;
		return true;
	    } else {
		trial += 1;
	    }
	} 
	return false;
    }
    
    function find (w) {
	var trial = 0;
	while (entry = hashTable[h(hashCode(w), trial)]) {
	    if (entry.key === w) {
		return entry;
	    } else {
		trial += 1;
	    }
	}
	return null;
    }
    
    function remove (w) {
	// while not found keep going
	var trial = 0;
    	var code; 
    	while (entry = hashTable[code=h(hashCode(w), trial)]) {
	    if (entry.key === w) { 
		hashTable[code] = null;
    	        --n;
    		return true;
    	    } else {
    		trial += 1;
    	    }
    	}
	return false;
    }
    
    function hashCode (word) {
	return 26 * (word.charCodeAt(0) - ("a").charCodeAt(0)) + (word.charCodeAt(1) - ("a").charCodeAt(0));
    }

    function h (hashCode, trial) {
	trial = trial || 0;
	return (hashCode + trial) % N;
    }
    
    
    me = this;
    if (!(me instanceof Hash)) return new Hash(N);
    hashTable = new Array(N);
    n = 0;
    me.insert = insert;
    me.find = find;
    me.remove = remove;
    me.hashCode = hashCode;
    me.h = h;
    me.loadfactor = loadfactor;
    me.num = num;
    return Object.freeze(me);
}

var dict = new Hash(255);
dict.insert("aa", "Das sind zwei A");
console.log(dict.find("aa"));
dict.insert("cc", "Das sind zwei C");
console.log(dict.find("cc"));
console.log(dict.find("aa"));
dict.insert("hash", "Es werden nur die ersten zwei Character benutzt.");
console.log(dict.find("hash"));
dict.insert("array", "Kollisionen sind vorprogrammiert.");
var l = "lec";
dict.insert(l, "Das ist die Code Folie aus der Stunde.");
console.log(dict.find("aa"));
console.log(dict.find("array"));
console.log(dict.find("lec"));
console.log(l+" hashCode = "+dict.hashCode(l));
console.log(l+" compressed = "+dict.h(dict.hashCode(l)));
dict.remove("array");
console.log(dict.find("array"));
console.log(dict.num()+ "items = " +dict.loadfactor()+ " of N (255)");
/*
{ constructor: [Function: Item],
  key: 'aa',
  value: 'Das sind zwei A' }
{ constructor: [Function: Item],
  key: 'cc',
  value: 'Das sind zwei C' }
{ constructor: [Function: Item],
  key: 'aa',
  value: 'Das sind zwei A' }
{ constructor: [Function: Item],
  key: 'hash',
  value: 'Es werden nur die ersten zwei Character benutzt.' }
{ constructor: [Function: Item],
  key: 'aa',
  value: 'Das sind zwei A' }
{ constructor: [Function: Item],
  key: 'array',
  value: 'Kollisionen sind vorprogrammiert.' }
{ constructor: [Function: Item],
  key: 'lec',
  value: 'Das ist die Code Folie aus der Stunde.' }
lec hashCode = 290
lec compressed = 35
null
4items = 0.02 of N (255)
*/

In CS61B gibt es eine Code Folie, in der ein Dictionary gezeigt wird. Eine der sinnvollen der tausend Hashanwendungen. Ich habe das aus Interesse mal nach JavaScript übertragen. Wie das fortgesetzt aussieht, konnte man im Beispiel hiervor bereits lesen.

/* Version 0, praktisch die Code Folie */

function Word (word) {
    var LETTERS = 26, WORDS = LETTERS * LETTERS;
    function hashCode () {
	return LETTERS * (word.charCodeAt(0) - ("a").charCodeAt(0)) + (word.charCodeAt(1) - ("a").charCodeAt(0));
    }
    function value () {
	return word;
    }
    var me = this;
    if (!(me instanceof Word)) return new Word(word);
    me.hashCode = hashCode;
    me.value = value;
    return Object.freeze(me);
}

function Definition (definition) {
    function value () {
	return definition;
    }
    var me = this;
    if (!(me instanceof Definition)) return new Definition(word);
    me.value = value;
    return Object.freeze(me);
}

function Dictionary (n, N) {

    function insert (w, d) {
	if (!(w instanceof Word)) w = new Word(w);
	if (!(d instanceof Definition)) d = new Definition(d);
	defTable[h(w.hashCode())] = d;
    }
    
    function find (w) {
	if (!(w instanceof Word)) w = new Word(w);
	var d = defTable[h(w.hashCode())]
	return  d && d.value();
    }
    
    function remove (w) {
    }
    
    function h (hashCode) {
	return hashCode % N;
    }
    
    var defTable = [];
    var me = this;
    me.insert = insert;
    me.find = find;
    me.remove = remove;
    me.h = h;
    if (!(me instanceof Dictionary)) return new Dictionary();
    return Object.freeze(me);
}

var dict = new Dictionary(20, 255);
dict.insert("aa", "Das sind zwei A");
console.log(dict.find("aa"));
dict.insert("cc", "Das sind zwei C");
console.log(dict.find("cc"));
console.log(dict.find("aa"));
dict.insert("hash", "Es werden nur die ersten zwei Character benutzt.");
console.log(dict.find("hash"));
dict.insert("array", "Kollisionen sind vorprogrammiert.");
var l = new Word("lec");
dict.insert(l, "Das ist die Code Folie aus der Stunde.");
console.log(dict.find("aa"));
console.log(dict.find("array"));
console.log(dict.find("lec"));
console.log(l.value()+" hashCode = "+l.hashCode());
console.log(l.value()+" compressed = "+dict.h(l.hashCode()));
/*
Das sind zwei A
Das sind zwei C
Das sind zwei A
Es werden nur die ersten zwei Character benutzt.
Das sind zwei A
Kollisionen sind vorprogrammiert.
Das ist die Code Folie aus der Stunde.
lec hashCode = 290
lec compressed = 35
*/

Hier ist das Dictionary schonmal aufbereitet, dass man es ausarbeiten kann. Ich habe Wort und Definition entfernt. In JavaScript lohnt sich das nicht unbedingt. In Bedenken an die anderen Datenstrukturen sei eine Node zum einsetzen in einen Bucket aber bestimmt eine gute Idee, wenn es ein {} Objekt ist.

function Hash (N) {

    var me, hashTable, num;
    
    function insert (w, d) {
	++num;
	var i = h(hashCode(w));
	if (!hashTable[i]) {
	    hashTable[i] = d;
	    return true;
	}
	return false;
    }
    
    function find (w) {
	return hashTable[h(hashCode(w))] || null;
    }
    
    function remove (w) {
    	var i = h(hashCode(w));
    	if (hashTable[i]) { 
    	    --num;
    	    hashTable[i] = null;
    	    return true;
    	}
	return false;
    }

    function hashCode (word) {
	return 26 * (word.charCodeAt(0) - ("a").charCodeAt(0)) + (word.charCodeAt(1) - ("a").charCodeAt(0));
    }
    
    function h (hashCode) {
	return hashCode % N;
    }
    
    me = this;
    if (!(me instanceof Hash)) return new Hash(N);
    hashTable = Array(N);
    num = 0;
    me.insert = insert;
    me.find = find;
    me.remove = remove;
    me.hashCode = hashCode;
    me.h = h;
    return Object.freeze(me);
}

var dict = new Hash(255);
dict.insert("aa", "Das sind zwei A");
console.log(dict.find("aa"));
dict.insert("cc", "Das sind zwei C");
console.log(dict.find("cc"));
console.log(dict.find("aa"));
dict.insert("hash", "Es werden nur die ersten zwei Character benutzt.");
console.log(dict.find("hash"));
dict.insert("array", "Kollisionen sind vorprogrammiert.");
var l = "lec";
dict.insert(l, "Das ist die Code Folie aus der Stunde.");
console.log(dict.find("aa"));
console.log(dict.find("array"));
console.log(dict.find("lec"));
console.log(l+" hashCode = "+dict.hashCode(l));
console.log(l+" compressed = "+dict.h(dict.hashCode(l)));
dict.remove("array");
console.log(dict.find("array"));
/*
Das sind zwei A
Das sind zwei C
Das sind zwei A
Es werden nur die ersten zwei Character benutzt.
Das sind zwei A
Kollisionen sind vorprogrammiert.
Das ist die Code Folie aus der Stunde.
lec hashCode = 290
lec compressed = 35
null
*/

Den Inhalt der Lektion dann spaeter.

Rolling Hash

In 6.006 gibt es noch einen Karp-Rabin Algorithmus, der O(s + n + #matches) kosten soll, anstelle von O(s * n), wie ein String-auf-String Vergleich. Hier wird nur der HashCode eines Ausschnittes des Textes genommen und mit dem HashCode des Suchstrings verglichen. (Wegen Kollisionen muss man dann noch +match, den match vergleichen, ob es auch der String ist.)

function RollingHash (input) {

    var me = this;
    var frame, hashcode = null, framesize = 0;
    var search, searchcode = null;
    var pos = 0;
    

    function h (c) {
	var i = 0;
	var hashval = 0; 
	while (i < c.length) {
	    hashval += (c.charCodeAt(i) - ("a").charCodeAt(0));
	    ++i;
	}
	return 26* hashval; 
    }

    
    function skip () {
	var c = frame[0];
	frame = frame.slice(1);
	framecode = +framecode - h(c);
    }

    function append (c) {
	frame += c;
	framecode = +framecode +h(c);
    }
    
    function nextchar() {
	if (pos < input.length-1) {
	    ++pos;
	    skip();
	    append(input[pos]);
	    return true;
	}
	return null;
    }

    function compare (s) {
	if (s===undefined) return s;
	search = s;
	searchcode = h(search);
	framesize = search.length;
	frame = input.substr(0, framesize);
	framecode = h(frame);
	pos = framesize-1;
	do {
	    if (searchcode === framecode) {	// hashCode matcht, kann Kollision sein
		console.log("Found "+s+" at pos: "+pos);
		if (input.substr(pos-framesize+1, framesize) === search) { // Unkodiert auch ?
		    console.log("Test bestanden");
		    return pos;
		}
	    } 
	} while (nextchar());
	return null;
    }
    
    if (me instanceof RollingHash === false) return new RollingHash(input);
    hashcode = h(input);
    Object.defineProperty(me, "hashCode", {
	    get: function () {
		return hashcode;
	    }    
    });
    me.search = compare;
    return me;
}

var rs = new RollingHash("In diesem Text versuche ich jetzt was zu finden");

console.log(rs.hashCode); // der gesamte string
console.log(rs.search("geht nicht"));
console.log(rs.search("find"));
console.log(rs.search("versuch"));

/*
-3432
Found geht nicht at pos: 26 // <-- Kollision (nur 1. Test bestanden)
null
Found find at pos: 44	// 1. + 2. Test bestanden
Test bestanden
44
Found versuch at pos: 21	// 1. + 2. Test bestanden
Test bestanden
21
*/

Der Code ist noch nicht optimiert. Und ich habe die search Funktion nun explizit zur Datenstruktur hinzugefuegt. Was die Struktur sonst hat, zu skip() und append() eine aktuelle hashvalue. Man koennte den String also nur durch skip() und append() in O(1)+O(1) durchjagen und .hashCode jedesmal lesen. Und einen Suchstring oder wofuer man den HashCode braucht ebenfalls einzeln beschreiben. In meinem Fall ist es aber eine Zusammenfassung, entstanden aus der Erinnerung, die ich am naechsten Tag von der Lektion hatte.

Lektion 22

Stacks and Queues

Hier ist schonmal der Source Code für meinen Stack. Er macht in der Lektion glaube ich mit den Hash Tables weiter, kommt kurz zum Stack und ueberspringt die Queues. Code für Warteschlangen kann ich allein durch Nennung der Regel FIFO (Stack ist LIFO) aber schonmal vorwegnehmen, und ob sie einendig oder zweiendig sind. So ist auch die Liste dann.

function StackNode (item) {
    "use strict";
    function item_ () {
	return item;
    }
    var me = this;
    if (!(this instanceof StackNode)) return new StackNode(item);
    me.item = item_;
    return me;
}
function Stack () {
    "use strict";
    var top = null;
    var size = 0;
    function top_ () {
	return top && top.item();
    }
    function push (item) {
	var node = new StackNode(item);
	size += 1;
    	if (top) {
    	    node.next = top;
    	    top = node;
    	}
    	else {
    	    top = node;
    	    top.next = null;
    	}
    	return size;
    }
    function pop () {
    	var node = top;
	if (size > 0) {
	    top = node.next;
	    size -= 1;
	}
	return node.item();	
    }
    function size_ () {
	return size;
    }
    var me = this;
    if (!(this instanceof Stack)) return new StackNode;
    me.top = top_;
    me.pop = pop;
    me.push = push;
    me.size = size_;
    return Object.freeze(me);    
}




var num = new Stack();
num.push(1);
num.push(4);
num.push(5);
num.push(6);

var op = new Stack();
op.push("+");
op.push("*");
op.push("*");

function val () {
    var num2 = num.pop();
    var num1 = num.pop();
    var o = op.pop();
    if (o == "+") {
	num.push(num1 + num2);
    } else if (o === "*") {
	num.push(num1 * num2);
    }
    return num.top();
}

console.log(val());	// 5 * 6 = 30
console.log(val());	// 30 * 40 = 120
console.log(val()); 	// 120 + 1 = 121

function val2 () {
    var num2 = num.pop();
    var num1 = num.pop();
    var o = op.pop();
    if (o == "+") {
	num.push(num1 + num2);
    } else if (o === "*") {
	num.push(num1 * num2);
    }
    return num[0];
}

var start, stop;

console.log("Array:");
console.log(start = Date.now());
num = [];
op = [];
for (var i = 0; i < 10000; i++) {


num.push(1);
num.push(4);
num.push(5);
num.push(6);


op.push("+");
op.push("*");
op.push("*");

val2();	// 5 * 6 = 30
val2();	// 30 * 40 = 120
val2();	// 120 + 1 = 121

}
console.log(stop = Date.now());
console.log(stop - start);



console.log("Stack:");
console.log(start = Date.now());
num = new Stack();
op = new Stack();
for (var i = 0; i < 10000; i++) {


num.push(1);
num.push(4);
num.push(5);
num.push(6);


op.push("+");
op.push("*");
op.push("*");

val();	// 5 * 6 = 30
val();	// 30 * 40 = 120
val(); 	// 120 + 1 = 121

}
console.log(stop = Date.now());
console.log(stop - start);

/*
30
120
121
Array:
1364154233214
1364154233245
31
Stack:
1364154233247
1364154234057
810
*/

Der Stack realisiert dann kurz mit val() einen Taschenrechner, um zu zeigen, dass die Liste Funktioniert.

Hier ist schonmal ein Queue, den ich fuer level-order traversal brauchen kann. Basiert auf der Eingebung des Stacks, der wiederum auf der Eingebung basiert, dass der Professor sagte, dass man ihn mit einer Liste implementieren kann, und wenn man sich nicht ganz dumm anstellt die Operationen auch schnell sind..


function Queue () {
    "use strict";
    var back = null;
    var front = null;
    var size = 0;
    function QueueNode (item) {
	"use strict";
	function item_ () {
	    return item;
	}
	var me = this;
	if (!(this instanceof QueueNode)) return new QueueNode(item);
	me.item = item_;
	me.next = null;
	me.prev = null;
	return me;	
    }
    function first () {
	return front && front.item();
    }
    function last () {
	return back && back.item();
    }    
    function enqueue (item) {
	var node = new QueueNode(item);
	size += 1;
    	if (back && front) {
    	    back.prev = node;
    	    node.next = back;
    	    back = node;
    	} else {
    	    front = node;
    	    back = node;
    	    node.prev = null;
    	    node.next = null;
    	}
    	return size;
    }
    function dequeue () {
    	var node = front;
	if (size > 0) {
	    front = node.prev;
	    if (front) {
		front.next = null;
	    }
	    node.prev = null;
	    node.next = null;
	    size -= 1;
	    if (size == 0) {
		front = null;
		back = null;
	    }
	    return node.item();	
	}
	return null;
    }
    function size_ () {
	return size;
    }
    var me = this;
    if (!(this instanceof Queue)) return new QueueNode;
    me.first = first;
    me.last = last;
    me.enqueue = enqueue;
    me.dequeue = dequeue;
    me.size = size_;
    return Object.freeze(me);    
}


var schlange = new Queue();
schlange.enqueue("Sabine");
schlange.enqueue("Marc");
schlange.enqueue("Inge");
schlange.enqueue("Kalle");
schlange.enqueue("Eddie");

var patient;
while (patient = schlange.dequeue()) {
    console.log("Neuer: "+ patient);
    console.log("Laenge: noch "+schlange.size());
    console.log("Naechster: "+ schlange.first());
    console.log("Letzter: " + schlange.last());
    if (patient === "Kalle") { 
	schlange.enqueue("Juergen");
	console.log("neue Laenge: "+schlange.size());	
    }
}

/*
Neuer: Sabine
Laenge: noch 4
Naechster: Marc
Letzter: Eddie
Neuer: Marc
Laenge: noch 3
Naechster: Inge
Letzter: Eddie
Neuer: Inge
Laenge: noch 2
Naechster: Kalle
Letzter: Eddie
Neuer: Kalle
Laenge: noch 1
Naechster: Eddie
Letzter: Eddie
neue Laenge: 2
Neuer: Eddie
Laenge: noch 1
Naechster: Juergen
Letzter: Juergen
Neuer: Juergen
Laenge: noch 0
Naechster: null
Letzter: null
*/

Hier ist eine schnellere Fassung.

  /* Schneller als Queue ganz unten */

    function Queue () {
	var queue = {};
	queue.length = 0;
	queue.dequeue = Array.prototype.shift.bind(queue)
	queue.enqueue = Array.prototype.push.bind(queue)	
	queue.first = function () { return queue[0]; }
	queue.last = function () { return queue[queue.length-1]; }
	return queue;
    }
    
    /* Am Besten man schreibt sie so minimalistisch wie moeglich. */
    
    var q = new Queue();
    q.enqueue("Eddie");
    q.enqueue("Daddy");
    q.enqueue("Eddie Daddy");
    var naechster;
    while (naechster = q.dequeue()) {
	console.log("naechster: "+naechster);
	console.log("noch warten: " +q.length);
    }
    /*
    naechster: Eddie
    noch warten: 2
    naechster: Daddy
    noch warten: 1
    naechster: Eddie Daddy
    noch warten: 0
    */

Bäume und Traversion

Lektion 23

Hier kommt der SibTree dran, den man vom DOM in Vollendung kennt. Na, ob die den dort in Berkeley gelernt haben? Die kennen den auch.

Die Axiome der Lektionen schreibe ich beim naechsten mal, ich stelle aus, was ich angefangen habe.

if (typeof exports !== "undefined") {
exports.SibTree = SibTree;
exports.SibTreeNode = SibTreeNode;
}


function SibTreeNode (value, parent, firstchild, nextsibling) {
    var node = Object.create(SibTreeNode.prototype);
    node.constructor = SibTreeNode;
    node.value = value || null;
    // wer kennt die aus dem DOM?
    node.parent = parent || null,
    node.firstChild = firstchild || null,
    node.nextSibling = nextsibling || null
    return node;
}
SibTreeNode.prototype = Object.create(null);
SibTreeNode.prototype.appendChild = function SibTreeNode_appendChild (node) {
    var child = this.firstChild;
    if (child === null) {
	this.firstChild = node;
	node.parent = this;
	return;
    } else {
	while (child.nextSibling !== null) {
	    child = child.nextSibling;
	}
	child.nextSibling = node;
	node.parent = this;
    }
};

function SibTree (root) {
    var tree = Object.create(SibTree.prototype);
    tree.root = root || null;
    return tree;
}
SibTree.prototype.visit = function (visitor, node) {
    var node = node || this.root;
    visitor(node);
    node = node.firstChild;
    while (node) {
	node.visit(visitor, node);
	node = node.nextSibling;
    }
}

// Programm mit dem ich das mal ausprobiert hatte, funktionierte sogar sofort ohne Korrektur

if (typeof require !== "undefined") {
SibTree = require("./sibtree").SibTree;
SibTreeNode = require("./sibtree").SibTreeNode;
var inspect = require("util").inspect;
}

var root = new SibTreeNode();

for (var i = 0; i < 10; i++) {
    root.appendChild(new SibTreeNode("node "+i));
}

var tree = new SibTree(root);
tree.visit(function (value) {
    console.log(value);
});

// inspect(tree);
// console.dir(tree);

// console.log(JSON.stringify(tree, null, 4)); // error: zirkulaere Struktur wegen parent
	

/* Ausgabe 

{ constructor: [Function: SibTreeNode],
  value: null,
  parent: null,
  firstChild: 
   { constructor: [Function: SibTreeNode],
     value: 'node 0',
     parent: [Circular],
     firstChild: null,
     nextSibling: 
      { constructor: [Function: SibTreeNode],
        value: 'node 1',
        parent: [Circular],
        firstChild: null,
        nextSibling: [Object] } },
  nextSibling: null }
{ constructor: [Function: SibTreeNode],
  value: 'node 0',
  parent: 
   { constructor: [Function: SibTreeNode],
     value: null,
     parent: null,
     firstChild: [Circular],
     nextSibling: null },
  firstChild: null,
  nextSibling: 
   { constructor: [Function: SibTreeNode],
     value: 'node 1',
     parent: 
      { constructor: [Function: SibTreeNode],
        value: null,
        parent: null,
        firstChild: [Circular],
        nextSibling: null },
     firstChild: null,
     nextSibling: 
      { constructor: [Function: SibTreeNode],
        value: 'node 2',
        parent: [Object],
        firstChild: null,
        nextSibling: [Object] } } }
{ constructor: [Function: SibTreeNode],
  value: 'node 1',
  parent: 
   { constructor: [Function: SibTreeNode],
     value: null,
     parent: null,
     firstChild: 
      { constructor: [Function: SibTreeNode],
        value: 'node 0',
        parent: [Circular],
        firstChild: null,
        nextSibling: [Circular] },
     nextSibling: null },
  firstChild: null,
  nextSibling: 
   { constructor: [Function: SibTreeNode],
     value: 'node 2',
     parent: 
      { constructor: [Function: SibTreeNode],
        value: null,
        parent: null,
        firstChild: [Object],
        nextSibling: null },
     firstChild: null,
     nextSibling: 
      { constructor: [Function: SibTreeNode],
        value: 'node 3',
        parent: [Object],
        firstChild: null,
        nextSibling: [Object] } } }
{ constructor: [Function: SibTreeNode],
  value: 'node 2',
  parent: 
   { constructor: [Function: SibTreeNode],
     value: null,
     parent: null,
     firstChild: 
      { constructor: [Function: SibTreeNode],
        value: 'node 0',
        parent: [Circular],
        firstChild: null,
        nextSibling: [Object] },
     nextSibling: null },
  firstChild: null,
  nextSibling: 
   { constructor: [Function: SibTreeNode],
     value: 'node 3',
     parent: 
      { constructor: [Function: SibTreeNode],
        value: null,
        parent: null,
        firstChild: [Object],
        nextSibling: null },
     firstChild: null,
     nextSibling: 
      { constructor: [Function: SibTreeNode],
        value: 'node 4',
        parent: [Object],
        firstChild: null,
        nextSibling: [Object] } } }
{ constructor: [Function: SibTreeNode],
    
...

*/	

Die Lektion ist noch viel spannender.

Lektion 24

Priority Queues

Die Einträge (Entries) haben Key und Value.

Die totale Ordnung wird durch die Schlüssel definiert.

Operationen:

[Zeichnung vom Prof. hier]

[Source Code von mir weiter unten]

Gewöhnlicher Einsatzort: Event Queues in Simulationen. Da ist der Key die Zeit, wann das Event passiert. Und die Value die Beschreibung des Events.

Binary Heap: Eine Implementation von Priority Queues. Ein binary heap ist ein kompletter binaerer Baum. Komplett bedeutet, dass jeder Level (Row) des Baums voll ist, ausser moeglicherweise die letzte (unterste Reihe).

/*
    Konversionsregeln btree <-> bheap:
    first element: i = 1
    left child: 2i
    right child: 2i+1
    parent: i/2
*/


function BinaryHeap () {
    "use strict";
    
    var heap = null;
    var tree = null;
    var i = 1;
    
    function getNode (i) {
	var j = i-1;  // i
	if (i >= 0 && i < heap.length) return heap[j];
	else return null;
    }
    function getLeft (i) {
	var j = 2*i -1;  // 2*i
	if (j >= 0 && j < heap.length) return heap[j];
	return null;
    }
    function getRight (i) {
	var j = 2*i; // 2*i+1 
	if (j >= 0 && j < heap.length) return heap[j]; 
	else return null;
    }
    function toHeap (tree) {
	heap = [];
	tree.preorder(function (node) {
	    heap.push(node.entry);
	});
	return heap; 
    }
    function toTree () {
	tree = new BinaryTree();
	forEach(function (entry) {
	    tree.insert(entry);
	});
	return tree;
    }
    function forEach (f) {
	if (typeof f !== "function") throw "Function argument expected.";
	for (var i = 0, j = heap.length; i < j; i++) {
	    f(heap[i], i);
	}
    }
    function toSize () {
	return heap && heap.length;
    }
    
    var me = this;
    if (!(me instanceof BinaryHeap)) return new BinaryHeap;
    me.heap = toHeap;
    me.tree = toTree;
    me.each = forEach;
    me.size = toSize;
    me.nth = getNode;
    me.nthleft = getLeft;
    me.nthright = getRight;
    return Object.freeze(me);
}

[Zeichnung eines kompletten Binary Trees]

Die Entries in einem Binary Heap erfuellen ausserdem die heap-order-property: Kein Kind hat einen Key kleiner als sein parent key. Das heisst, der Wert des Parentknotens ist immer kleiner als die seiner Kinder. Die wiederrum kleiner sind als die Werte ihrer Kinder und so weiter.

Sie werden oftmals als Array von Entries durch inorder Traversion defininiert.

Das Mappen der Nodes (Baum) zu Indizes (Array) wird auch als Level-Numbering bezeichnet. Das bedeutet, Die Kinder von Node i sind 2i und 2i+1, das bedeutet, liegt Node i auf bheap[4], sind die Kinder auf bheap[8] (2i) und bheap[9] (2i+1) zu finden. (Anmerkung. Die letzte Reihe mag blanke Felder im Array hinterlassen. Die Felder kann man dann nicht nach links shiften, weil die Folge dann zerstoert wird und die Formel nicht mehr funktioniert.)

Jede tree node hat 2 Referenzen, eine für den Key und eine für die Value

	    node = { entry: { key, value }, left: node, right: node };
	

tree.min(); Gebe den Entry der Root zurück.

tree.insert(k, v): Lass x einen neuen Entry(k,v) sein. Plaziere x in der untersten Reihe auf den ersten freien Platz von links. Im Array bedeutet das, das erste freie Feld des Arrays zu nutzen.

Falls die unterste Reihe voll ist, wird eine neue erzeugt, von links begonnen. -- Das mag nun gegen die Heap-Order-Property (die Keys der Kinder sind groesser als der Key des Parents) verstossen.

Sollte der Key kleiner als sein Parent sein, bubbled der Entry up, bis die Heap-Order-Property erfuellt ist.

bubbling up Wiederhole: Vergleiche den Schluessel x mit dem Parent, wenn er kleiner ist, tauschen wir x mit dem parent. Solange, bis die x und parent kleiner oder gleich ist. (Mit den Siblings gibt es da keine Probleme, die braucht man nicht zu beachten, deren parents key bleibt kleiner durch das Umtauschen, so oder so.)

.removeMin(); Entferne den Eintrag an der Wurzel. Speichern fuer die return Value. Dadurch ensteht ein Loch. Man fuellt das Loch mit dem letzten Eintrag (x) im Baum. (Rechts in der untersten Reihe). Da der Schluessel dann wieder die HOP verletzt, bubblen wir ihn (x) diesmal down...

bubbling down Wiederhole: Falls x > eins seiner Kinder, oder > als beide Kinder, dann tausche x mit dem kleinerem Child. Solange, bis die HOP wieder hergestellt ist.

Subtrees eines kompletten Trees sind auch Binary Heaps (also wiederum komplette Trees)

Laufzeit:

Neben dem Tree kann man Priority Queues aber auch mit Listen, Arrays implementieren. Hier gibt es einen Vergleich vom Professor.

fn() Binary Heap Sorted List Unsorted List
min() Θ(1) Θ(1) Θ(n)
insert() worst-case Θ(log n) Θ(n) Θ(1)
insert() best-case Θ(1) Θ(1) Θ(1)
removeMin() worst-case Θ(log n) Θ(1) Θ(n)
removeMin() best-case Θ(1) Θ(1) Θ(n)

O(1) wird als konstante Zeit bezeichnet. Wieviele tausendstel ms das sind bei welcher Operation, sei mal 1 gegeben, jedenfalls ist die konstant..

n = lineare Zeit (z.B. muessen zusaetzlich alle items beim insert im Array ausserdem nach rechts verschoben werden).

insert() braucht O(1) um x mit dem parent zu vergleichen.

Kompletter Binaerbaum: hat mindestens l+log2n level; n ist die # der entries. Θ(log n) ist damit worst-case time.

Bottom-Up Heap Konstruktion:

Gegeben seinen ein Haufen Entries, man mache nun einen Heap aus denen.

insert() einen nach dem anderen. Θ(n log n).

void bottomupheap();

Baue einen kompletten Baum aus den Entries in irgendeiner Ordnung. Laufe rückwärts vom letzten internen Knoten (vorletzte Reihe rechts, in der letzten Reihe sind Blätter, keine Knoten) zur root. Zum Beispiel rückwärts im Array. Und wenn wir einen Knoten besuchen, bubblen wir sie down wie in removeMin(), als wenn die HOP nicht erfüllt wird. --- Dann gehts einen Schritt zurueck, dass heisst, linker Sibling vom letzten internen Knoten rechts, bubblen den down, dann gehen wir einen Level hoch, in dem Beispiel jetzt die Root, und dann Bubblen wir die down.

[Zeichnung zur Veranschaulichung hier...]

function PriorityQueue (options) {
    "use strict";
    var me = this;
    var root = null;

    function Node (k, v, p, l, r) {
	"use strict";
	var me = this;
	var o;
	if (typeof k === "object" && k !== null) {
	    o = k;
	    k = o.key;
	    v = o.value;
	    p = o.parent;
	    l = o.left;
	    r = o.right;
	}
	me.key = typeof k !== "undefined" ? k : null;
	me.value = typeof v !== "undefined" ? v : null;
	me.parent = p || null;
	me.left = l || null;
	me.right = r || null;
	return Object.seal(me);
    }
    
    
    function find (k, node) {
	node = node || root;
	if (node) {
	    if (k === node.key) return node;
	    if (k < node.key) return find(k, node.left);
	    if (k > node.key) return find(k, node.right);
	}
	return null;
    }
    
    
    function update(k, v, node) {
	return insert(k, v, node, true);
    }
    
    function insert (k, v, node, update) {
	var c;
	c = new Node(k,v, null, null, null);
	if (root === null) {
	    root = c;     
	    return c;
	} else {
	    node = node || root;
	    while (node) {
		if (node.key === k) {
		    if (update) {
			 node.value = v;
	    		return node;
	    	    } else {
	    		return null;
	    	    }
		} else if (k < node.key) {
		    if (!node.left) {
			c.parent = node;
			node.left = c;
			return c;
		    } else {
			node = node.left;
		    }
		} else if (k > node.key) {
		    if (!node.right) {
			c.parent = node;
			node.right = c;
			return c;
		    } else {
			node = node.right;
		    }
		}
	    }
	}
	return null;
    }
    
    function removeMin () {
	var node = root;
	var right;
	while (node) {
	    if (node.left) node = node.left;
	    else break;
	}
	if (node) {
	    if (node.left) throw "mistaken programming";
	    right = node.right;
    	    node.right = null;
    	    if (!node.parent && right) {
    		root = right;
    	    } else if (!node.parent && !right) {
    		root = null;
    	    }
	    if (right) {
		right.parent = node.parent;
		node.parent = null;
		if (right.parent) {
		    right.parent.left = right;
		}
	    } 
	    if (node.parent) {
	        node.parent.left = null;
	    } 
	}
	return node;
    }
    
    function inorder(visit, node) {
	node = node || root;
	if (node) {
	    if (node.left) inorder(visit, node.left);
	    var r = visit(node);
	    if (node.right) inorder(visit, node.right);
	    return r;
	} 
	return null;
    }
    
    function print () {
	var nodes = 0;
	inorder(function (node) {
	    ++nodes;
	    console.log("node "+nodes+ ": key="+node.key+", value="+node.value+ " (l="+(node.left && node.left.key)+",p="+(node.parent && node.parent.key)+",r="+(node.right && node.right.key)+")");
	});
    }
    
    var me = this;
    if (me instanceof PriorityQueue === false) return new PriorityQueue(options);
    me.insert = insert;
    me.find = find;
    me.update = update;
    me.removeMin = removeMin;
    me.print = print;
    return Object.freeze(me);
}

/* ---- ausprobieren */

var pq = new PriorityQueue();

pq.insert(30, "Hallo Welt");
pq.insert(20, "Hallo Eddie");
pq.insert(10, "Hallo Queue");
pq.insert(40, "Hallo BSP");
pq.insert(1, "More");
pq.print();

function next () {
    var n;
    n=pq.removeMin();
    if (n) {
        console.log("removeMin().key == " +(n.key) + ", value=" +(n.value));
    } else { 
	console.log("removeMin() == null (Queue empty)"); 
    }
    pq.print();
}

next();
next();
next();
next();
next();
next();

for (var i = 0; i < 10; i++) {
    pq.insert(Math.random().toPrecision(3), "Zufallswert "+(i+1));
}
for (var i = 0; i < 10; i++) {
    next();
}
/*
node 1: key=1, value=More (l=null,p=10,r=null)
node 2: key=10, value=Hallo Queue (l=1,p=20,r=null)
node 3: key=20, value=Hallo Eddie (l=10,p=30,r=null)
node 4: key=30, value=Hallo Welt (l=20,p=null,r=40)
node 5: key=40, value=Hallo BSP (l=null,p=30,r=null)
removeMin().key == 1, value=More
node 1: key=10, value=Hallo Queue (l=null,p=20,r=null)
node 2: key=20, value=Hallo Eddie (l=10,p=30,r=null)
node 3: key=30, value=Hallo Welt (l=20,p=null,r=40)
node 4: key=40, value=Hallo BSP (l=null,p=30,r=null)
removeMin().key == 10, value=Hallo Queue
node 1: key=20, value=Hallo Eddie (l=null,p=30,r=null)
node 2: key=30, value=Hallo Welt (l=20,p=null,r=40)
node 3: key=40, value=Hallo BSP (l=null,p=30,r=null)
removeMin().key == 20, value=Hallo Eddie
node 1: key=30, value=Hallo Welt (l=null,p=null,r=40)
node 2: key=40, value=Hallo BSP (l=null,p=30,r=null)
removeMin().key == 30, value=Hallo Welt
node 1: key=40, value=Hallo BSP (l=null,p=null,r=null)
removeMin().key == 40, value=Hallo BSP
removeMin() == null (Queue empty)
removeMin().key == 0.0599, value=Zufallswert 4
node 1: key=0.185, value=Zufallswert 6 (l=null,p=0.378,r=0.344)
node 2: key=0.344, value=Zufallswert 7 (l=null,p=0.185,r=null)
node 3: key=0.378, value=Zufallswert 1 (l=0.185,p=null,r=0.681)
node 4: key=0.488, value=Zufallswert 9 (l=null,p=0.564,r=null)
node 5: key=0.564, value=Zufallswert 8 (l=0.488,p=0.589,r=null)
node 6: key=0.589, value=Zufallswert 3 (l=0.564,p=0.681,r=null)
node 7: key=0.681, value=Zufallswert 2 (l=0.589,p=0.378,r=0.687)
node 8: key=0.687, value=Zufallswert 5 (l=null,p=0.681,r=0.874)
node 9: key=0.874, value=Zufallswert 10 (l=null,p=0.687,r=null)
removeMin().key == 0.185, value=Zufallswert 6
node 1: key=0.344, value=Zufallswert 7 (l=null,p=0.378,r=null)
node 2: key=0.378, value=Zufallswert 1 (l=0.344,p=null,r=0.681)
node 3: key=0.488, value=Zufallswert 9 (l=null,p=0.564,r=null)
node 4: key=0.564, value=Zufallswert 8 (l=0.488,p=0.589,r=null)
node 5: key=0.589, value=Zufallswert 3 (l=0.564,p=0.681,r=null)
node 6: key=0.681, value=Zufallswert 2 (l=0.589,p=0.378,r=0.687)
node 7: key=0.687, value=Zufallswert 5 (l=null,p=0.681,r=0.874)
node 8: key=0.874, value=Zufallswert 10 (l=null,p=0.687,r=null)
removeMin().key == 0.344, value=Zufallswert 7
node 1: key=0.378, value=Zufallswert 1 (l=null,p=null,r=0.681)
node 2: key=0.488, value=Zufallswert 9 (l=null,p=0.564,r=null)
node 3: key=0.564, value=Zufallswert 8 (l=0.488,p=0.589,r=null)
node 4: key=0.589, value=Zufallswert 3 (l=0.564,p=0.681,r=null)
node 5: key=0.681, value=Zufallswert 2 (l=0.589,p=0.378,r=0.687)
node 6: key=0.687, value=Zufallswert 5 (l=null,p=0.681,r=0.874)
node 7: key=0.874, value=Zufallswert 10 (l=null,p=0.687,r=null)
removeMin().key == 0.378, value=Zufallswert 1
node 1: key=0.488, value=Zufallswert 9 (l=null,p=0.564,r=null)
node 2: key=0.564, value=Zufallswert 8 (l=0.488,p=0.589,r=null)
node 3: key=0.589, value=Zufallswert 3 (l=0.564,p=0.681,r=null)
node 4: key=0.681, value=Zufallswert 2 (l=0.589,p=null,r=0.687)
node 5: key=0.687, value=Zufallswert 5 (l=null,p=0.681,r=0.874)
node 6: key=0.874, value=Zufallswert 10 (l=null,p=0.687,r=null)
removeMin().key == 0.488, value=Zufallswert 9
node 1: key=0.564, value=Zufallswert 8 (l=null,p=0.589,r=null)
node 2: key=0.589, value=Zufallswert 3 (l=0.564,p=0.681,r=null)
node 3: key=0.681, value=Zufallswert 2 (l=0.589,p=null,r=0.687)
node 4: key=0.687, value=Zufallswert 5 (l=null,p=0.681,r=0.874)
node 5: key=0.874, value=Zufallswert 10 (l=null,p=0.687,r=null)
removeMin().key == 0.564, value=Zufallswert 8
node 1: key=0.589, value=Zufallswert 3 (l=null,p=0.681,r=null)
node 2: key=0.681, value=Zufallswert 2 (l=0.589,p=null,r=0.687)
node 3: key=0.687, value=Zufallswert 5 (l=null,p=0.681,r=0.874)
node 4: key=0.874, value=Zufallswert 10 (l=null,p=0.687,r=null)
removeMin().key == 0.589, value=Zufallswert 3
node 1: key=0.681, value=Zufallswert 2 (l=null,p=null,r=0.687)
node 2: key=0.687, value=Zufallswert 5 (l=null,p=0.681,r=0.874)
node 3: key=0.874, value=Zufallswert 10 (l=null,p=0.687,r=null)
removeMin().key == 0.681, value=Zufallswert 2
node 1: key=0.687, value=Zufallswert 5 (l=null,p=null,r=0.874)
node 2: key=0.874, value=Zufallswert 10 (l=null,p=0.687,r=null)
removeMin().key == 0.687, value=Zufallswert 5
node 1: key=0.874, value=Zufallswert 10 (l=null,p=null,r=null)
removeMin().key == 0.874, value=Zufallswert 10
*/

Binäre Suchbäume

Lektion 25

Für jeden Knoten und des Folgeknoten (links, rechts) gilt: Links ist die Zahl kleiner als der Wert des Knotens (node.left.value < node.value), rechts die Zahl groesser (node.right.value > node.value).

Traversiert wird inorder, dass heisst, erst links, dann die node, dann rechts.

Das ist eine vernuenftige Zusammenfassung fuer Binaere Suchbaeume. Um das aber mal zu zeigen, und die Zahlen sprechen zu lassen brauche ich erstmal einen Binaerbaum. Der folgende Code ist der Anfang der Binaerbaumdatenstruktur, die ich schreiben werde.

Neben inorder enthaelt er bereits mehrere Traversionsarten. Um die Inordertraversion, um geordnete Zahlen, vom kleinsten zu groessten Key aus dem Suchbaum aufgrund der links kleiner, rechts groesser Regel, nochmal zu zeigen, muss ich mir nochmal Zeit nehmen und die Lektion nochmal machen.

Hier erstmal ein Binaerer Baum. Mit eingekapselten Properties, aber public access ueber die Methoden. Das kann ich im folgenden dann noch feiner einstellen, und noch weiter entwickeln. Die inorder Funktion aus Binaere Suchbaeume ist bereits drin. Man kann die Keys jetzt von Hand ordnen und sich die mal ausgeben lassen. Am besten man nimmt ein Blatt Papier und zeichnet sich Zahlen auf, links kleiner, rechts groesser, als die eigene Zahl, wir koennen links oder rechts von der zahl unseres parents sein, je nachdem, ob wir kleiner oder groesser sind.

if (typeof exports !== "undefined") {
    exports.BinaryTree = BinaryTree;	// Der Tree
    exports.BinaryNode = BinaryNode;	// Ein Knoten im Tree
    exports.BinaryHeap = BinaryHeap;    // (merge) Der Heap aus dem Tree
}

function BinaryNode (key, value, parent, left, right) {
    "use strict";
    var me = this;
    if (!(me instanceof BinaryNode)) return new BinaryNode(key, value, parent, left, right);
    if (arguments.length === 1) {
	value = key.value || null;
	parent = key.parent || null;
	left = key.left || null;
	right = key.right || null;
	key = key.key || null;
    } 
    me.key = key || null;
    me.value = value || null;
    me.parent = parent || null;
    me.left = left || null;
    if (me.left instanceof BinaryNode) me.left.parent = me;
    me.right = right || null;
    if (me.right instanceof BinaryNode) me.right.parent = me;
    return Object.seal(me);
}

function BinaryTree (root) {
    "use strict";
    var me;
    function getset_root (update) {
	if (update && update instanceof BinaryNode) {
	    root = update;
	    root.parent = null;
	}
	return root;
    }
    function preorder (visit, node) {
        node = node || root;
        visit(node);    
        if (node.left) { 
	    preorder(visit, node.left);
        }
        if (node.right) {
	    preorder(visit, node.right);
        }    
    }
    function inorder (visit, node) {
        node = node || root;
        if (node.left) { 
	    inorder(visit, node.left);
        }
        visit(node);
        if (node.right) {
    	    inorder(visit, node.right);
        }
    }
    function postorder (visit, node) {
        node = node || root;
        if (node.left) { 
	    postorder(visit, node.left);
        }
        if (node.right) {
    	    postorder(visit, node.right);
        }    
        visit(node);    
    }
    function levelorder (visit, node) {
	node = node || root;
	var lastlevel = -1;
	var level = 0;
	var queue = [];
	var w;
	queue.push({node:node, level: level });
	while (queue.length)  {
	    w = queue.shift();
	    node = w.node;
	    level = w.level;
	    visit(node, level);
	    if (level > lastlevel) {
		lastlevel = level;
	    }
	    if (node.left) { queue.push({node:node.left,level:level+1}); }
	    if (node.right) { queue.push({node:node.right,level:level+1}); }
	}
    }    
        
    function find (key, node) {
	node = node || root;
	if (key < node.key) {
	    node = find(key, node.left);
	} else if (key > node.key) {
	    node =  find(key, node.right);
	} else if (key === node.key) {
	    return node;
	}
	return node;
    }
    function insert (key, value, node) {
	var newnode;
	if (key instanceof BinaryNode) { 
	    newnode = key;
	    key = newnode.key;
	    value = newnode.value;
	}
    	if (root === null) {
    	    return ((root = newnode || new BinaryNode({key:key,value:value})), root.parent = null, root);
    	}
    	node = node || root;
	if (key < node.key) {
	    if (node.left === null) {
		node.left = newnode || new BinaryNode({key:key,value:value});
		node.left.parent = node;
		return node.left;
	    } else {
		return insert(newnode || key, value, node.left);
	    }
	} else if (key > node.key) {
	    if (node.right === null) {
		node.right = newnode || new BinaryNode({key:key,value:value});
		node.right.parent = node;
		return node.right;
	    } else {
		return insert(newnode || key, value, node.right);
	    }
	} else if (key === node.key) {
	    return null;
	}
	return null;
    }

    function update (key, value) {
	var node = find(key);
	if (node) {
	    node.value = value;
	    return node;
	}
	return null;
    }

    function remove (key) {
	var node, parent, left, right;
	node = find(key);
	if (node) {
	    parent = node.parent;
	    left = node.left;
	    right = node.right;
	    if (node === parent.left) {
		// entferne node links
		// mit bubbling und co
	    } else if (node === parent.right) {
		// entferne node rechts
		// mit rotation und co
	    }
	    return node;
	} else {
	    return null;
	}
    }

    function rotatel (x) {
	var p = x.parent;
	var leftchild = x.parent && x.parent.left === x;
	var y = x.right;
	var B = y.left;
	x.right = B;
	if (B) B.parent = x;
	y.left = x;
	x.parent = y;
	y.parent = p;
	if (p !== null) {
	    if (leftchild) {
		p.left = y;
	    } else {
		p.right = y;
	    }
	} else {
	    root = y;
	}
    }
    
    function rotater (y) {
	var p = y.parent;
	var leftchild = y.parent && y.parent.left === y;
	var x = y.left;
	var B = x.right;
	y.left = B;
	if (B) B.parent = y;
	x.right = y;
	y.parent = x;
	x.parent = p;
	if (p !== null) {
	    if (leftchild) {
		p.left = x;
	    } else {
		p.right = x;
	    }
	} else {
	    root = x;
	}
    }

    
    function height (node) {
	var height = 1;
	while (node.parent) {
	    node = node.parent;
	    ++height;
	}
	return height;
    }


    function levelorder_mod (visit, node) {
	/*
	    Modifiziert, Daten ueber die Position mitzugeben.
	*/
	node = node || root;
	var lastlevel = -1;
	var lastchild = 0;
	var level = 0;
	var queue = [];
	var parent;
	var child;
	var w;
	queue.push({node:node, parent: node.parent, level:level, child: 1});
	while (queue.length)  {
	    w = queue.shift();
	    node = w.node;
	    level = w.level;
	    parent = w.parent;
	    child = w.child;
	    visit(node, level, parent, child);
	    if (level > lastlevel) {
		lastlevel = level;
		lastchild = 0;
	    }
	    if (node.left) { queue.push({node:node.left, parent: node.parent, level:level+1, child: lastchild+1}); }
	    if (node.right) { queue.push({node:node.right, parent: node.parent, level:level+1, child: lastchild+2}); }
	    lastchild+=2;
	}
    }    
        
    function fixlen(str, w) {
	var l = str.length;
	if (l < w) {
	    for (var i =0; w < l; l++) {
		str+= " ";
	    }
	    return "{"+str+"}";
	} else {
	    return "{"+str.substr(0,w)+"}";
	}
   }
    function print (node) {
	/* 
	Muss verbessert werden,
	hier muss ein Zaehler hin, ein
	Pointer zum Parent, oder die # dessen auf seiner Zeile, von wem ich bin,
	um zu wissen, wie weit ich eingerueckt werden will. 
	*/
	
	var output = "'BinaryTree': {";
	var whole = "";
	var lastlevel = -1;
	var lastchild;
	node = node || root;
	levelorder_mod(function (node, level, parent, child) {
	    if (level > lastlevel) {
		output += "";
		lastlevel += 1;	
		whole += output;
		console.log(output);
		output = "";
	    } 
	    if (parent && parent.right === node) { 
		     output += "\\";
		     if (parent && parent.right == null) output += fixlen("[null]",10);
	    }
	    if (node !== null) output += fixlen(+node.key+",'"+node.value+"'",10);
	    if (parent && parent.left === node) { 
		if (parent && parent.right == null) output += fixlen("[null]",10);
		output += "/";
	    }
	    output += " ";
	});
	output += "\n";
	output += "}";
	whole+=output;
	console.log(output);
	return whole;
    }
    
    
    function minimum (key) {
	var min, node;
	if (!(key instanceof BinaryNode) && key !== null) node = find(key); else node = key;
	if (!(min = node)) return null;
	while (node = node.left) {
	    min = node;
	}
	return min;
    }
    
    function maximum (key) {
	var max, node;
	if (!(key instanceof BinaryNode) && key !== null) node = find(key); else node = key;
	if (!(max = node)) return null;
	while (node = node.right) {
	    max = node;
	}
	return max;
    }
    
    function successor (key) {
	var node;
	if (!(key instanceof BinaryNode)) node = find(key); else node = key;
	if (node.right) {
	    return minimum(node.right);
	} else if (node.right === null && node.parent && node.parent.left === node) {
	    return node.parent;
	}
	return null;
    }
    
    function predecessor (key) {
    	var node;
	if (!(key instanceof BinaryNode)) node = find(key); else node = key;
	if (node.left) {
	    return maximum(node.left);
	} else if (node.left === null && node.parent && node.parent.right === node) {
	    return node.parent;
	} 
	return null;
    }


    function remove_min () {
    }
    function remove_max () {
    }
    
    

    function is_bst (node) {
	if (!node) node = root;
	if (node.left) {
	    if (node.left.key >= node.key) {
		return false;
	    } else {
		if (!is_bst(node.left)) return false;
	    }
	}
	if (node.right) {
	    if (node.right.key <= node.key) {
		return false;
	    } else {
		if (!is_bst(node.right)) return false;
	    }
	}
	return true;
    }
    
    
    function isminheap (node) {
	// alle parents <= ihre children
	node = node || root;
	if (node.left) {
	    if (node.left.key <= node.key) {
		return false;
	    } else {
		if (!isminheap(node.left)) return false;
	    }
	}
	if (node.right) {
	    if (node.right.key <= node.key) {
		return false;
	    } else {
		if (!isminheap(node.right)) return false;
	    }
	}
	return true;
    }
    
    function ismaxheap (node) {
	// alle parents >= ihre children
	node = node || root;
	if (node.left) {
	    if (node.left.key >= node.key) {
		return false;
	    } else {
		if (!ismaxheap(node.left)) return false;
	    }
	}
	if (node.right) {
	    if (node.right.key >= node.key) {
		return false;
	    } else {
		if (!ismaxheap(node.right)) return false;
	    }
	}
	return true;	
    }

    me = this;
    root = root || null;
    if (!(me instanceof BinaryTree)) return new BinaryTree(root);
    if (!(root instanceof BinaryNode && root !== null)) {
	if (root) throw "BinaryNode for root position required";
    }

    me.root = getset_root;
    // traversion
    me.preorder = preorder;
    me.inorder = inorder;
    me.postorder = postorder;
    me.levelorder = levelorder;
    // standard operations
    me.find = find;
    me.insert = insert;
    me.update = update;
    me.remove = remove;
    // balancing/rotate
    me.leftrotate = rotatel;
    me.rightrotate = rotater;
    // print
    me.print = print;
    // height of a node
    me.height = height;
    
    // Bst
    me.is_bst = is_bst;
    // minheap und maxheap properties
    me.minimum = function (keyornode) { keyornode = keyornode || root; return minimum(keyornode); };
    me.maximum = function (keyornode) { keyornode = keyornode || root; return maximum(keyornode); };
    me.successor =  function (keyornode) { keyornode = keyornode || root; return successor(keyornode); };
    me.predecessor =  function (keyornode) { keyornode = keyornode || root; return predecessor(keyornode); };
    
    me.is_maxheap = ismaxheap;
    me.is_minheap = isminheap;
    // to array
    return Object.freeze(me);
}

Eigentlich habe ich die Geschichte genial kurzgefasst, wie die Schluessel (Zahlen) der Nodes zu ordnen sind.

Balancierte Suchbäume

Lektion 26

2-3-4 Tree

Den Code habe ich noch nicht zu Ende gebracht. Ein 2-3-4 Suchbaum ist etwas breiter und weniger tief als ein normaler Baum. Er kann zwischen 1-3 keys mit 1-4 children speichern und balanciert sich selbst aus, wenn neue keys eingefuegt werden, indem er sich aufbricht und neu ordnet. Sollte man auf dem Weg nach unten auf eine Node mit 3 keys treffen, kickt man den mittleren (!) key und seine children hoch. Dadurch dass das immer geschieht, haelt sich der Baum in Balance.

Die insert Operation, wie der 2-3-4 Tree sich aufbricht und den mittleren Key nach oben bewegt sowie seine children re-arrangiert muss ich noch einmal gucken, bevor ich den Code zu Ende bringe.

Das hier ist erst der Anfang vom 2-3-4 tree. Eine Inorder Traversion gibt aber bereits geordnete Keys aus, wenn ich mit Math.random() wild welche einfuege. Ist schonmal ein gutes Zeichen, die weiter zu schreiben...

function TwoThreeFourTree (root) {

    "use strict";
    var size = 0;

    function Entry (k, e) {
        var entry = Object.create(null);
        entry.key = k;
        entry.value = e;
        entry.toString = function () { return "[object Entry ("+k+")]"; };
        return Object.seal(entry);
    }


    function TwoThreeFourNode (parent, entries, children) {
	"use strict";
        var me = this;
        if (!(me instanceof TwoThreeFourNode)) return new TwoThreeFourNode(parent, entries, children);
	me.parent = parent;
	entries = entries || []; 
        me.entries = entries;
        children = children || [];
        me.children = children;
        return Object.freeze(me);
    }

        function inorder (visit, node) {
    	    var c, e;
    	    node = node || root;
    	    if (typeof visit !== "function") throw "no visit function";
            for (var i = 0; i < node.entries.length; i++) {
        	if (c=node.children[i]) inorder(visit,c);
        	if (e=node.entries[i]) visit(e);
            }
            if (c=node.children[node.entries.length]) inorder(visit,c);
        }

        function preorder (visit, node) {
    	    var c, e, i;
    	    node = node || root;
    	    if (typeof visit !== "function") throw "no visit function";
            for (i = 0; i < node.entries.length; i++) {
        	if (e=node.entries[i]) visit(e);
            }
            for (i = 0; i < node.children.length; i++) {
    	        if (c=node.children[i]) preorder(visit, c);
    	    }
        }
        
        function postorder (visit, node) {
    	    var c, e, i;
    	    node = node || root;
    	    if (typeof visit !== "function") throw "no visit function";
            for (i = 0; i < node.children.length; i++) {
    	        if (c=node.children[i]) postorder(visit, c);
    	    }
            for (i = 0; i < node.entries.length; i++) {
        	if (e=node.entries[i]) visit(e);
            }    	    
        }        
        
        function levelorder (visit, node) {
    	    node = node || root;
    	    var levels = [];
    	    var level = 0;
    	    function summarize(node, level) {
    		// like bfs
    	    }
    	    levels.forEach(function (level) {
    		level.forEach(visit);
    	    });
        }
        
        
        

        function remove (node, k) {
        }
        
        function remove_ (k) {
    	    remove(root, k);
        }

        function insert (node, k, e) {
            var entry, t, ok, oe, c;
    	    node = node || root;
	    /* Node ist Leer */
            if (node.entries.length === 0) {
        	entry = Entry(k, e);
        	return node.entries[0] = entry;
            }
            
            /* Node ist voll */
            if (node.entries.length === 3) {
            	    ok = node.entries[2].key, oe = node.entries[2].value;
            	    /*
            		Hier jetzt der Code, wo ich die Children umstelle
            		room for an extra key?
            		parent hat bereits nur 2 keys max.
            		kicking the key upstairs higher
            			 [ 20 ]
            		[10 11 12]
            		
            			[11      20]
            		    [10]    [12]
	        		
            	    */
            	    
            	    
            	    if (node.parent === null) {
        		root = node.parent = new TwoThreFourNode(node.parent);
            	    } else {
            	        node.parent = new TwoThreFourNode(node.parent);
            	        /* Hier jetzt richtig zuweisen... */
            	    }
                    return insert(node.parent, oe, ok);
    	    }
            /* Performe insert, falls noch nichts passierte,
            vergleiche dafuer die keys */
    		for (var i=0; i < node.entries.length; i++) {
            	    if ((t=node.entries[i]) && k < t.key) {
            		if (c = node.children[i]) {
            		    return insert(c, k, e);
            		} else {
            		    c = node.children[i] = new TwoThreeFourNode(me);
            		    return insert(c, k, e);
            		}
            	    }
        	}
        	if (t && k > t.key) {
            		if (c = node.children[node.entries.length]) {
            		    return insert(c, k, e);
            		} else {
            		    c = node.children[node.entries.length] = new TwoThreeFourNode(me);
            		    return insert(c, k, e);
            		}
        	}
        }

        function find (node, k) {
            var key, rkey, child;
            var entries = node.entries;
            var children = node.children;
            for (var i = 0; i < entries.length; i++) {
        	key = entries[i].key;
        	rkey = entries[i+1] && entries[i+1].key || null;
        	child = children[i];
        	if (k === key) return entries[i].value;
	        if (k < key) {
            	    return find(child, k);
        	} else if (k > key && rkey !== null && k < rkey) {
            	    return find(child, k);
        	}
            }
            if (children[entries.length]) return find(children[entries.length]);
            return null;
        }


    function root_ () {
	return root;
    }
    
    function insert_ (key, value) {
	if (!root) root = new TwoThreeFourNode(null);
	return insert(root, key, value); // Die dann insert auf ihren nodes ruft
    }
    
    function find_ (k) {
	return find(root, k);
    }
    
    var me = this;
    if (!(me instanceof TwoThreeFourTree)) return new TwoThreeFourTree();
    me.find = find_;
    me.insert = insert_;
    me.remove = remove_;
    me.root = root_;
    me.inorder = inorder;
    me.preorder = preorder;    
    me.postorder = postorder;
    
    return me;
}


/* Ausprobieren */


var tree = new TwoThreeFourTree();
var i;
for (i = 0; i < 50; i++) {
    if (i % 3 === 0) {
	tree.insert(i, "abcd"+i);
	    console.log(i);
    }
}
for (i = 10; i < 40; i++) {
    if (i % 2 === 0) {
	tree.insert(i, "abcd"+i);
		    console.log(i);
    }
}
for (i = 0; i < 50; i++) {
    if (i % 4 === 0) {
	tree.insert(i, "abcd"+i);
	    console.log(i);
    }
}
for (i = 1; i < 60; i++) {
    tree.insert(i, "abcd"+i);
}

console.log("inorder:");
tree.inorder(function (entry) {
    console.log("node: "+entry.key+" ("+entry.value+")");
});
console.log("preorder:");
tree.preorder(function (entry) {
    console.log("node: "+entry.key+" ("+entry.value+")");
});
console.log("postorder:");
tree.postorder(function (entry) {
    console.log("node: "+entry.key+" ("+entry.value+")");
});

console.log(tree.root().entries);
console.log(tree.root().children);
	

AVL Trees

Nicht aus CS61B, sondern aus MIT6.006 ist das Kapitel AVL Trees.

Ebenfalls ein selbstbalancierender Baum, der anhand der Hoehe seiner Children entscheidet, ob er sich ordnen muss.

Graphen

Lektion 27

Hier eine praktische Anwendung eines Graphen. Ich male seinen Pfad. Oder nicht wortwortlich. Ich male vom einen Vertex zum naechsten eine Linie.

window.addEventListener("DOMContentLoaded", function (e) {
    var canvas, context;
    canvas = document.querySelector("#cv");
    canvas.width = 200;
    canvas.heigth = 200;
    context = canvas.getContext("2d");
    function Point(x,y) {
	return Object.freeze({ x:x, y:y });
    }
    var g = new Graph();
    /*
   p1
p5/  \p2
  |   |
p4 __ p3
    */
    var p1 = g.insert("p1",Point(10,40));	
    var p2 = g.insert("p2",Point(50,20));	
    var p3 = g.insert("p3",Point(90,40));
    var p4 = g.insert("p4",Point(90,90));
    var p5 = g.insert("p5",Point(10,90));
    var colors = ["red","green","blue","yellow","brown"];
    p1.connect(p2);
    p2.connect(p3);
    p3.connect(p4);
    p4.connect(p5);
    p5.connect(p1);

    context.moveTo(p1.value().x, p1.value().y);
    
    g.dfs(p1, function (v) {
	var point = v.value();
	context.save();
	context.lineTo(point.x, point.y);
	context.lineColor = colors.shift();
	context.stroke();
	context.restore();
    });
    // letzter Vertex ausgeschlossen
    context.save();
    context.lineTo(p1.value().x, p1.value().y);
    context.lineColor = colors.shift();
    context.stroke();
    context.restore();

}, false);

/*
    Wenn das fertig ist, wird das mal ein Graph
    
*/

function Graph (options) {
    "use strict"
    
    var vertices = []; 
    var digraph = false;
    
    function Edge(origin,destination,weight) {
	return Object.seal({
	    __proto__: Edge.prototype,
	    vertices: [origin,destination],
	    weight: weight
	});
    }
    
    function Vertex (key, value) {

	function get_key () { return key; }
	function get_value () { return value; }
	function set_value (v) { value = v;  }
	function get_weight (v) {
	
	}
	function set_weight (v, weight) {
	    adjacents.forEach(function (edge) {
		if (!digraph && edge.vertices[0] === v || edge.vertices[1] === v) {
		    edge.weight = weight;
		} else if (digraph && edge.vertices[1] === v) {
		    edge.weight = weight;
		}
	    });
	}
	
	function connect (v, weight) {
	    if (v instanceof Edge) {
		adjacents.push(v);
		return v;
	    } else {
		var edge = Edge(me, v, weight);
		adjacents.push(edge);
		if (!digraph) {
		    v.connect(edge);
		}	
		return edge;
	    }
	}
	function disconnect (v) {
	    if (v instanceof Vertex) { // by vertices[1]
	        adjacents = adjacents.filter(function (edge) {
	    	    if (!digraph && edge.vertices[1] === v) {
	    		v.disconnect(edge);
	    	    }
		    return edge.vertices[1] !== v;
		});
	    } else if (v instanceof Edge) { // by ref
		adjacents = adjacents.filter(function (edge) {
		    return v !== edge;
		});
	    }
	}
	
	function neighbor_visit (f) {
	    if (typeof f === "function") {
		adjacents.forEach(function (edge){
		    f.call(me, edge.vertices[1]);
		});
	    }
		else throw "function(vertex) expected";
	}
	
	function get_adjacents_copy () {
	    return adjacents.slice();
	}
	
	var adjacents = [];
	var me = { __proto__: Vertex.prototype };
	me.key = get_key;
	me.value = get_value;
	me.update = set_value;
	me.connect = connect;
	me.disconnect = disconnect;
	me.neighbors = neighbor_visit;
	me.adjacents = get_adjacents_copy;
	me.dfs = function (f) { return dfs(me, f); };
	me.bfs = function (f) { return bfs(me, f); };
	return Object.freeze(me);
    }
    
    
    function bfs (vertex, visitfunc) {

	var levels = [];
	var visited = [];
	var e;
	levels[0] = [vertex];
	visited.push(vertex);
	summarize(vertex, 1);
	function summarize (vertex, lvl) {
	    if (levels[lvl] === undefined) levels[lvl] = [];
	    var edges = vertex.adjacents();
	    for (var i = 0, j = edges.length; i < j; i++) {
		e = edges[i];
		if (e) {
		    e = e.vertices[1];
		    if (visited.indexOf(e) === -1) {
		        levels[lvl].push(e);
	    		visited.push(e);
			summarize(e, lvl+1);
		    }
		}
	    }
	}
	levels.forEach(function (level) {
	    level.forEach(function (node) {
		visitfunc(node);
	    });
	});
    }
    
    function dfs (vertex, visitfunc) {
	var visited = [];
	visitfunc(vertex);
	visited.push(vertex);
	vertex.neighbors(function traverse (v) {
	    if (visited.indexOf(v) === -1) {
		visitfunc(v);
		visited.push(v);
		v.neighbors(traverse);
	    }
	});
    }
    
    function insert (key, value) {
	var v = find(key); // insert nutzt O(n) find jedesmal wenn ein key eingefuegt wird? options.duplicates=false first?
	if (!v) {
	    v = new Vertex(key, value);
	    vertices.push(v);
	    return v;
	} 
	return null;
    }
    function update (key, value) {
	var f = find(key);
	if (v) {
	    v.update(value);
	    return value;
	}
	return null;
    }
    
    function remove (v) {
	vertices = vertices.filter(function (vertex) {
	    return v !== vertex;
	});
    }
    function connect (v,w) {
	if (!(v instanceof Vertex)) {
	    v = find(v);
	}
	if (typeof w === "string") {
	    w = find(w);
	}
	if (v instanceof Vertex && w instanceof Vertex) {
	    v.connect(w);
	}
    }
    function disconnect (v,w) {
	if (!(v instanceof Vertex)) {
	    v = find(v);
	}
	if (typeof w === "string") {
	    w = find(w);
	}
	if (v instanceof Vertex && w instanceof Vertex) {
	    v.disconnect(w);
	}    
    }

    function find (v) {	// returnt vertex bei string und index bei objekt (versuch)
	// 1. finde objekt
	if (!(v instanceof Vertex)) {
	    for (var i=0, j=vertices.length; i < j; i++) {
		if (vertices[i].key() === v) return vertices[i];
	    }
	// 2. finde index 
	} else /*if (v instanceof Vertex)*/ {	// __proto__: Vertex.prototype
	    return vertices.indexOf(v);
	}
	// 3. nix gefunden
	return null;
    }
    
    var me = this;
    if (!(me instanceof Graph)) return new Graph;
    me.insert = insert;
    me.update = update;
    me.find = find;
    me.remove = remove;
    me.connect = connect;
    me.disconnect = disconnect;
    me.bfs = bfs;
    me.dfs = dfs;
    return Object.freeze(me);
}

/* Ausprobieren */

function visit1 (v) {
    console.log(this.key() + " ist jetzt connected mit " + v.key());
    console.log(v.key() + " ist uebrigens ein(e) " + v.value());
}

function visit2 (v) {
    console.log("Besuche: " +v.key() + " ("+v.value()+")");
}

var g = new Graph();
console.log("1 ---");

// g.insert gibt den Vertex zurueck, dass wir mit ihm spielen koennen
// Mit find() koennen wir aber auch Vertices finden.
var eddie = g.insert("Edward", "42");
var berlin = g.insert("Berlin", "Ort");
var js = g.insert("JavaScript", "Sprache");
eddie.connect(berlin, "Mein Bezug zum Ort");
eddie.connect(js, "Mein Bezug zur Sprache");
eddie.neighbors(visit1);
console.log("2 ---");
eddie.disconnect(js);
eddie.disconnect(berlin);

var c = g.insert("C++", "Sprache");
var z = g.insert("Zuhause", "Ort");
eddie.connect(c);
eddie.connect(z);
eddie.neighbors(visit1);
console.log("3 ---");

var s = g.insert("Sprache", "Oberbegriff Sprachen");
s.connect(js);
s.connect(c);
s.neighbors(visit1);

console.log("4 --- graph.bfs(eddie, visit2)");
g.bfs(eddie, visit2);
console.log("5 --- sprachen.bfs(visit2)");
s.bfs(visit2);
var doppelg = g.insert("Edward","Neuer Wert");
if (doppelg === null) console.log("g.insert reagiert richtig, Edward ist bereits im Graphen.");
console.log("Update (Eddie vorher): "+eddie.value());
eddie.update("42224222");
console.log("Update (Eddie nachher): "+eddie.value());


console.log("Ich suche und besuche jetzt g.find('Edward') mit visit2");
var eddie_ref = g.find("Edward");
if (eddie_ref) {
    eddie_ref.bfs(visit2);
}

var d1 = g.insert("Start", "Level 1");
var d2 = g.insert("Tief", "Level 2");
var d3 = g.insert("Tiefer1", "Level 3");
var d32 = g.insert("Tiefer2", "Level 3");
var d33 = g.insert("Tiefer3", "Level 3");
var d34 = g.insert("Tiefer4", "Level 3");
var d4 = g.insert("Noch Tiefer1", "Level 4");
var d42 = g.insert("Noch Tiefer2", "Level 4");

s.connect(d1);
d1.connect(d2);
d2.connect(d3);
d2.connect(d32);
d2.connect(d32);
d2.connect(d33);
d2.connect(d34);
d3.connect(d4);
d3.connect(d42);
d42.connect(eddie);
d3.connect(eddie_ref);

s.bfs(function (v) {
    console.log("bfs: Besuche: "+v.key() + " ("+v.value()+")");
});

s.dfs(function (v) {
    console.log("dfs: Besuche: "+v.key() + " ("+v.value()+")");
});
/*
1 ---
Edward ist jetzt connected mit Berlin
Berlin ist uebrigens ein(e) Ort
Edward ist jetzt connected mit JavaScript
JavaScript ist uebrigens ein(e) Sprache
2 ---
Edward ist jetzt connected mit C++
C++ ist uebrigens ein(e) Sprache
Edward ist jetzt connected mit Zuhause
Zuhause ist uebrigens ein(e) Ort
3 ---
Sprache ist jetzt connected mit JavaScript
JavaScript ist uebrigens ein(e) Sprache
Sprache ist jetzt connected mit C++
C++ ist uebrigens ein(e) Sprache
4 --- graph.bfs(eddie, visit2)
Besuche: Edward (42)
Besuche: C++ (Sprache)
Besuche: Zuhause (Ort)
5 --- sprachen.bfs(visit2)
Besuche: Sprache (Oberbegriff Sprachen)
Besuche: JavaScript (Sprache)
Besuche: C++ (Sprache)
g.insert reagiert richtig, Edward ist bereits im Graphen.
Update (Eddie vorher): 42
Update (Eddie nachher): 42224222
Ich suche und besuche jetzt g.find('Edward') mit visit2
Besuche: Edward (42224222)
Besuche: C++ (Sprache)
Besuche: Zuhause (Ort)
bfs: Besuche: Sprache (Oberbegriff Sprachen)
bfs: Besuche: JavaScript (Sprache)
bfs: Besuche: C++ (Sprache)
bfs: Besuche: Start (Level 1)
bfs: Besuche: Tief (Level 2)
bfs: Besuche: Tiefer1 (Level 3)
bfs: Besuche: Tiefer2 (Level 3)
bfs: Besuche: Tiefer3 (Level 3)
bfs: Besuche: Tiefer4 (Level 3)
bfs: Besuche: Noch Tiefer1 (Level 4)
bfs: Besuche: Noch Tiefer2 (Level 4)
bfs: Besuche: Edward (42224222)
bfs: Besuche: Zuhause (Ort)
dfs: Besuche: Sprache (Oberbegriff Sprachen)
dfs: Besuche: JavaScript (Sprache)
dfs: Besuche: C++ (Sprache)
dfs: Besuche: Start (Level 1)
dfs: Besuche: Tief (Level 2)
dfs: Besuche: Tiefer1 (Level 3)
dfs: Besuche: Noch Tiefer1 (Level 4)
dfs: Besuche: Noch Tiefer2 (Level 4)
dfs: Besuche: Edward (42224222)
dfs: Besuche: Zuhause (Ort)
dfs: Besuche: Tiefer2 (Level 3)
dfs: Besuche: Tiefer3 (Level 3)
dfs: Besuche: Tiefer4 (Level 3)
*/

Gewichtete Graphen

Lektion 28

In Lektion 27 kamen einfache gerichtete und ungerichtete Graphen dran. Jetzt in 28 kommen noch WEIGHTS auf die Edges.

Das bedeutet, die Edges kriegen eine Zahl.

Dazu gibt es Algorithmen, inbesondere die Shortest-Path Algorithmen von Dijkstra und Bellman-Ford, letzterer kann negative Gewichte, ersterer nicht.

In MIT 6.006 sind Dijskstra und Bellman-Ford gleich mehrere Lektionen gewidmet.

Um es kurz zu fassen, die Zahlen werden zusammengerechnet zu einer kuerzesten Weg Formel.

Sortieren I

Lektion 29

Mein einfachster Sortieralgorithmus. Ich durchlaufe den Array, und vergleiche jedes Element mit allen Elementen. Ich hatte so einen schonmal geschrieben.

function eddies_sort (array) {
    var tmp, i, j, k;
    for (i=0, j=array.length; i < j; i++) {
	for (k=0; k < j; k++) {
	        if (array[k] > array[i]) {
	    	    tmp = array[i];
	    	    array[i] = array[k];
	    	    array[k] = tmp;
	        }
	}
    }
    return array;
}
eddies_sort([4,6,5,180,11,56,44,8,17]);
// [ 4, 5, 6, 8, 11, 17, 44, 56, 180 ]

Ich behaupte, der lauft garantiert mit Θ(n²), weil ich n mal die n items durchlaufe. Je nachdem, ob die Condition (if) erfuellt ist wird dann Zeit zum Swappen benoetigt. Darum unterschreitet man die maximale Laufzeit gering, wenn die Condition nicht true ist.

Sortieren mit JavaScript

JavaScript hat eine Array.prototype.sort Funktion, die einen Callback hat, der a und b vergleicht und true oder false returns. False true, werden die Werte getauscht, falls false, bleiben sie so.

	    [1,2,3,4].sort(function(a,b){return false;});
	    // 1,2,3,4
	    
	    [1,2,3,4].sort(function(a,b){return true;});
	    // 4,3,2,1
	

So kann man mit einem return true einfach den Array umdrehen, wofuer es aber auch Array.prototype.reverse gibt, dass man es eher nicht braucht.

	[33,44,53,77,22,11].sort (function (a, b) { return a > b; });
	
	// [11,22,33,44,53,77]
	
	[33,44,53,77,22,11].sort (function (a, b) { return a < b; });
	
	// [77, 53, 33, 22, 11]
	
Alphabetisches sortieren
function sort_alpha (w1, w2) {
    var i, b1, b2;
    i = -1
    do {
	i += 1;
	b1 = w1[i]; // (""+w1).charAt(i);
	b2 = w2[i]; // (""+w2).charAt(i);
	if (b1 < b2) return false;
	else if (b1 > b2) return true;
	// falls beide Buchstaben gleich sind,
	// einen Buchstaben weiter gehen.
	// entschieden wird, sobal sie ungleich sind.
    } while (b1 === b2);
}

["Edward", "Edwin", "Edna", "Edzak", "Edzorn", "Edzel", "Eddie", "Edi", "Ede"].sort(sort_alpha);

/*
[ 'Eddie',
  'Ede',
  'Edi',
  'Edna',
  'Edward',
  'Edwin',
  'Edzak',
  'Edzel',
  'Edzorn' ]
*/	

Gut, kommen wir zur Lektion

Insertion Sort.

/*
 Insertion Sort
*/
function insertion (A) {
    var B = A.slice();
    var k, t;
    for (var i = 1, j = B.length; i < j; i++) {
	k = i;
	while (B[k] < B[k-1]) {
	    t = B[k-1];
	    B[k-1] = B[k];
	    B[k] = t;
	    k -= 1;
	}
    }
    return B;
}

var unsorted1 = [234,22,275,55,362,7548,3636,233,34678,25426,23542,11,123,45,6,7,8,346,346,346];

console.log(insertion(unsorted1));
/*
[6,7,8,11,22,45,55,123,233,234,275,346,346,346,362,3636,7548,23542,25426,34678]
*/

Braucht O(n²) bis Ω(n) bei einem bereits sortierten Array.

Man beginnt beim zweiten Element. Vergleicht es mit dem Vorgaenger. Ist es zu tauschen, tauscht man.

Dann geht man weiter. Und immer wenn was mit dem Vorgaenger zu tauschen ist, tauscht man es. Ist es danach nochmal zu tauschen, tauscht man es nochmal, usw.

Dann geht man zum naechsten Element.

Mergesort:

function mergesort (sortable) {
    var m, L, R;
    if (sortable.length < 2) return sortable;
    m = Math.floor(sortable.length/2);
    L = sortable.slice(0,m);
    R = sortable.slice(m);
    return merge(mergesort(L), mergesort(R));
}

function merge (L, R) {
    var M = [];
    var i = 0, j = 0;
    while (i < L.length && j < R.length) {
	L[i] < R[j] ? (M.push(L[i]),i+=1) : (M.push(R[j]),j+=1);
    }
    return [].concat(M, L.slice(i), R.slice(j));
}

var a = [7,342,242,12701,541251,14,235,5188,4829,4528501,2783,2384784];
console.log(mergesort(a));
console.log(mergesort([33,4,5,678,77,65]));
/*
[ 7,
  14,
  235,
  242,
  342,
  2783,
  4829,
  5188,
  12701,
  541251,
  2384784,
  4528501 ]
[ 4, 5, 33, 65, 77, 678 ]
*/

Mergesort ist einer der einfachsten Divide and Conquer Algorithmen. Hier wird der Array solange geteilt, bis er nur 1 Elemente gross ist, dann werden die richtigrum zusammengefuegt, dann wieder die 4 Elemente, dann die 8 Elemente und so weiter. Wenn der while Loop bei i und j zuende ist, bleibt ein Element uebrig. Das gilt es noch hintenanzufuegen.

Man nennt das zwei-Finger Algorithmus. Man hat zwei Zahlenreihen, und den einen Finger hier, und den anderen da, und immer, wenn eine Zahl kleiner als die andere ist, geht das Element weg, und der Finger weiter. Wer zuerst fertig ist, laesst den anderen seine letzte groesste Zahl noch hinzufuegen (das macht die slice Operation).

Sortieren II

Lektion 30

Quicksort

Array.prototype.sort(compfn) ist ein richtiger Quicksort mit C++ Geschwindigkeit, wenn man in JavaScript was zu sortieren hat, sollte man es erstmal damit probieren, wenn der schon reicht.

in-place: Man nimmt zwei extra Parameter l (low) und h (high), die den Teilbereich des Arrays ausdruecken. Man hat einen Pivot rechts (h-1) und einen extra Zeiger m, der links mit l beginnt. Dann durchlaeuft man den Array. Wenn der Wert I[i] kleiner dem Pivot ist, swappt man den Wert I[i] mit I[m] und inkrementiert m darauf. Wenn man durch ist, swappt man den Pivot mit dem aktuellen Wert von m und daraufhin stehen links die kleinen Zahlen und rechts die grossen Zahlen. Der Array ist noch nicht sortiert. Jetzt wendet man quicksort rekursiv auf die beiden Bereiche links und rechts vom Pivot an. Das wiederholt sich dadurch automatisch runter bis auf eine Arraylaenge von 1 oder 0, bei 2 kann man vielleicht noch tauschen, aber dann loest sich der Callstack auch schon auf (alle Funktionen kehren zurueck) und man hat einen sortierten Array.


/* Auchtung, bevor ich mich hier schuldig mache, ich hatte bei der
in-place Variante vorher Wikipedia gelesen und eine Quicksort Demo
mit Pseudocode gesehen. Das hier ist in etwa das Gleiche. */

function quicksort (I, l, h) {
    if (l === undefined && h === undefined) l = 0, h = I.length;
    var it, v, i, m, len;
    if (h - l < 2) return I; 
    else {
	v = I[h-1];
	m = l;
	for (i=l; i < h-1; i++) {
	    if (I[i] < v) {
		it = I[i];
		I[i] = I[m];
		I[m] = it;
		++m;	
	    }
	}
	it = I[h-1];
	I[h-1] = I[m];
	I[m] = it;
	quicksort(I, l, m);
	quicksort(I, m+1, h);
    }
    return I;
}
var a1 = [345345,7347,367377,232,23526,234252626,3423,23456,7888,45363,36737];
var a2 = [0.23545,0.34536,-2354,43363,-8586,7789789.54675, 457457.4574, -5723987];
var a3 = [2,2,3,4,5,3,3,2,2,25,5,66,6,6,6,6,78,64,55,55,55,55,6,6,6,6];
var a4 = [5,5];
var a5 = [2,3,4,1];
var a6 = [23,24,-25,26,27,27,28,28,39,0.2,-99];
var a7 = [0];
var a8 = [];

console.log(quicksort(a1));
console.log(quicksort(a2));
console.log(quicksort(a3));
console.log(quicksort(a4));
console.log(quicksort(a5));
console.log(quicksort(a6));
console.log(quicksort(a7));
console.log(quicksort(a8));
/*
[ 232, 3423, 7347, 7888, 23456, 23526, 36737, 45363, 345345, 367377, 234252626 ]
[ -5723987, -8586, -2354, 0.23545, 0.34536, 43363, 457457.4574, 7789789.54675 ]
[ 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 25, 55, 55, 55, 55, 64, 66, 78 ]
[ 5, 5 ]
[ 1, 2, 3, 4 ]
[ -99, -25, 0.2, 23, 24, 26, 27, 27, 28, 28, 39 ]
[ 0 ]
[]
*/

nicht in-place

- Man nimmt zwei Arrays I1 und I2 und einen Pivot v.

Man zaehlt die Elemente vor dem Pivot durch. Man zaehlt die Elemente nach dem Pivot durch. Alles was kleiner v ist, geht nach I1, alles was groesser oder gleich dem Pivot ist, geht nach I2. Auf I1 und I2 wird quicksort jeweils rekursiv angewandt. Zum Schluss fuegt man alle drei, I1, v und I2 wieder zusammen.

function quicksort (I) {
    var it, v, I1, I2, i, m, len; 
    if ((len=I.length) < 2) return I; 
    else {
	I1 = [];
	I2 = [];
	m = Math.floor(len / 2)
	v = I[m];
	for (i=0; i < m; i++) {
	    it = I[i];
	    if (it < v) I1.push(it);
	    else if (it >= v) I2.push(it);
	}
	for (i=m+1; i < len; i++) {
	    it = I[i];
	    if (it < v) I1.push(it);
	    else if (it >= v) I2.push(it);
	}
	return quicksort(I1).concat(v).concat(quicksort(I2));
    }
}
var a1 = [345345,7347,367377,232,23526,234252626,3423,23456,7888,45363,36737];
var a2 = [0.23545,0.34536,-2354,43363,-8586,7789789.54675, 457457.4574, -5723987];
var a3 = [2,2,3,4,5,3,3,2,2,25,5,66,6,6,6,6,78,64,55,55,55,55,6,6,6,6];
var a4 = [5,5];
var a5 = [2,3,4,1];
var a6 = [23,24,-25,26,27,27,28,28,39,0.2,-99];
var a7 = [0];
var a8 = [];

console.log(quicksort(a1));
console.log(quicksort(a2));
console.log(quicksort(a3));
console.log(quicksort(a4));
console.log(quicksort(a5));
console.log(quicksort(a6));
console.log(quicksort(a7));
console.log(quicksort(a8));
/*
[ 232, 3423, 7347, 7888, 23456, 23526, 36737, 45363, 345345, 367377, 234252626 ]
[ -5723987, -8586, -2354, 0.23545, 0.34536, 43363, 457457.4574, 7789789.54675 ]
[ 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 25, 55, 55, 55, 55, 64, 66, 78 ]
[ 5, 5 ]
[ 1, 2, 3, 4 ]
[ -99, -25, 0.2, 23, 24, 26, 27, 27, 28, 28, 39 ]
[ 0 ]
[]
*/

Die zweite Variante, mein erster Versuch, nutzt drei Arrays, um die Werte, die gleich dem Pivot sind, zu speichern. Dadurch ist nur noch ein Loop noetig.

function quicksort (I) {
    var it, v, V, I1, I2, len; 
    if ((len=I.length) < 2) return I; 
    else {
	V = []; 
	I1 = [];
	I2 = [];
	v = I[Math.floor(len / 2)];
	for (var i=0; i < len; i++) {
	    it = I[i];
	    if (it < v) I1.push(it);
	    else if (it > v) I2.push(it);
	    else V.push(it);
	}
	return quicksort(I1).concat(V).concat(quicksort(I2));
    }
}

/*
[ 232, 3423, 7347, 7888, 23456, 23526, 36737, 45363, 345345, 367377, 234252626 ]
[ -5723987, -8586, -2354, 0.23545, 0.34536, 43363, 457457.4574, 7789789.54675 ]
[ 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 25, 55, 55, 55, 55, 64, 66, 78 ]
[ 5, 5 ]
[ 1, 2, 3, 4 ]
[ -99, -25, 0.2, 23, 24, 26, 27, 27, 28, 28, 39 ]
[ 0 ]
[]
*/

Hier teilt man den Array in der Mitte, das Element nennt man Pivot oder v.

Man nimmt drei neue Arrays. Einen Links, einen Rechts, einen Mitte.

Alles was kleiner als V ist, geht nach Links, alles was v ist in die Mitte, und alles was groesser als V ist geht nach Rechts.

Dann wendet man quicksort rekursiv auf Links und Rechts an und gibt Links + Mitte + Rechts zusammengefuegt zurueck.

Sortieren III

Lektion 32

Ich frage mich gerade, wo die Kapitel hin sind. Ich bin mir sicher, über Bucketsort und Counting Sort bereits geschrieben zu haben. Nun habe ich doch keinen Eintrag in dieser Datei. Sie kommt mir vor, wie eine ältere.

Bucket Sort

function bucketsort (A) {
    var queues = [], Q = [], q;
    var item;
    for (var i = 0, j = A.length; i < j; i++) {
	item = A[i];
	if (!queues[item]) queues[item] = [];
	queues[item].push(item);	
    }	
    for (i = 0, j = queues.length; i < j; i++) {
	if (q=queues[i]) Q = Q.concat(q);
    }
    return Q;
}

var a1 = [456,73,673,323,2,26,346,7,85,8568,68,4,745,7356,36,37];
var a2 = [45345,344,3453,455,3453,7637,37,37,37,7.367346,3446];
var a3 = [23,35,346,454.456,0.345];

console.log(bucketsort(a1));
console.log(bucketsort(a2));
console.log(bucketsort(a3));

/*

Ziffern wie 3463636346 sorgen fuer 3463636346 Elemente im JavaScript Array,
dass macht Bucket Sort so unertraeglich langsam. Man kann damit Objekte mit
gleichen Keys sortieren. In der Art muessen sie aber niedrig sein, damit der
Zugriff schnell genug ist. Bucket Sort soll O(n) sein, aber queues[452353453]
zu finden...Da ist auch ein linearer Algorithmus mehr als nicht zu gebrauchen.

Man kann nur Integer damit sortieren, aber keine 0.3453

[ 2, 4, 7, 26, 36, 37, 68, 73, 85, 323, 346, 456, 673, 745, 7356, 8568 ]
[ 37, 37, 37, 344, 455, 3446, 3453, 3453, 7637, 45345 ]
[ 23, 35, 346 ]

    Mit queues = {} geht es leider auch nicht,
    ohne, dass man keys(qs).sort(fn).forEach(q) schreibt
    
    Object.keys(queues).forEach(function (key) {
	Q = Q.concat(queues[key]);
    });     
[ 2, 4, 7, 26, 36, 37, 68, 73, 85, 323, 346, 456, 673, 745, 7356, 8568 ]
[ 37, 37, 37, 344, 455, 3446, 3453, 3453, 7637, 45345, 7.367346 ]
[ 23, 35, 346, 454.456, 0.345 ]
*/

[ 2, 4, 7, 26, 36, 37, 68, 73, 85, 323, 346, 456, 673, 745, 7356, 8568 ]
[ 37, 37, 37, 344, 455, 3446, 3453, 3453, 7637, 45345 ]
[ 23, 35, 346 ]

Counting Sort


function countingsort (A) {
    var counters = [], i, j, k, l, S = [];
    for (i = 0, l = A.length; i < l; i++) {
	k = A[i];
	j = counters[k];
	counters[k] = j ? j+1 : 1;
    }
    for (i = 0, l = counters.length; i < l; i++) {
	k = counters[i];
	if (typeof k !== undefined) {
	    for (j = 0; j < k; j++) { S.push(i); }
	}
    }
    return S;
}

var a = [ 1, 54, 345, 12, 141, 12, 12, 12, 12, 5365, 55, 5, 26, 23, 1, 1, 3, 12, 12, 5365 ];
var b = [ 1,2,3,4,5,6,7,8,9,0,9,8,7,6,5,4,3,2,1,2,3,4,5,1,2,3,4,6,7,8,9,7,9,7,5,4,3,2];
var c = [ -1, -2, -3, -1, -2, -3, -1, -2, -3, -1, -2, -3 ];

console.log(countingsort(a));
console.log(countingsort(b));
console.log(countingsort(c));

/*
[ 1,1,1,3,5,12,12,12,12,12,12,12,23,26,54,55,141,345,5365,5365 ]
[ 0,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,6,6,6,7,7,7,7,7,8,8,8,9,9,9,9]
[]
*/

Splay Trees

Lektion 34

Splay Trees sind selbstbalancierende Baeume, die eine zig, eine zigzig und eine zigzag Rotationsformel besitzen. Man rotiert die Node durch ihren Parent, oder sogar ihren Grandparent. Je nachdem, ob von links, oder von rechts aus (left child of a left child und right child of a right child) heisst es dann zigzig oder zigzag. Dabei werden die Pointer neu verlinkt.

Durch die Rotation balanciert sich der Baum aus. Und das Gute ist, ich denke, das war der Splay Tree, keys, die oft benoetigt werden, wandern nach oben.

Ich wundere mich gerade, dass dieseS Dokument schon zu Ende ist, obwohl ich meine hier noch einen Nachmittag mehr geschrieben zu haben.

Amortized Analysis

Lektion 35

Komisch, ich war mir sicher, dieses Kapitelchen bereits geschrieben zu haben.

In diesem Kapitel geht es um amortisierende Kosten. In dem Fall wird sogar ein Dollar statt Zeitmodell gewaehlt. Dann wird als Fallbeispiel der HashTable gewahlt. Der Lookup ist praktisch O(1), bis der Table resized werden muss. Und da kommt dann die amoritisierende Analyse ins Spiel. Es wird ausgerechnet, wieviel Zeit man wobei verbraucht, dass man sich Zeit fuers resizen verdienen kann. Es amortisieren sich halt die Kosten.

Das in kurzen Worten. Wie es aussieht darf ich das nochmal machen. Muss ich aber sowieso, weil ich das ja auch lernen will, hehe.

top

Quelle

Quelle fuer die Lektionen: Semesterkurs "Datenstrukturen und Algorithmen", Berkeley Universität von Kalifornien, CS61B, auf YouTube.

Hinzu kommt in Zukunft, MIT 6.006 "Einführung in Algorithmen". Ebenfalls auf YouTube.

Die CS61B Lektionen decken bereits alle wichtigen Datenstrukturen und Algorithmen von 6.006, ebenso, wie die Analyse von Algorithmen dort vorgestellt wird, waehrend sie in 6.006 praktisch, oder mit Randbemerkung, was was ist, vorkommt. Aber dort, wo in CS61B Java unterrichtet wird, geht 6.006 mit Algorithmen weiter.