Willkommen auf meiner Homepage

Tic Tac Toe

Spielanleitung: Der Zufallsgenerator waehlt aus, wer anfängt. Wer anfängt ist X. Man muss in das Feld klicken. Touchen geht da natürlich auch. Wenn das Spiel vorbei ist, kann man neu spielen, und die Schwierigkeit einstellen. Das Gitter muss dazu vollgespielt werden, auch wenn das Unentschieden bereits sicher ist, weil ich das noch nicht programmiert habe.

Relationen

Auf die Art und Weise kann man in ES5 Objekte als Keys verwenden. Aus Langeweile habe ich mir mal eine Datenstruktur einfallen lassen.

In ES6 entspricht das in etwa den Maps, was die Struktur hier kann.

Ich habe sie schonmal ein wenig ausgeforscht. Durch einen Graphen ersetzen kann man sie in jedem Fall. Der Graph ist in etwa gleich strukturiert. Hier ist relation.key === dem Vertex und relation.values === Edges/Adjacency Lists. Darum denke ich mir, dass sich die Struktur Relations nicht weiter durchsetzen wird, weil sie komplett durch vorhandene ersetzt werden kann.

/*
    Relations.
    Eine einfache Datenstruktur um Beziehungen auszudruecken.
    (Kennt keine Mengen, Permutationen, Sequenzen, in keinem Fall)
    Hat einen beliebigen key. Und beliebig viele Values die mit
    dem Key assoziiert sind.
    Ist noch nicht auf Struktur/Geschwindigkeit gebracht, und
    findet mit O(n) bis O(n + m) Schluessel oder Schluessel und Values.
    Kann durch einen Graphen komplett ersetzt werden.
*/

function Relations () {
    "use strict";

    var me = this;
    var relations = [];
    
    function Relation (key, value) {
	var relation = { __proto__: Relation.prototype, constructor: Relation };
	relation.key = key;
	relation.values = [];
	if (typeof value !== "undefined") relation.values.push(value);
	return relation;
    }
    
    function find (k) {
	var v;
	for (var i = 0; i < relations.length; i++) {
	    v = relations[i];
	    if (v && v.key === k) return v;
	}
	return null;
    }
    
    function insert (k, v) {
	var r = find(k);
	if (!r) {
	    r = new Relation(k, v);
	    relations.push(r);
	} else {
	    r.values.push(v);
	}
    }
    
    function contains (k, v) {
	var r = find(k);
	if (v === undefined) return !!r;
	if (r) return !!(r.values.indexOf(v) > -1);
	return null;
    }
    
    function relations (k) {
	var r;
	if (k instanceof Relation) r = k;
	else r = find(k);
	if (r.values.length)
	return r.values.slice();
	else return null;
    }
    
    function remove (k, v) {
	var r = find(k), i;
	if ((i=r.values.indexOf(v)) > -1) {
	    r.values.splice(i,1);
	    return true;
	} 
	return null;
    }
    
    function visit_values(k, f) {
	var r, m;
	if (typeof f === "function") {
	    r = find(k);
	    if (r) return r.values.map(function (v) { return f(v); });
	} else if (typeof k === "function" && arguments.length === 1) {
	    f = k;
	    m = relations.map(function (r) { 
		return f(r);
	    });
	    return m;
	}
	return null;
    }
    
    if (!(me instanceof Relations)) return new Relations;

    me.find = find;
    me.insert = insert;
    me.relations = relations;
    me.visit = visit_values;
    me.contains = contains;
    return Object.freeze(me);
}


var obj1 = { toString: function () { return "[Object eddie]"; }};
var obj2 = { toString: function () { return "[Anderer Key]"; }};

var R = new Relations();
R.insert(obj1);
R.insert(obj2);
R.insert(obj1, "Edward ist toll");
R.insert(obj1, obj2);
R.insert(obj2, obj1);
R.insert(obj2, "Ich rocke auch");
R.insert(obj2, 25235);
R.insert(obj1, true);
R.insert(obj1, false);
R.insert(obj1, null);
R.insert(obj2, 0.53737);
R.insert(obj1, 0xFF);
R.insert(obj1, "file_id..diz is a string");

console.log(R.contains(obj1, 0xFF));

R.visit(function (each) {
    console.log(each);
});


R.visit(obj1, function (v) {
    console.log("Mit obj1 verknuepft ist " + v);
});

R.visit(obj2, function (v) {
    console.log("Mit obj2 verknuepft ist " + v);
});


/*
true
{ constructor: [Function: Relation],
  key: { toString: [Function] },
  values: 
   [ 'Edward ist toll',
     { toString: [Function] },
     true,
     false,
     null,
     255,
     'file_id..diz is a string' ] }
{ constructor: [Function: Relation],
  key: { toString: [Function] },
  values: 
   [ { toString: [Function] },
     'Ich rocke auch',
     25235,
     0.53737 ] }
Mit obj1 verknuepft ist Edward ist toll
Mit obj1 verknuepft ist [Anderer Key]
Mit obj1 verknuepft ist true
Mit obj1 verknuepft ist false
Mit obj1 verknuepft ist null
Mit obj1 verknuepft ist 255
Mit obj1 verknuepft ist file_id..diz is a string
Mit obj2 verknuepft ist [Object eddie]
Mit obj2 verknuepft ist Ich rocke auch
Mit obj2 verknuepft ist 25235
Mit obj2 verknuepft ist 0.53737
*/

Eulertour

Eine Eulertour bedeutet, jede Edge nur einmal zu besuchen, und bei dem Vertex wieder anzuhoeren, wo man angefangen hat. Die Bruecken von Koenigsberg sind das bekannte Beispiel aus der Graphentheorie. Eine Eulertour ist moeglich sagt man, wenn alle Vertices einen geraden Degree haben. Der Grad ist die Anzahl der Edges.

    function has_euler_tour () {
	return vertices.every(function (v) {
	    return v.degree() % 2 === 0;
	});
    }

Matching Problem

Mehr Graphentheorie. In Mathematik für Informatiker wird geheiratet. Und perfekte Paare muessen gebildet werden. Macht garantiert fun.

/*
[
    [
        "Tom",
        "Nicole"
    ],
    [
        "Tom",
        "Sybille"
    ],
    [
        "Nicole",
        "Tom"
    ],
    [
        "Bill",
        "Natascha"
    ],
    [
        "Natascha",
        "Bill"
    ],
    [
        "Mario",
        "Maria"
    ],
    [
        "Maria",
        "Mario"
    ],
    [
        "Sybille",
        "Tom"
    ]
]
[]
[]
*/

    function matches () {
	var vs = vertices.slice();
	var v,w;
	var ms = [];
	for (var i = 0, j = vs.length; i < j; i++) {
	    v = vs[i];
	    if (v) {
		v.adjacents().forEach(function (edge) {
		    if (edge) {
			if (!digraph && edge.vertices[0] !== v) {
			    w = edge.vertices[0];
			}
			else if (edge.vertices[1] !== v) { w = edge.vertices[1]; }
			ms.push([v.key(),w.key()]);
		    }
		});
		v = null;
	    }
	}
	return ms;
    }
    function perfectmatches () {
    "use strict";
	var vs = vertices.slice();	// copy
	var perfects = [], v, w;
	for (var i = 0, j = vs.length; i < j; i++) {
	    v = vs[i];
	    if (v) {
		if (v.degree() === 1) {	// grad 1 hat nur 1 connected
		    if (perfects.indexOf(v) === -1) {
	    		if ((w=v.adjacents[0]) && w.degree() === 1) {
			    perfects.push([v.key(),w.key()]);
			    vs[i] = null;	// streichen
			    vs[vs.indexOf(w)] = null;
			}
		    }
		} 
	    }
	}
	return perfects;
    }
    

/* Matching Problem. */

var g2 = Graph();
g2.insert("Tom");
g2.insert("Nicole");
g2.insert("Bill");
g2.insert("Natascha");
g2.insert("Mario");
g2.insert("Maria");
g2.insert("Sybille");
g2.connect("Tom", "Nicole");
g2.connect("Bill", "Natascha");
g2.connect("Mario", "Maria");
g2.connect("Sybille", "Tom");
/* Eine Art, vertices und edges zu counten */
console.log(JSON.stringify(matches, null, 4));

*/

Numerics

So sieht es aus, wenn ich was nicht richtig mache. Ich zeige nun ein Beispiel wie ich den Rest intuitiv benutze.

    function even (n) {
	return n % 2 === 0;
    }
    function odd (n) {
	return n % 2 !== 0;
    } 
    function divisor (n, m) {
	return n % m === 0;
    }   

Dann kann ich nochmal kurz was voraussagen. Auch zum euklid.

    15 % 6 = 3
    // Der gcd ist 3
    15 % 7 = 1
    // Der gcd ist 1 die beiden sind keine gemeinsamen vielfachen
    18 % 3 = 0
    // teilt genau durch (wie oft ist hier nicht gesagt, nutze 18 / 3, aber das teilt)
    var n = 3; // Mit welchem x man n multiplziert um y zu kriegen? 
    y = 18 / n; // y === 6	
    x = n * y   //  3 * 6 === 18
    x % n = 0   // 18 % 3 === 0
    // x mod n ==== y  ist { n = 3, x = 18, y = 6 }

Nun zum folgenden Code. Ich habe es nicht hingekriegt, die einfache Buchstabenverschluesselung zur Unicodeverschluesselung zu machen. Die Integer sind zu gross fuer JavaScript und die Stringberechnung muss ich mir dann wohl erst mal aneignen. Ich glaube aber jetzt schon Stellen als 10er Potenzen zu sehen, und ausser dem 10er Exponenten noch andere Stringzahl++ Stringzahl davor auch ++ hinzukriegen. Darum wird es gehen, wenn man hier was stabiles schreiben will, was den Text auch wieder herstellt, den es angeblich kodiert.

function inverse (x, y) {
    var x1;
    var n = 0;
    do {
	x1 = y % n;
	if (x*x1 !== 1 % n) {
	    n++;
	}
	
    } while (x1);
    return n;
}

console.log(inverse(127, 133));
console.log(inverse(127,  1024));
console.log(inverse(127, 127));
console.log(inverse(17,14));
console.log(inverse(18, 4));
console.log(inverse(18, 19));
/*
1
1
1
1
1
1
*/

WebGL Tools

Eine triviale Aufgabe, um den Draw Buffer vollzukriegen. Vielleicht kann man mit den Vertices kleine Renderpuffer benutzen. Was auch immer. Finden wir es mal heraus. Was ich dafuer aber jetzt machen muss, um zu wissen, was hier vertices sind und was hier edges sind, und wie der Shader jetzt damit umgeht, lese ich mir die khronos Seiten mal durch.

    var vertexArray = g.getWebGLVertices();
    var edgesArray = g.getWebGLEdges();
    var colorArray = g.aintGotColorsForTheGraph("?");

Wenn ich damit fertig bin, sind die zwei interfaces Geschichte.

Ich denke mir, so kann man aber auch einen Graphen flachmachen. Was mit dem Binaerbaum geht, geht mit jeder anderen Datenstruktur ebenfalls. Sie in einen Array umwandeln. Die Pointer kann ich entweder behalten, oder ihre Daten in den Array extrahieren. Ein Array (Felder) ist eine einfache Struktur fuer jede Menge. In JavaScript sind sie dynamisch (oder typed). In C++ sind sie durch Angabe ihrer Groesse beschraenkt, ausser man zeigt auf einen Speicherbereich und teilt ihn selbst. In Java muss man beim instanziieren des Arrays eine Größe angeben. Linked Lists sind ueblich als ein eigener Ansatz, dynamische Anzahlen zu speichern. Die folgende Funktion ist eine kleine Helfer Funktion, um einen Array aus einer Matrix zu machen. Genaugenommen muss ich meiner function Graph mal ein wenig mehr abverlangen. Darum mache ich das.


function vector(a,b,c) {
    return [a,b,c];
}

function matrix(v1,v2,v3,v4) {
    return [[v1],[v2],[v3],[v4]];
}

function flatten(array) {
    var a, b, i;
    for (i=0; i < array.length; i++) {
	a = array[i];
	if (Array.isArray(a)) {
	    array = array.slice(0, i).concat(flatten(a)).concat(array.slice(i+1));
	} 
    }
    return array;
}

var matze1 = [
    [[1,2,3], [1,2,3], [1,2,3], [1,2,3]], // je eine Reihe
    [[1,2,3], [1,2,3], [1,2,3], [1,2,3]],
    [[1,2,3], [1,2,3], [1,2,3], [1,2,3]],    
    [[1,2,3], [1,2,3], [1,2,3], [1,2,3]]
];

var matze2 = [
    [1,2,3], [1,2,3], [1,2,3], [1,2,3],	// untereinander
    [1,2,3], [1,2,3], [1,2,3], [1,2,3],
    [1,2,3], [1,2,3], [1,2,3], [1,2,3],    
    [1,2,3], [1,2,3], [1,2,3], [1,2,3]
];

console.log(JSON.stringify(flatten(matze1)));
console.log(JSON.stringify(flatten(matze2)));

/*
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3]
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3]
*/

Interessant wird, wenn ich etwas hab, womit ich 3D-Graphen erstellen kann. Vielleicht mit einem 3D-Graphen Programm, wo ich den visuell erzeugen kann. Ich brauche ein Formular. Und einen Canvas. Schon kann das Spass machen, was neues zu schreiben.





syntax.js

Ich hab bemerkt, dass der AST Button bei keiner Function Expression ohne Namen mehr ging. Ich hab meinen letzten Edit von vor ein paar Wochen upgeloaded. Wenn jetzt irgendwas anderes ausfaellt.

Ich hatte zuletzt Token von Tokenizer zum Parser per throw geworfen (Exeptions -von mir- abused). Per Callback kann ich die besser verbinden. Tokenizer und Parser haben als getrennte Module begonnen, und sollen das auch bleiben. Wenn man die aber koppeln kann, dass sie auch schrittweise harmonieren, wenn der Parser ein Token will.

Neu fuer mich ist immernoch das einbauen der Cover Grammatik aus EcmaScript 6. Arrow Functions () => {} haben das Ding, vor dem Pfeil ein ExpressionStatement sein zu koennen. Stand zu Beginn des Monats schon auf dem Plan. War aber so gestoked von Algorithmen und Mathe, oder der OpenCourseWare, dass ich erstmal damit gespielt habe.

Primfaktoren, ggT

Diesmal hat die Wikipedia nachgeholfen. Primfaktoren zu ermitteln ist ja leichter als gedacht. Die Quelle des Algorithmus ist http://openwebschool.de/06/ma/0003/start.html. Ich konnte es mir nicht nehmen, den zu probieren, anstatt zu probieren.

function primefactors ( n ) {
    var pf, factors = [];
    if (n === 1) return n;
    pf = 2;
    while (n > pf) {
	while (n % pf === 0) {
	    n = n/pf;
	    factors.push(pf);	    
	}
	++pf;
    }
    if (n > 1) factors.push(n);
    return factors;
}

function print (n) {
    console.log("Primfaktoren zu "+n+" = " + primefactors(n).join("*"));
}

print(100);
print(1000);
print(3254);
print(47);
print(126234);
print(13426626);
print(33335566);
print(134);
print(2);
print(4);
print(8);
print(16);
print(15);
print(25205);

/*
Primfaktoren zu 100 = 2*2*5*5
Primfaktoren zu 1000 = 2*2*2*5*5*5
Primfaktoren zu 3254 = 2*1627
Primfaktoren zu 47 = 47
Primfaktoren zu 126234 = 2*3*3*7013
Primfaktoren zu 13426626 = 2*3*2237771
Primfaktoren zu 33335566 = 2*11*1019*1487
Primfaktoren zu 134 = 2*67
Primfaktoren zu 2 = 2
Primfaktoren zu 4 = 2*2
Primfaktoren zu 8 = 2*2*2
Primfaktoren zu 16 = 2*2*2*2
Primfaktoren zu 15 = 3*5
Primfaktoren zu 25205 = 5*71*71
*/

Ich nutze in der Funktion n, und aendere n, weil in JavaScript n durch Call-by-Value ausserhalb nichts veraendert wird.

Der Algorithmus funktioniert so: Wenn n 1 ist, gebe ich n zurueck. Dann geht es los mit dem Primfaktor pf = 2. Solange n > pf fuehre ich folgende Schritte durch. Solange sich n % pf === 0 teilen laesst, hat man einen Faktor, und pusht in in die Sammlung (man kann auch einen Counter nehmen, der die Anzahl der Exponenten je pf zaehlt), und teil n durch den Faktor. n wird nun kleiner. Den pf inkrementieren wir. Beispiel pf==2 und pf==4, wenn pf==4 ist, ist durch den Primfaktor pf==2 bereits alles abgedeckt und wir kommen zur 5 und so weiter. Wenn n < dem pf ist, koennen wir aufhoeren. Wenn der Rest (n) aber noch groesser 1 ist, zum Beispiel 1487 (pf(333335566)), dann gehoert er auch nochmal in den Faktorenarray, oder den Exponentencounter.

Man kann bei laengeren Zahlen bereits sehen, dass er so seine Zeit braucht, die Faktoren zu finden. Bei 13Mio und 33Mio macht mein PC zum Beispiel bereits eine kurze Pause.

Das Ausdrucken des Objekts mit Exponentenzaehler ist etwas umstaendlicher. Man muss Object.keys(factors).forEach(function (key) { if (str) str += " * "; str += key + "^" + factor[key]; }); schreiben, ich hab das mal ausprobiert.

Auch der Euklid zum Ermitteln des ggT ist diesmal von der Wikipedia. Ich wollte mich ueber Primfaktorzerlegung informieren und musste diese Pflichtuebung mal absolvieren.

// Der "alte" Euklidische Algorithmus naehert sich durch Subtraktion 
function euklid0 (a, b) {
    if (a === 0) return b;
    while (b !== 0) {
	if (a > b) a = a - b;
	else b = b - a;
    }
    return a;
}
console.log("euklid0(10, 12) = " + euklid0(10,12));
console.log("euklid0(100, 50) = " + euklid0(100,50));
console.log("euklid0(777, 7770) = " + euklid0(777, 7770));
console.log("euklid0(777, 7771) = " + euklid0(777, 7771));
console.log("euklid0(128, 256) = " + euklid0(128, 256));
/*
euklid0(10, 12) = 2
euklid0(100, 50) = 50
euklid0(777, 7770) = 777
euklid0(777, 7771) = 1		// <-- die haben keinen Teiler ueber 1
euklid0(128, 256) = 128
*/

// Der "neuere" Euklidische Algorithmus naehert sich durch Modulus
function euklid (a, b) {
    var t;
    while (b !== 0) {
	t = a;
	a = b;
	b = t % b;	// In ES6 [b,a]=[a,a%b];
    }
    return a;
}
console.log("euklid(10, 12) = " + euklid(10,12));
console.log("euklid(100, 50) = " + euklid(100,50));
console.log("euklid(777, 7770) = " + euklid(777, 7770));
console.log("euklid(777, 7771) = " + euklid(777, 7771));
console.log("euklid(128, 256) = " + euklid(128, 256));
/*
euklid(10, 12) = 2
euklid(100, 50) = 50
euklid(777, 7770) = 777
euklid(777, 7771) = 1
euklid(128, 256) = 128
*/

In diesem Fall bedanke ich mich mal bei der Wikipedia, mir nur noch das auswendig lernen zu ermoeglichen. Ohne den Algorithmus zu begreifen, bringt das mitschreiben nichts.

Numeric Theory II

Large integers koennen in JavaScript als String bearbeitet werden. http://2ality.com/2012/07/large-integers.html. Das passt zu dem folgenden Beispiel aus Mathematik für Informatiker.

Ich versuche mich mal daran, etwas zu verschluesseln. Mit einer Funktion E. Ich verwandele jeden Buchstaben in eine Nummer. [Ich lasse das auf eine Primzahl erweitern weg.] Ich multipliziere mit einer Prim. Ich erhalte eine groessere Nummer. Die gebe ich dann mit der Prim an eine Entschluessungsfunktion D. Die teilt erstmal den Code, und errechnet dann wieder alle Buchstaben aus den Zahlen.

/*  
    Turing Code 1 (nicht direkt)
    Zur Vereinfachung konvertiere ich die Nummern in einen String.
    Ich muss mir unbedingt das Rechnen mit Primzahlen aneignen.
    Ich bring die Summe der Buchstaben nicht noch auf eine Prim (man
    addiert bei diesem Turing Code noch was hinzu, dass es eine Prim ist.
    Dann multipliziert man mit einer anderen Primzahl, dem Schluessel).
    
    Uebrigens. Beim zweiten mal dran gedacht. Hier kann man die Alphabet-
    berechnung weglassen und direkt die Unicode Codeunits verrechnen. In
    diesem Beispiel ist die Breite der Zahlen = 2 Ziffern. Beim naechsten
    mal denk ich sofort dran.
*/
function encrypt(word, key) {
    var m = "", t;
    for (var i=0, j=word.length; i < j; i++) {
	t = ""+(word.charCodeAt(i) - ("A").charCodeAt(0)+1);
	m += t.length === 1 ? "0"+t : t;
	console.log(t);
    }
    return (+m) * key;
}

function decrypt(m1, key) {
    var word = "", m, t;
    m = ""+(m1 / key);
    if ((m.length % 2) !== 0) m = "0"+m;
    for (var i = 0, j=m.length; i < j; i+=2) {
	t = +(m[i] + m[i+1])-1+("A").charCodeAt(0);
	console.log(t);
	word += String.fromCharCode(t);
    }
    return word;    
}

console.log("1. ----");
var e = encrypt("Edward", 127);
console.log(e);
console.log("---");
var d = decrypt(e, 127);
console.log(d);    
console.log("2. ----");
e = encrypt("Gerhold", 111);
console.log(e);
console.log("----");
d = decrypt(e, 111);
console.log(d);        
    
/*    
1. ----
5
36
55
33
50
36
6814227549572
---
69
100
119
97
114
100
Edward
2. ----
7
37
50
40
47
44
36
818629492662396
----
71
101
114
104
111
108
100
Gerhold
*/

Mit der gcd funktion (euklid) weiter oben kann man die Primzahl, mit der verschluesselt wurde leicht ermitteln, sobald wir zwei Nachrichten haben, die damit verschluesselt wurden. Darum wurden public und private key erfunden.

Hier folgt Turing Code V2

Moment. Erstmal sollte ich mit dem gcd nochmal Edward und Gerhold entschluesseln.

/*  
    Tunring V1 update
    Ich habe die Worte * key probiert
    Ich habe die Message * key probiert
    Ich habe sogar eine XOR Verschluesselung probiert
    Ich habe 50 verschiedene Varianten probiert.
    Keine hat funktioniert. Und ich hatte je falsche
    Verschluesselung viele falsche Ergebnisse die korrekt
    waren.
    Ich habe sogar mit dem strict mode eine undefinierte
    Variable eliminiert.
    Dass vergesst ihr alle immer wieder zu tun.
*/
function encrypt(text, key) {
    "use strict";
    var m = "", t;
    for (var i=0, j=text.length; i < j; i++) {
	t = text.charCodeAt(i);
	t = ((""+t).length + "" + t);
	m = m + "" +  t;
	console.log(t);	
    }
    return (+m * key) + "";
}

function decrypt(m, key) {
    "use strict";
    var text = "", t, l = 0, k;
    m = ""+(+m / key);
    for (var i = 0; i < m.length; i++) {
	l = +m[i];
	i = i + 1;
	t = "";
	for (k =0; k < l; k++, i++) {
	    t += ""+m[i];
	}
	text =  text + "" + String.fromCharCode(+t); 
	console.log(t);
    }
    return text;    
}

console.log("1. e----");
var e = encrypt("Edward", 127);
console.log(e);
console.log(" d---");
var d = decrypt(e, 127);
console.log(d);    
console.log("2. e----");
e = encrypt("Gerhold", 111);
console.log(e);
console.log(" d----");
d = decrypt(e, 111);
console.log(d);    
console.log("3. e----");
e = encrypt("Mit Unicode sollte auch ein ganzer Satz gehen", 127);
console.log(e);
console.log(" d---");
d = decrypt(e, 127);
console.log(d);    

/*
1. e----
269
3100
3119
297
3114
3100
3.420237396150759e+23
 d---
.6
100
1
97
e
1undefined
da
2. e----
271
3101
3114
3104
3111
3108
3100
3.011542455688458e+28
 d----
.7
101
1
104
e+2
eh
3. e----
277
3105
3116
232
285
3110
3105
299
3111
3100
3101
232
3115
3111
3108
3108
3116
3101
232
297
3117
299
3104
232
3101
3105
3110
232
3103
297
3110
3122
3101
3114
232
283
297
3116
3122
232
3103
3101
3104
3101
3110
3.5218437457614996e+166
 d---
.7
105
1
32
3e+164undefinedundefined
i 
*/

Schlechter Witz: Das Jobcenter meldet sich mal...

Hurra! Eine Arbeitsgelegenheit. Datenerfasser/in. Klingt ja ganz toll...

Doch Datenerfassung heisst fuer das Arbeitsamt "Stadtbildpflege". Ich sehe die 30% Sanktionen, schon auf mich zukommen. Obwohl ich dringend arbeiten will, damit ich am Ende des Monats keine Pullen mehr sammeln brauche. Und auch diese Obdachlosenzeitungen nicht mehr verkaufen muss, weil die einen schlechteren Ruf haben, als Pullen sammeln.

Ich habe jetzt zwei Jahre darauf gehofft, dass sie ihre Meinung mal aendern. Jetzt haben die die Bedeutung von dem Begriff verwechselt. Ich habe jahrelang von der anderen geredet.

TC39-Notes

RW hat die Minutes vom letzten TC-39 Treffen online gestellt. Da kann man mal lesen, worueber sich unterhalten wird.

Besseren Einblick in die Kommunikation von EcmaScript kann man im Mozilla Mail Archiv von es-discuss kriegen.

  1. 12. Maerz
  2. 13. Maerz
  3. 14. Maerz

Interessante Sachen. Symbols und WeakMaps. Object.observe. RegExp Properties und Object.freeze. (...) "ECMA approval Dezember 2014".

Lost + Found

Hier ist noch ein Suchalgorithmus, ich habe aber vergessen, wann und wozu ich den gemacht habe.

Ich glaube der gehoert zum BinaryHeap, arbeitet auf einem sortierten Array und bewegt sich per divide and conquer fort. Ich werde ihn als bheap.bsearch nach binaryheap.js bewegen.

Im weiteren Gedanken kann man damit bestimmt den quadratischen Algorithmus um zwei Primen zu einer geraden Zahl zu addieren verbessern (weiter unten, naechstes Thema, nach "HashTables"). Ich denke aber mal, da der Callstack das nicht verkraften wird, hoehere Zahlen durchzugehen, muss hieraus erstmal was iteratives gemacht werden. (Was ich fuer quicksort ja ebenfalls noch machen muss. Hier helfen LabelledStatements label: while () {} und break label; bzw. continue label; und [nicht unbedingt] eine var queue = []; um die vorher zu rekurrierenden Ranges fuer das naechste continue festzuhalten. Glaube ich zumindest.

/* Datum 7. Februar 2013, im /home/ Verzeichnis entdeckt. */

function bsearch( what, a, left, right ) {
    if (left > right) return -1;
    var mid = Math.floor((left + right) / 2);
    if (a[mid] === what) return { pos: mid, what: what };
    else if (what < a[mid]) {
	return bsearch(what, a, left, mid-1)
    } else if (what > a[mid]) {
	return bsearch(what, a, mid+1, right);
    }
}

var array = [ "a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"];
console.log(bsearch("a", array, 0, 25));
console.log(bsearch("b", array, 0, 25));
console.log(bsearch("z", array, 0, 25));
console.log(bsearch("y", array, 0, 25));
console.log(bsearch("a", array, 1, 25));
console.log(bsearch("b", array, 1, 25));
console.log(bsearch("k", array, 0, 25));
console.log(bsearch("l", array, 0, 25));
console.log(bsearch("m", array, 10, 25));

/*
{ pos: 0, what: 'a' }
{ pos: 1, what: 'b' }
{ pos: 25, what: 'z' }
{ pos: 24, what: 'y' }
-1
{ pos: 1, what: 'b' }
{ pos: 10, what: 'k' }
{ pos: 11, what: 'l' }
{ pos: 12, what: 'm' }
*/

HashTables

Ich habe dann mal den HashCode verbessert, entsprechend dem Tip aus CS61B (UCBerkeley) habe ich jetzt die gleichen Primzahlen benutzt, weil sie eine sehr gute Verteilung haben sollen. Anders als 26 * erste zwei Character nehme ich hier nun ausserdem das ganze Wort, um einen Code zu berechnen. Danach kommt der trial Code dran, falls der Slot belegt ist. Lag mir die ganze Zeit auf der Zunge. Dachte mir 26* sieht jetzt langsam peinlich aus.

    // Hashcode function
    function hashCode (word) {
	var hashVal = 0;
	for (var i = 0, j= word.length; i < j; i++) {
	    hashVal += (word.charCodeAt(i) - ("a").charCodeAt(0));
	}
	return 127 * hashVal % 16908799;
    }
    // Compression function
    function h (hashCode, trial) {
	trial = trial || 0;
	return (hashCode + trial) % N;
    }

Jetzt gibt es da noch eine Zeile, die aus einem geraden N eine ungerade Zahl macht, indem sie 1 addiert. Ich sollte daraus eine Primzahl machen. Muss mir aber die Divisionsmethode (das Sieb ist zu lahmarschig) beibringen.

∀ n ∈ N+gerade {2,4,6,8,10,...n-2, n}, gilt ∃ x, y ∈ Primzahlen P { 1,3,5,7,... }, für die gilt → x + y = n

Das mit den Symbolen uebe ich noch.

Goldbach: Es gibt eine Vermutung aus dem 18. Jahrhundert (1742), dass gerade Zahlen eine Summe aus zwei Primzahlen sind. Da hat eine bekannte amerikanische mathematische Institution (Globe) sogar einen Preis ausgeschrieben. Sie haben auf dem Papier aber einen Fehler gemacht, dass die Klasse lacht. Sie hatten bei den Beispielen 24 als 11 + 13 angefuehrt, dann 20 als 9 + 11. Nur ist 9 keine Primzahl. 7 + 13 ist richtig. Zum Beispiel.

Und wenn man es ausprobiert, kann man alle geraden Zahlen wahrscheinlich aus zwei Primen berechnen. Ich habe es gestern abend, bis 100 im Kopf versucht und es hingekriegt. Bis dahin ging das. Auf jeden Fall. In Mathe fuer Informatiker, MIT 6.042j, Lektion 2 1 kommt das vor.

Abends fiel mir dann ein Algorithmus zu ein, zuerst fiel mir die Art des Besseren ein, dann schrieb ich erstmal den quadratischen (das ist der einfachste, den man schreiben kann, man probiert einfach jeden mit jedem, nur ist quadratisch gleich unertraeglich bei grossen Quadraten). Den muss ich aber verbessern.

(function evenprimesums () {
    var primes = [ 1, 3, 5, 7, 11, 13, 17, 19 ];
    var sums = [];
    var a, b, c;
    for (var i = 0, j = primes.length; i < j; i++) {
	for (var k = 0, l = primes.length; k < l; k++) {
	    a = primes[i];
	    b = primes[k];
	    c = a + b;
	    sums[c] = a + " + " + b + " = " + c;
	}
    }
    sums.forEach(function (sum) {
	if (sum) console.log(sum);
    });
}());
/*
1 + 1 = 2
3 + 1 = 4
5 + 1 = 6
7 + 1 = 8
7 + 3 = 10
11 + 1 = 12
13 + 1 = 14
13 + 3 = 16
17 + 1 = 18
19 + 1 = 20
19 + 3 = 22
19 + 5 = 24
19 + 7 = 26
17 + 11 = 28
19 + 11 = 30
19 + 13 = 32
17 + 17 = 34
19 + 17 = 36
19 + 19 = 38
*/

Beobachtung: Ein und das gleiche Ergebnis kann aus mehreren Primzahlen berechnet werden. Immer dann, wenn die je einen Partner z.B. zwei oder gleiche n neben sich haben. Die kann man dann tauschen. (Das ist jetzt auch eine Behauptung.)

Ein paar Irrtuemer und eine lange Laufzeit bei der Summe bis 1999998

Ich glaube, ich weiss, warum der Beweis bislang noch nicht fertig ist ;-) Der arme Computer. Update: Ich kürze jetzt den ganzen Text. Gestern habe ich hier ein wenig philosophiert, wie ich den quadratischen Θ(primes²) Algorithmus, um die Summen zu berechnen, verbessere. Einen Teil habe ich bereits. Es ist O(sums * primes²). Hierbei handelt es sich bereits um ein logarithmisches Spiel. Um es genau zu sagen, fehlt mir noch die Übung. Hier ist zum Beispiel ein Logarithmus fuer das Anwachsen der Anzahl von Primzahlen. Es ist also bereits ein log log oder lg log oder irgendwas, was ich vermuten koennte. Den 2er Logarithmus beim Baum habe ich verstanden, aber die anderen sind mir noch nicht leibhaftig. Nach der folgenden Fassung, die fuer jede Summe eine maximale Anzahl von Primzahlen von max 1 bis n-1 hat, ist wohl eine binaersuche auf dem Array eine weitere Beschleunigung. Ist die Summe in array[mid] zu gross, versuche eine andere Stelle, ist sie kleiner nach links, ist sie groesser nach rechts.

(function evenprimesums () {
    var primes = [ 1, 3, 5, 7, 11, 13, 17, 19 ];
    var sums = [];
    var a, b, c;
    var max = primes[primes.length-1] + primes[primes.length-1];
    var sum = 0;
    var index = 0; // beginnt mit primes[0]
    next:
    while (sum < max) {
	sum += 2;
	while (primes[index] < sum-1) ++index; // <--- passe counter an	 	-- gehoert das auch zu log? oder was gibt das in O()
	for (var i=0, j=index; i <= j; i++) {	// <-- das ist noch
	    for (var k=index, l = 0; k >= l; k--) {	// <-- zu ungenau
		a = primes[i];				// <--- 
	        b = primes[k];				// <---
		c = a + b;
		if (c === sum) {
		    sums.push(a + " + " + b + " = " + c);
		    continue next; // <-- stoppe beim ersten ergebnis. Was gibt das. Einen log? Was gibt das mit dem Rest in O()
		}
	    }
	}
	/*
	console.log(sum + " konnte nicht berechnet werden! Die These ist falsch.");
	process.exit();
	*/
    }
    sums.forEach(function (sum) {
	console.log(sum);
    });
}());

/*
1 + 1 = 2
1 + 3 = 4
1 + 5 = 6
1 + 7 = 8
3 + 7 = 10
1 + 11 = 12
1 + 13 = 14
3 + 13 = 16
1 + 17 = 18
1 + 19 = 20
3 + 19 = 22
5 + 19 = 24
7 + 19 = 26
11 + 17 = 28
11 + 19 = 30
13 + 19 = 32
17 + 17 = 34
17 + 19 = 36
19 + 19 = 38
*/

evenprimesums(primes(1000))

Mit der O(s * n²) Routine.


/* sums[sum] = sum; --- 999 sums.length

708 bis start
Alle Zahlen bis 1994 konnten berechnet werden
76 bis Ende
999 ist sums.length
0 bis EndeEnde
*/

/* sums.push(sum); -- 499 sums.length
694 bis start
Alle Zahlen bis 1994 konnten berechnet werden
96 bis Ende
499 ist sums.length
0 bis EndeEnde
*/

Dann versuchte ich das zuerstmal das Ergebnis von evenprimesums(primes(20000000))

Irgendwann hatte ich aufgegeben zu warten. Eben angefuehrte Ergebnisse habe ich mit folgenden Codes geprueft. Das waren aber nur die Summen bis 1994 einschliesslich. Sinnvollerweise konnten alle 2er-Summen mit den Primzahlen bis 19942 bereits berechnet werden. Aber es gilt ja das bis gen unendlich zu beweisen. Oder es zum Beispiel durch Widerspruch zu widerlegen.

/* Mit 999 [jedes 2. Array Feld, sums[sum] = c] */
var sum;
for (var i = 2; i < sums.length; i+=2) {
    sum = sums[i];
    if (sum !== i) {
	console.log(sum + "konnte nicht berechnet werden");
    }
}

/* Oder mit 499 [sums.push(c)] was nur halb soviel Speicher [fuer die Ergebnisse] braucht. */
var sum;
for (var i = 0, s = 2; i < sums.length; i++, s+=2) {
    sum = sums[i];
    if (sum !== s) {
	console.log(sum + "konnte nicht berechnet werden");
    }
}

console.log("Alle Zahlen bis "+max+" konnten berechnet werden."); gab die ander Funktion aus. Und der Falschbeweis blieb aus. sums.length ist uebrigens === max.

Binary Search Tree

Hier wieder ein paar nützliche Funktionen fuer den Binärbaum. Ich bin mit den balancierenden Baeumen (2-3-4, Splay, AVL) noch nicht fertig. Mit den Min- und Maxheaps (komplette Binärbäume als Arrays wo key entweder groesser als beide children ist (maxheap) oder kleiner (minheap)) ebenso noch nicht. Aber ich komme jedesmal ein Stück weiter. Das macht voll Spass. Vielleicht mach ich mir gleich nochmal 6.006 oder CS61B an.


    /* 
    Die Minimum Funktion sucht den kleinsten Schluessel, dazu geht
    sie links runter. Denn die kleineren Keys sind alle auf der linken Seite.
    */

    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;
    }
    
    /* Die Successor Funktion sucht den naechstgroessten Schluessel.
    Das heisst bei der BST Property, links < key < rechts, dass man 
    rechts die node nimmt (node.right), die ist in jedem Fall > key, 
    und dann ihr minimum (links runter) sucht */    
    
    function successor (key) {
	var node;
    	if (!(key instanceof BinaryNode) && key !== null) 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;
    }

    /* Das kann man natuerlich auch umkehren mit maximum und predecessor.
    Wie man das beweisen kann, lerne ich gerade in "Mathematik fuer Informatiker".  */
    
    function maximum (key) {
	var node, max;
    	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 predecessor (key) {
	var node;
    	if (!(key instanceof BinaryNode) && key !== null) 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; // gibt keinen naechstkleineren Key hier. Parent und alles andere sind groesser.
    }
    
    /* Die Funktionen gehoeren zum BST Binary Search Tree, wo die 
       node.links < dem node.key < node.rechts (und das rekursiv jede node so) ist.
    */ 
    

Mathematik für Informatiker

Montag: Genau das habe ich geguckt. 6.042j vom MIT. Ich hatte Mathe für Informatiker bislang nur als ein paar Bücher gehabt und die gerne gelesen. Aber so verstehe ich das blendend.

Wenn meine Frau abends zu Bett geht, gucke ich noch Video. Dadurch kann ich was lernen.

2-3-4 Tree

Den Code habe ich ausgegraben. Muss vom ersten oder zweiten Tag mit CS61B gewesen sein. Ein balancierter Suchbaum, der dem BinarySearchTree aehnelt, aber breiter, und darum niedriger ist. Das andere besondere ist, er balanciert sich selbst. Die insert, remove Routinen sind recht magisch.

    /* 2-3-4 Tree */

    function inorder (visit) {
// gehe links, gucke key 0, [gehe knoten 1, gucke key 1, [gehe knoten 2, gucke key 2]]
	for (var i = 0; i < entries.length; i++) {	
	    if (children[i]) children[i].inorder(visit);
	    if (entries[i]) visit(entries[i]);
	}
// und besuche noch rechts aussen die knoten
	if (children[entries.length]) children[entries.length].inorder(visit);
    }

Hier habe ich ausserdem children (nodes) und entries (enthaelt key und value) gekapselt und ihnen die Traversion zugewiesen. Ich finde die andere Variante, entries und nodes als .property zu haben und im TwoThreeFourTree die Traversionsfunktionen unterzubringen, wie schon im BinaryTree, besser. Ich denke dabei daran, dass ich den 2-3-4 Tree mit zu Beginn probiert haben muss, wie der Code mir sagt, weil ich kurz darauf auf ein anderes Muster (Pattern) umgestiegen bin, das aber schon lange her ist und zwei, drei Tage später war. Sag eine Woche.

    
/*
Das sind die Keys die ich einfuege.

0
3
6
9
12
15
18
21
24
27
30
33
36
39
42
45
48
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38

/* Geordnet sind sie bereits beim inorder traversal. */

{ key: 0, value: 'abcd0' }
{ key: 3, value: 'abcd3' }
{ key: 6, value: 'abcd6' }
{ key: 9, value: 'abcd9' }
{ key: 10, value: 'abcd10' }
{ key: 12, value: 'abcd12' }
{ key: 14, value: 'abcd14' }
{ key: 15, value: 'abcd15' }
{ key: 16, value: 'abcd16' }
{ key: 18, value: 'abcd18' }
{ key: 20, value: 'abcd20' }
{ key: 21, value: 'abcd21' }
{ key: 22, value: 'abcd22' }
{ key: 24, value: 'abcd24' }
{ key: 26, value: 'abcd26' }
{ key: 27, value: 'abcd27' }
{ key: 28, value: 'abcd28' }
{ key: 30, value: 'abcd30' }
{ key: 32, value: 'abcd32' }
{ key: 33, value: 'abcd33' }
{ key: 34, value: 'abcd34' }
{ key: 36, value: 'abcd36' }
{ key: 38, value: 'abcd38' }
{ key: 39, value: 'abcd39' }
{ key: 42, value: 'abcd42' }
{ key: 45, value: 'abcd45' }
{ key: 48, value: 'abcd48' }

/* 
Sieht schonmal vielversprechend aus. Ich garantiere aber, dass ich den Algorithmus noch nicht zu Ende geschrieben habe.
Wenn es drei Keys sind, teile ich auf, fuege den 2. key in die neue Node ein, aber bubble nicht weiter. Soweit ging der
Code bereits. Ich sollte mir jetzt die Lektion zu 2-3-4 mal anmachen, dann kann ich den Rest schreiben. 
 */

Spaeter habe ich dann noch die Funktion von TwoThreeFourNode nach TwoThreeFourTree umbewegt und die gekapselten Propertiers zu . (dot) properties gemacht, weil es die Arbeit erleichtert, beziehungsweise komplexere Arbeit ermoeglicht.


        function inorder (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 (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);
            }    	    
        }        
        

/*

So kann man noch nichts auf die Struktur des Baumes schliessen. Zumindest scheint er sie nicht
irgendwie daemlich einzufuegen oder wild Nodes zu kreieren. Ich habe hier vier Loops, die bis zu
60 Keys einfuegen, Duplikate ausgeschloessen. Ich muss mir das mal im Browser angucken, weil ich 
da einen Debugger habe, der mich die Struktur oeffnen laesst. Damit ich das mal sehe, wie der Baum
bislang aussieht. Und Funktionen wie "height (suche das tiefste Kind und returne die Tiefe)" schreiben
sollte man sich da auch. 

Achtung lange Ausgabe von 180 Zeilen, dann geht es weiter mit der Homepage.

inorder:
node: 0 (abcd0)
node: 1 (abcd1)
node: 2 (abcd2)
node: 3 (abcd3)
node: 4 (abcd4)
node: 5 (abcd5)
node: 6 (abcd6)
node: 7 (abcd7)
node: 8 (abcd8)
node: 9 (abcd9)
node: 10 (abcd10)
node: 11 (abcd11)
node: 12 (abcd12)
node: 13 (abcd13)
node: 14 (abcd14)
node: 15 (abcd15)
node: 16 (abcd16)
node: 17 (abcd17)
node: 18 (abcd18)
node: 19 (abcd19)
node: 20 (abcd20)
node: 21 (abcd21)
node: 22 (abcd22)
node: 23 (abcd23)
node: 24 (abcd24)
node: 25 (abcd25)
node: 26 (abcd26)
node: 27 (abcd27)
node: 28 (abcd28)
node: 29 (abcd29)
node: 30 (abcd30)
node: 31 (abcd31)
node: 32 (abcd32)
node: 33 (abcd33)
node: 34 (abcd34)
node: 35 (abcd35)
node: 36 (abcd36)
node: 37 (abcd37)
node: 38 (abcd38)
node: 39 (abcd39)
node: 40 (abcd40)
node: 41 (abcd41)
node: 42 (abcd42)
node: 43 (abcd43)
node: 44 (abcd44)
node: 45 (abcd45)
node: 46 (abcd46)
node: 47 (abcd47)
node: 48 (abcd48)
node: 49 (abcd49)
node: 50 (abcd50)
node: 51 (abcd51)
node: 52 (abcd52)
node: 53 (abcd53)
node: 54 (abcd54)
node: 55 (abcd55)
node: 56 (abcd56)
node: 57 (abcd57)
node: 58 (abcd58)
node: 59 (abcd59)
preorder:
node: 0 (abcd0)
node: 3 (abcd3)
node: 1 (abcd1)
node: 2 (abcd2)
node: 6 (abcd6)
node: 4 (abcd4)
node: 5 (abcd5)
node: 9 (abcd9)
node: 8 (abcd8)
node: 7 (abcd7)
node: 12 (abcd12)
node: 10 (abcd10)
node: 11 (abcd11)
node: 15 (abcd15)
node: 14 (abcd14)
node: 13 (abcd13)
node: 18 (abcd18)
node: 16 (abcd16)
node: 17 (abcd17)
node: 21 (abcd21)
node: 20 (abcd20)
node: 19 (abcd19)
node: 24 (abcd24)
node: 22 (abcd22)
node: 23 (abcd23)
node: 27 (abcd27)
node: 26 (abcd26)
node: 25 (abcd25)
node: 30 (abcd30)
node: 28 (abcd28)
node: 29 (abcd29)
node: 33 (abcd33)
node: 32 (abcd32)
node: 31 (abcd31)
node: 36 (abcd36)
node: 34 (abcd34)
node: 35 (abcd35)
node: 39 (abcd39)
node: 38 (abcd38)
node: 37 (abcd37)
node: 42 (abcd42)
node: 40 (abcd40)
node: 41 (abcd41)
node: 45 (abcd45)
node: 44 (abcd44)
node: 43 (abcd43)
node: 48 (abcd48)
node: 46 (abcd46)
node: 47 (abcd47)
node: 49 (abcd49)
node: 50 (abcd50)
node: 51 (abcd51)
node: 52 (abcd52)
node: 53 (abcd53)
node: 54 (abcd54)
node: 55 (abcd55)
node: 56 (abcd56)
node: 57 (abcd57)
node: 58 (abcd58)
node: 59 (abcd59)
postorder:
node: 2 (abcd2)
node: 1 (abcd1)
node: 5 (abcd5)
node: 4 (abcd4)
node: 7 (abcd7)
node: 8 (abcd8)
node: 11 (abcd11)
node: 10 (abcd10)
node: 13 (abcd13)
node: 14 (abcd14)
node: 17 (abcd17)
node: 16 (abcd16)
node: 19 (abcd19)
node: 20 (abcd20)
node: 23 (abcd23)
node: 22 (abcd22)
node: 25 (abcd25)
node: 26 (abcd26)
node: 29 (abcd29)
node: 28 (abcd28)
node: 31 (abcd31)
node: 32 (abcd32)
node: 35 (abcd35)
node: 34 (abcd34)
node: 37 (abcd37)
node: 38 (abcd38)
node: 41 (abcd41)
node: 40 (abcd40)
node: 43 (abcd43)
node: 44 (abcd44)
node: 47 (abcd47)
node: 46 (abcd46)
node: 59 (abcd59)
node: 58 (abcd58)
node: 57 (abcd57)
node: 56 (abcd56)
node: 55 (abcd55)
node: 54 (abcd54)
node: 53 (abcd53)
node: 52 (abcd52)
node: 51 (abcd51)
node: 50 (abcd50)
node: 49 (abcd49)
node: 48 (abcd48)
node: 45 (abcd45)
node: 42 (abcd42)
node: 39 (abcd39)
node: 36 (abcd36)
node: 33 (abcd33)
node: 30 (abcd30)
node: 27 (abcd27)
node: 24 (abcd24)
node: 21 (abcd21)
node: 18 (abcd18)
node: 15 (abcd15)
node: 12 (abcd12)
node: 9 (abcd9)
node: 6 (abcd6)
node: 3 (abcd3)
node: 0 (abcd0)
*/

Bit Hacks

Lecture 2 von 6.172 Performance Engineering of Software Systems hat es wohl in sich. Hier bin ich richtig. Wie swappt man zwei Variablen ohne temporäre Dritte ?

var a = 10, b = 12;

a ^= b;		 // a = a ^ b;
b = a ^ b; 	 // b = a ^ b;
a ^= b; 	 // a = a ^ b;

a
// 12
b
// 10

Richtig. Mit XOR. Geiler Trick. In ES6 braucht man den dann dank destructuring assignment aber trotzdem nicht und der neue Einzeiler ist noch viel eleganter. Aber gut zu wissen. Aus solchen Lektionen kann ich noch was lernen.

var x = 10, y = 12;

/* XOR invertiert die Bits */

(x ^ y) ^ y === x
(x ^ y) ^ x === y

Das wollte ich schon immer mal wissen. Der Professor sagte gerade, die ganze Stunde soll soviel Magic drin sein :-) Bis dann.

Ich denke, am Ende der Stunde kann ich mit Shift und Co. umgehen. Wobei direkt zu bemerken sei: In JavaScript wird bei einer Integer-Bitoperation erstmal nach Floating Point konvertiert und dann wieder zurück, darum sind Shift Operationen in JavaScript nicht schneller als eine normale Multiplikation, sondern langsamer. Da bin ich bereits informiert.

var a = 10, b = 12, t;

/* ES 5 mit temp. Variable (wenn man den XOR Trick nicht kennt, wie ich) */

t = a;
a = b;
b = t;

/* ES 6 ohne temp. Variable (destructuring assignment) */

[a,b] = [b,a];

Anderer Trick: Finde die kleinere von zwei Integerzahlen. Der Professor redet direkt von Prozessorzyklen, und wieviele eine Instruktion braucht, und kommt zum Branching, was beim If-else passiert (ich sehe jetzt schon, dass ich mir ne gesunde Hardwarelektion beim MIT holen kann.) Die Loesung sorgt gleichzeitig dafuer, keinen Zweig zu suchen und zu gehen.

 
var r1, r2;

var x = 10, y = 12;

/* Herkoemmlich */

r1 = (x < y) ? x : y;

/* Ohne if-else */

r2 = y ^ ((x ^ y) & -(x < y));

Wusste gar nicht, dass man "x XOR x bitweises-UND minus(x KLEINER y)" schreiben kann, um es mit y zu XORen, hehe. Wie man sieht, geht das aber. Also wenn x < y kommt bei -(x < y) dann -1 raus. Was dann y ^ (x ^ y) = x bedeutet. Sollte aber x ≥ y sein, dann ist -(x < y) === 0 und y ^ 0 ergibt y. Verstehen tu ich das, aber ich denke mir, das gucke ich mir mal zuende an.

Auf die naechste 2er Potenz runden (beliebige Zahl, 64-bit Integer)

var n = 888; // die naechste 2er ist 1024. (geht mit 10, kommt 16 raus, 7 und 8, etc.)
// 888, 23952
--n;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;	
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
++n;
// 1024, 32768

Update: Ich habe einen Bug im Syntaxhighlighter entdeckt. Wer spottet den mit? Richtig. Der Shift Operator >> wird nicht rot dargestellt, was bedeutet, dass er nicht richtig erkannt wurde. Was mich zwar wundert.. Aber vor ein paar Tagen erst habe ich einen Bug entdeckt, wo ein Regex gelesen wurde (ich glaube bei function Graph unten in der bfs oder im levelorder der BST Struktur war das), der durch einbauen der restlichen Grammatik fuer den Regex entfaellt.

Interessanter Unterricht. Ich habe bei 180px 3gp gerade eine Addition nicht erkannt. Aber erstmal gucke ich mir das an. Das ist ja spannend. Was wohl noch kommt?

Spass mit dem Binärbaum.

Es sind unterschiedliche Regeln, die fuer den Maxheap (node.key groesser als der ihrer Kinder), den Minheap (key kleiner als der der Kinder) sowie einen BinarySearchTree gelten (linkes Kind kleiner, rechtes Kind groesser). Aber diese sind einfach zu lernen. Ich habe vorher noch keinen Baum in einen Array verwandelt, oder die Keys entsprechend der Regeln in O(n lg n) sortiert, und umgekehrt, oder diese Technik fuer eine O(lg n) Suche verwendet. Sofern man sie wiederholt, und auch ausprobiert, sind diese Regeln zu lernen, und gar nicht so schwer. Und wie ich das mache? Ich gucke mir eine Lektion an, hoere genau zu und versuche, die verbalen Algorithmusdefinitionen in JavaScript umzuwandeln. Und zuerstmal habe ich mir alle Lektionen angeguckt ;-).

is_minheap: false
is_maxheap: false
is_bst: true

Counting Sort

Gut geeignet fuer viele gleiche Zahlen. Man legt fuer jeden Key einen Zaehler an und gibt hinterher soviele von zurueck, wie man gezaehlt hat. Wenn man Objekte statt Zahlen hat, sollte man Bucket Sort nehmen, weil der Counter natuerlich keine Referenz zum Objekt speichert und die sonst verloren gingen.

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));

/*
Counting Sort ist uebrigens genauso wie Bucket Sort fuer kleine Integer Ranges mit vielen
gleichen Keys gedacht. Nur wird keine Referenz auf die Objekte gespeichert, nur ein Zaehler.
Es gibt aber eine Verbesserung, um die Probleme der beiden Funktionen (hohe Zahlen erfordern
grosse Arrays um den Index aufzunehmen) zu loesen, die werde ich als naechstes versuchen 
herauszufinden, denn es ist interessant, wenn man den Algorithmus aus dem Kopf kann, der sowas 
kann.

[ 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]
[] negative Array Indizes sind nicht moeglich.
*/

Bucketsort

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

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));

/*

Das ist uebrigens richtig, Bucketsort ist fuer kleine 1-n (z.B. 100-200) gedacht,
fuer mehrere Objekte (gern tausende, solange der Speicher halt reicht) mit den gleichen Keys, 
die dann im jeweiligen Bucket landen. Zur Vereinfachung, dass ich nicht so viele Demoobjekte 
erzeugen muss, ist in diesem Falle der key gleich dem item selbst.

Ziffern wie 3463636346 sorgen fuer 3463636346 Elemente im JavaScript Array,
dass macht Bucketsort 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 ist zwar O(q+n) aber queues[452353453]
zu finden, dauert sehr lange fuer den Interpreter. Und das Problem ist bekannt
und gehoert zum Algorithmus. Es gibt da auch eine Loesung fuer, die kenne ich 
zum Zeitpunkt aber noch nicht.

Man kann nur Integer damit sortieren, aber keine 0.3453 Dezimalzahlen.

[ 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 ]
*/

Quicksort

Quicksort, die Dritte. Jetzt habe ich noch die in-place Variante geschafft. Nachdem ich einen Pseudocode ueber die Wikipedia gelesen hatte. Sie braucht zwei extra Parameter, l (low) und h (high). Und de sorgen dafuer, in einem bestimmten Bereich des Arrays zu arbeiten.

In der in-place Variante hat man einen Zeiger m, der bei low beginnt und einen Pivot v, der das letzte Element der Reihe ist. Dann bewegt man sich mit i durch den Array. Sollte das Element bei i kleiner dem Pivot sein, wird mit I[m] geswappt und der Zeiger m inkrementiert. Das muss man sich mit einem Finger als Zeiger auf der Tafel vorstellen, oder auf Papier in mehreren Bildern mit Pfeilen malen.

Wenn man durch den Teil Arrays gegangen ist, und alle Teile eventuell geswappt hat, swappt man noch das Pivot Element mit dem aktuellen Zeiger m. Ab der Stelle sind die geswappten Werte links vom Pivot kleiner, und alles was rechts ist, ist groesser. Das ist aber noch nicht sortiert.

Darum werden links und rechts von v (m) als naechstes rekursiv quicksortiert, und das gleiche Verfahren auf die immer kleiner werdenden Arrayteile angewandt. Nach einigen Rekursionen ist der Array dann sortiert.

Alles wird innerhalb eines Arrays gemacht (darum in-place) und man braucht keine weiteren Arrays. - Die in-place Variante ist natuerlich die (zweit-) schnellste. Jetzt muss ich noch die iterative Fassung knacken. Was rekursiv geht, geht auch als loop. Und das wiederrum spart den Callstack. Was natuerlich noch was schneller ist.

    
function quicksort (I, l, h) {
    if (l === undefined && h === undefined) l = 0, h = I.length;
    var it, v, i, m;
    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 = v;
	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 ]
[]
*/

Man nimmt einen Pivot v (die Mitte des Arrays), einen Array I1, einen I2. Man geht den Array I vor dem Pivot durch und nach dem Pivot durch. Alles was kleiner oder gleich dem Pivot ist, geht nach I1. Alles was groesser ist, geht nach I2. Auf I1 und I2 wird quicksort dann rekursiv angewandt. Danach fuegt man I1, v und I2 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));
    }
}

/*
[ 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 ]
[]
*/

Beim ersten Versuch habe ich drei Arrays benutzt. Und alles was gleich dem Pivot ist in die Mitte gepusht. Anders ist, dass ich nur einen Loop brauche, statt einen vor dem Pivot und einen nach dem Pivot. Anstatt alles was gleich v ist, in M zu pushen, braucht man das hier nur entweder nach links (wird deren groesste Zahl) oder nach rechts (wird deren kleinste Zahl) mit einzusortieren.

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 einen Array in der Mitte. Das Element nennt man Pivot oder v.

-Man nimmt drei neue Arrays. Links, Mitte, Rechts.

-Dann wirft man alles was kleiner v ist links rein, alles was gleich v ist in der Mitte, und alles was groesser ist, nach rechts.

-Dann wendet man quicksort rekursiv auf Links und Rechts an, um sie zu sortieren.

-Man gibt Links, Mitte, Rechts zusammengefuegt wieder zurueck.

Der schnellste Quicksort ist dennoch Array.prototype.sort, weil er nativ und mit C++ Speed arbeiten kann.

Baumrotation

Balancierte Suchbaeume nutzen unter anderem Rotation, um sich zu balancieren. Diese Funktionen rotieren einen Subtree unter einer parent Node so, dass sich die Node darunter (die kann links oder rechts stehen) nach links oder nach rechts runter bewegt, die andere Node hochwandert und der Subtree am anderen Arm der anderen Node haengt. (Am besten ist, man sieht sich eine Abbildung an. Ich muss noch eine malen...)

    function rotate_left (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 rotate_right (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;
	}
    }

var BinaryTree = require("./binarytree").BinaryTree;
var btree = new BinaryTree();
var node1 = btree.insert(2, "Top");
var node2 = btree.insert(1, "Links");
var node3 = btree.insert(3, "Rechts");
btree.print();
btree.leftrotate(node1);
btree.print();
btree.rightrotate(node3);
btree.print();

/*
'BinaryTree': {
{2,'Top'} 
{1,'Links'} {3,'Rechts'} 
}
'BinaryTree': {
{3,'Rechts'} 
{2,'Top'} 
{1,'Links'} 
}
'BinaryTree': {
{2,'Top'} 
{1,'Links'} {3,'Rechts'} 
}
*/

Ist schonmal ein Anfang.

Hashtabellen

Ich arbeite dran. Der folgende Code nutzt den einfachsten HashCode Algorithmus, der moeglich ist. Die sogenannte Divisionsmethode, wo h(k) = k mod N. Es gibt dann noch eine Multiplikationsmethode, wo h(k) = ((a*k) mod 2^w) >> (w-r), die ein paar Bits Bits aus einem grossen, durch die Multiplikation entstandenen, Wort extrahiert, die exakt auf den Array mappen.

Die folgende Variante benutzt Open Addressing mit Probing (Array statt Liste und mehrere Versuche bei Kollision). Es gibt noch eine Fassung mit Linked Lists und Chaining, wo man hinter einem Slot eine Liste hat. Vor- und Nachteile gibt es dazu, und die Open Adressing Variante soll in der Praxis besser sein, hier mal ein Argument, weil die Lookup Zeit einfach konstant (O(1)) ist, waehrend die Linked Lists beim Chaining O(n) braucht.

Was wichtig ist, ist die Groesse der Hashtabelle und auch die Berechnung der Keys auf Primzahlen zu schreiben, weil die Verteilung besser ist, und die Kollisionsgefahr geringer. Ein vielfaches von 2 (jede gerade Zahl) z.B. kann leicht alles in ein Feld mappen. So hat man beim Chaining statt einer Hashtabelle eine Linked List in einem Slot, und der Rest ist leer. Kommt dabei auf die Keys der Items an, die eingefügt werden.

Wer das alles noch nicht kennt, oder auffrischen will, kann sich CS61B und 6.006 auf YouTube angucken. Da gibt es Lektionen zum Hashing, sowie Amortized Analysis (CS61B), was sich mit der Berechnung der Kosten beschaeftigt. Danach sollte man es raus haben.

In CS61B kommen die Primzahlen 127 * ... sowie % 16908799 für die Division in Frage, weil die Zuverlässig sein sollen.

function Hash (N) {	// N sollte am besten eine Primzahl sein, und nie ein vielfaches von 2.
    var me, hashTable, n;
    var deleted = {};
    
    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(entry.key), trial);
	    if (!hashTable[code] || hashTable[code] === deleted) {
		hashTable[code] = entry;
	        ++n;
		return true;
	    } else {
		if (entry.key === w) {
		    return false;
		}
		trial += 1;
	    }
	} 
	return false;
    }
    
    function find (w) {
	var trial = 0;
	while (entry = hashTable[h(hashCode(w), trial)]) {
	    if (entry.key === w) {
		return entry.value;
	    } else {
		trial += 1;
	    }
	}
	return null;
    }
    
    function remove (w) {
	var trial = 0;
    	var code; 
    	while (entry = hashTable[code=h(hashCode(w), trial)]) {
	    if (entry.key === w) { 
		hashTable[code] = deleted;
    	        --n;
    		return true;
    	    } else {
    		trial += 1;
    	    }
    	}
	return false;
    }
    
    function hashCode (word) {
	var hashVal = 0;
	for (var i = 0, j= word.length; i < j; i++) {
	    hashVal += (word.charCodeAt(i) - ("a").charCodeAt(0));
	}
	return 127 * hashVal % 16908799;
    }

    function h (hashCode, trial) {
	trial = trial || 0;
	return (hashCode + trial) % N;
    }
    
    me = this;
    if (!(me instanceof Hash)) return new Hash(N);
    if (N % 2 === 0) N += 1;
    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)");
console.log(dict.remove("aa"));
console.log(dict.find("aa"));
console.log(dict.remove("aa"));
dict.insert("aa", "lets look");
console.log(dict.find("aa"));

if (!dict.insert("aa", "lets look2")) {
    console.log("aa exists");
}

console.log(dict.find("aa"));
/*
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 = 2159
lec compressed = 119
null
4items = 0.02 of N (255)
true
null
false
lets look
aa exists
lets look
*/

JavaScript

Auf Stackoverflow findet man eine Antwort zu "Big O of JavaScript Arrays".

  1. Zugriff (access) - O(1)
  2. Einfügen (insert) - Amortized O(1)
  3. Anhängen (append) - Amortisiert O(1)
  4. Vorne einfügen (prepend) - O(n), weil alle Indizes reorganisiert werden (*)
  5. Löschen (delete) - Amortisierte O(1). ABER O(n) wenn man z.B. splice benutzt und alle Indizes reorganisiert werden.
  6. Swapping - O(1)

(Quelle: Stackoverflow: Big O of JavaScript Arrays)

In CS61B (Berkeley Uni, auf YouTube) gibt es die Lektion "Hash Tables" und die Lektion "Amortized Analysis". Wenn man die nimmt, hat man die genauen Kosten der Hashtable Operationen zusammen und versteht dann auch, wie sich das oder was sich da amortisiert.

Sortieralgorithmen

Mergesort, Divide and Conquer, die erste. Teile den Array solange entzwei, bis man die Haelften geordnet zusammenfuehren kann. Man ordnet erst zwei Elemente, dann zwei geordnete Arrays, mit zwei Elementen, dann mit 4 Elementen Links und Rechts, dann fuegt man die solange zusammen (man guckt was groesser ist, L[i] oder R[j] und fuegt sie zusammen. Der Professor nannte ihn zwei-Finger Algorithmus und zeigte mit zwei Fingern wo der Zeiger ist.

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 M.concat(L.slice(i), R.slice(j));
}

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

/*
[7,14,235,242,342,2783,4829,5188,12701,541251,2384784,4528501]
[4,5,33,65,77,678]
*/

Jeder fängt mal klein an. Hier ist mein Insertionsort.

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]) {	// ab ES6: [B[k],B[k-1]]=[B[k-1],B[k]]
	    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] 
*/

Der funktioniert so, man beginnt beim zweiten Element des Arrays und guckt zurueck. Ist es zu tauschen, tauscht man es. Man geht zum zweiten, guckt, tauscht, geht zum dritten, guckt, geht zum vierten, tauscht. Muss mehr als einmal getauscht werden, tauscht man solange zurueck, bis das Element richtig einsortiert ist. Der Algorithmus hat eine Laufzeit von O(n²).

Spass mit dem Graphen

Um schnell zu zeigen, wofür ein Graph gut ist, hier mal schnell die Graphenstruktur mit 5 Punkten gefuellt, und auf dem Canvas gemalt, waehrend ich mit einer einfachen Traversion den Pfad lang gehe.

Wenn das DOMContentLoaded Event gefeuert wird, zeichne ich ein Haus. Die Punkte hole ich aus dem Graphen. Hinterher erzeugte ich noch einen Stern. Im selben Graphen. Nur ist kein Vertex des Sterns mit dem des Hauses verbunden. Man muss, um sie zu besuchen, zumindest je einen Vertex von haben.

Die Struktur Graph ist weiter unten zu finden. Sie ist gerade erst angebrochen, wie man sieht. Aber wie man sieht, kann man damit erstaunliche Sachen machen, und nicht nur Freunde connecten. Ich kann mir die ganze Welt (das Inventar) eines Computerspiels bereits im Graphen vorstellen. Und noch mehr.

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();
    /*
   p2
p1/  \p3
  |   |
p5 __ p4
    */
    
    // Das Haus
    
    var p1 = g.insert("p1",Point(10,40)); // nutze v.value()
    var p2 = g.insert("p2",Point(50,20)); // und v.key() hat "p1"
    var p3 = g.insert("p3",Point(90,40)); // Beispiel 1
    var p4 = g.insert("p4",Point(90,90));
    var p5 = g.insert("p5",Point(10,90));
    p1.connect(p2);
    p2.connect(p3);
    p3.connect(p4);
    p4.connect(p5);
    p5.connect(p1);
    context.moveTo(p1.value().x, p1.value().y);
    // Ich male ein Haus mit dfs-visit
    g.dfs(p1, function (v) {
	var point = v.value();
	context.save();
	context.lineTo(point.x, point.y);
	context.stroke();
	context.restore();
    });
    // der erste Knoten ist bereits besucht, ich muss die Linie
    // vom letzten zum ersten noch nachsetzen.
    context.save();
    context.lineTo(p1.value().x, p1.value().y);
    context.stroke();
    context.restore();

    // Und ein Stern (im gleichen Graphen gespeichert)
    // s1 ist oben, und ich gehe im Uhrzeigersinn durch
    // Ich habe Kaestchenpapier 10*10 Quadrate genommen.
    // Und mit Kuli kurz aufgemalt.

    var s1 = g.insert(Point(150,15)); // nutze v.key()
    var s2 = g.insert(Point(160,40)); // statt "s1", .. zu speichern
    var s3 = g.insert(Point(180,40)); // Beispiel 2
    var s4 = g.insert(Point(165,55));
    var s5 = g.insert(Point(170,80));
    var s6 = g.insert(Point(150,65));
    var s7 = g.insert(Point(130,80));
    var s8 = g.insert(Point(135,55));
    var s9 = g.insert(Point(120,40));
    var s10 = g.insert(Point(140,40));

    s1.connect(s2);
    s2.connect(s3);
    s3.connect(s4);
    s4.connect(s5);
    s5.connect(s6);
    s6.connect(s7);
    s7.connect(s8);
    s8.connect(s9);
    s9.connect(s10);
    s10.connect(s1);
    
    context.moveTo(s1.key().x, s1.key().y);
    g.dfs(s1, function (v) {
	var point = v.key();
	context.save();
	context.lineTo(point.x, point.y);
	context.stroke();
	context.restore();
    });
    context.save();
    context.lineTo(s1.key().x, s1.key().y);
    context.stroke();
    context.restore();

    
}, false);

EcmaScript next

Montag: Das neue EcmaScript.next draft ist online. Lest selbst.

Changes include:

Algorithmen

Dem Binaerbaum und Binaerheap habe ich ein wenig hinzugefuegt. Die insert Operation des Trees sollte nun einer BinaerHeap Property folgen. In dem Fall sind links die Kids kleiner als der key, und rechts sind sie groesser. Die find und insert Operation gehen rekursiv vor. insert gibt null zurueck, dann kommt update, usw. fuer den queue beim levelorder nehme ich einen Array statt function Queue. Ich habe die ueppigen und haesslichen bnode Operationen entfernt. In JS lohnt das nicht, weil das extrem lahm wird. Ausserdem waren die häß und stören beim ausprobieren.

Weiter unten gibt es function Queue, die eine Warteschlange mit verketteter Liste erzeugt. Um in JavaScript aber schneller Datenstrukturen und Algorithmen zu schreiben, muss man auf Tricks zurueckgreifen, und moeglichst die internen Methoden direkt rufen. Das sind im Falle des Queues Array.prototype.shift() fur dequeue des ersten Elements, und Array.prototype.push() fuer das Enqeueing (hinten Anstellen).

    /* 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
    */

Mathematik für Informatiker (Hatte ich als Buch schon einige von) ist auch cool. Der Kerl erklaert die Symbole und ich muss nur vor und zurueckspulen und mir die merken. Dann kriege ich die Texte auch endlich gelesen. Ich denke mal, das werde ich mehrmals machen, bevor ich in ein paar Monaten dann mal andere Fächer ausprobiere.

Montag: Ich mach Dienstag wohl mit CS61B weiter. Der Ausflug zum MIT ist vorbei. Mein Schatz meinte, ich habe sehr lange Video geguckt, und sie haette alleine vorm Video gesessen. Nur die Kaninchen waren bei ihr. Was mir sehr leid tat. Und ich habe ihr das erzaehlt und jetzt mache ich, was ich wollte, und das Semester von der Berkeley Uni fertig. Ich wollte die Datenstrukturen und Algorithmen, die DORT vorkommen, machen. Am MIT habe ich mir das Gleiche doppelt erklaeren lassen, und ich muss sagen, von der Berkeley schon eine Menge gewusst zu haben. Auf jeden Fall werden wir das bald in den neuen Docs, die ich im Laufe der Zeit schreibe, sehen, denn das hat sich bisher wirklich gelohnt und lohnt sich auch weiter. Update: Ich habe zu viele Kommata in den Sätzen. UpUpDate: Und zu viele Vorandkuendigungen. Das ist ja voll laut. Die Datenstrukturen und Algorithmen verbessere ich von Zeit zu Zeit ebenfalls.

var start = Date.now();

/* 
    Interessant ist der high precision number computing Teil im 6.006 Kurs.
    Die Primzahlen sollte ich mir allgemein mal wieder aneignen. 
*/

var isprime = (function () {
    var min = 2;
    var max = 100000;
    var teilbar = [];
    function sieb () {
	for (var i = min; i < max+1; i++) {
	    if (i % 2 === 0) teilbar[i] = true;
	    else if (teilbar[i] !== true) {
		for (var j = i*i; j < max+1; j += i) {
		    teilbar[j] = true;	// wikipedia hat sieb des erathostenes mit pseudocode
	        }
	    }
        }
    }
    sieb();
    function istprim (n) {
	if (n > max) { min = max; max = n; sieb(); }
	return !teilbar[n];
    }
    return istprim;
}());

/* Dennoch erfuellt es seinen Zweck */

function primes (n) {
    var result = [];
    for (var i = 0; i < n; i++) {
	if (isprime(i)) result.push(i);
    }
    return result;
}

console.log("Siebe primzahlen bis 100.000 in " + ((Date.now() - start) / 1000)+ " Sekunden.");
console.log("bis 100: "+primes(100));
console.log("bis 10: "+primes(10));
console.log("bis 1000: "+primes(1000));

/*

Siebe primzahlen bis 100.000 in 0.187 Sekunden.
bis 100: 1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
bis 10: 1,3,5,7
bis 1000: 1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997

*/    

MIT 6.006: In Lektion 1 wird zu allererst das triviale Problem, peaks (Spitzen, Gipfel) zu finden, angesprochen. Muss man mal gemacht haben. Ein Peak ist ein Peak, wenn er ≥ seinem linken und rechten Nachbarn ist. Im Falle, dass er das letzte oder erste Element ist, pr&uum;ft man nur den einen Nachbarn, ist der wieder kleiner, ist man ein Peak und spitze. Auch wenn man von 1..7 durchzaehlt, ist 7 dann eben ein Peak. Ist ja wohl logisch. Oder mit JavaScript if ((i===0 && c <= b) || (i === j-1 && a <= b) || (b >= a && b >= c)) peaks.push(b);

function findpeaks (array) {
    var a, b, c, peaks = [];
    for (var i=0, j=array.length; i < j; i++) {
        a = array[i-1]; // keine arrayindexoutofboundsexceptions wie in java
        b = array[i];
        c = array[i+1]; // nur undefined, wenn man in js ueber length rausgeht
        // nur noch "[a,b,c] = array.slice(i-1, 3);" in ES6 
	if ((i === 0 && c <= b) ||	 // linker rand
	(i === j-1 && a <= b) || 	// rechter rand
	(b >= a && b >= c)) peaks.push(b); // mittendrin
    }
    return peaks;
}
console.log(JSON.stringify(findpeaks([1,2,3,4,5,6,7,8,9]))); 
console.log(JSON.stringify(findpeaks([6,5,3,4,9,2,7,1,5])));
/*
[9]
[6,9,7,5]
*/

Samstag: Videotip. MIT 6.006 Introduction to Algorithms Fall 2011. Ein aktuelles Semester. Eine ideale Ergänzung zu CS61B. Als wär man zu zwei Unis geheizt. 25 mathematisch, softwareorientierte Lektionen plus Recitations. (Hab fast meine 5GB Traffic aufgebraucht, um mir die ersten 24 Lektionen mal zuzulegen. Das sind bei 180px schon 129MB pro Stück. Sonst haette ich noch das Mathesemester genommen, dann gibt es da noch maechtig Auswahl. Aber das ist wieder so eine Lebensaufgabe ;))

/* fib_l(n) mit bottom-up Loop statt Rekursion. Keine Kosten fuer den Callstack. */

function fib_l(n) {
    if (fib_l.prototype[n]) return fib_l.prototype[n];
    for (var k = 1; k < n+1; k++) {
	if (k <= 2) fib_l.prototype[k] = 1;
	else fib_l.prototype[k] = fib_l.prototype[k-1]+fib_l.prototype[k-2];
    }
    return fib_l.prototype[n];
}	

/* fib_m(n) Mit Memoizer */ 

function fib_m(n) {
    if (fib_m.prototype[n]) return fib_m.prototype[n];
    if (n <= 2) return fib_m.prototype[n] = 1;
    return (fib_m.prototype[n] = fib_m(n-1) + fib_m(n-2));
}

/* fib(n) Ohne Memoizer */

function fib(n) {
    /*if (n <= 2) return 1;
    else return fib(n-1) + fib(n-2);*/
    return (n <= 2) ? 1 : fib(n-1)+fib(n-2);
}

/*

Reine Rekursion

fib(10): 55
fib(11): 89
fib(12): 144
fib(13): 233
time: 89
fib(30): 832040
fib(31): 1346269
fib(32): 2178309
fib(33): 3524578
fib(40): 102334155
time: 40065

Rekursion mit Memo

fib_m(10): 55
fib_m(11): 89
fib_m(12): 144
fib_m(13): 233
time: 5
fib_m(30): 832040
fib_m(31): 1346269
fib_m(32): 2178309
fib_m(33): 3524578
fib_m(40): 102334155
time: 2

Loop mit Memo

fib_l(10): 55
fib_l(11): 89
fib_l(12): 144
fib_l(13): 233
time: 5
fib_l(30): 832040
fib_l(31): 1346269
fib_l(32): 2178309
fib_l(33): 3524578
fib_l(40): 102334155
time: 1

*/

Datenstrukturen

Freitag: Ich hab immernoch keinen vernünftigen Graphencode geschrieben. Das hier läuft schonmal von Anfang an. Schonmal eine Grundlage. (*)

(*) Bevor ich was eigenes erfinde, kann ich dann mit den vorhandenen Algorithmen weitermachen. Tausche den Code dann einfach aus. Update: Habe schonmal ein wenig weitergemacht.

/*
    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) {
	    var weight;
	    adjacents.some(function (edge) {
		if ((!digraph && edge.vertices[0] === v) || edge.vertices[1] === v) {
		    return (weight = edge.weight), true;
		}
		return false;
	    });
	    return weight;

	}
	function set_weight (v, weight) {
	    adjacents.forEach(function (edge) {
		if ((!digraph && edge.vertices[0] === v) || 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, visit) {

	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) {
		visit(node);
	    });
	});
    }
    
    function dfs (vertex, visit) {
	var visited = [];
	visit(vertex);
	visited.push(vertex);
	vertex.neighbors(function traverse (v) {
	    if (visited.indexOf(v) === -1) {
		visit(v);
		visited.push(v);
		v.neighbors(traverse);
	    }
	});
    }
    
    function insert (key, value) {
	var v = find(key); 
	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 (!(v instanceof Vertex)) {
	    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 (!(v instanceof Vertex)) {
	    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)
*/

Dann die fünf Minuten heute Mittag, einen Binärbaum in einen Binärheap flachzulegen.


var BinaryTree = require("./binarytree").BinaryTree;
var BinaryNode = require("./binarytree").BinaryNode;
if (typeof exports !== "undefined") {
    exports.BinaryHeap = BinaryHeap;

}
/*
    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);
}

Hier das Program, womit das kurz ausprobiert wurde, einen BinaerBaum in eine BinaerHalde zu verwandeln.


var BinaryTree = require("./binarytree").BinaryTree;
var BinaryNode = require("./binarytree").BinaryNode;
var BinaryHeap = require("./binarytree").BinaryHeap;

var tree = new BinaryTree(
    new BinaryNode("0","Ich bin die Wurzel", null,
	new BinaryNode("1","Ich bin Links",  null, new BinaryNode("2","ll"), new BinaryNode("2","lr")),
	new BinaryNode("1","Ich bin Rechts", null, new BinaryNode("2","lr"), new BinaryNode("2","rr"))
    )
);
console.dir(tree);
function show_data (node) {
    console.log("key='"+node.key+"', value='"+node.value+"'");
}
console.log("inorder:");
tree.inorder(show_data);
console.log("postorder:");
tree.postorder(show_data);
console.log("HEAPS:");
var heap = new BinaryHeap();
var array = heap.heap(tree);
heap.each(function (item) {
    console.log(item);
});
console.dir(array);
var btree = new BinaryTree();
for (var i = 0; i < 26; i++) {
    btree.insert(i+1, String.fromCharCode("A".charCodeAt(0)+i));
}
console.log("*************** btree inorder");
btree.inorder(show_data);
console.log("*************** btree postorder");
btree.postorder(show_data);
console.log("*************** btree preorder");
btree.preorder(show_data);
btree.print();
btree = new BinaryTree();
var node = new BinaryNode(10.1, "das bin ich");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(10.2, "das bist du");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(10.3, "das ist er");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(10.123, "das ist .123");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(10.2223, "das ist .2223");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(10.2123, "das ist .2123");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(8, "das ist 8");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(7, "das ist 7");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(6, "das ist 6");
btree.insert(node);
console.log(btree.height(node));
node = new BinaryNode(8, "das ist 8");
btree.insert(node);
console.log(btree.height(node));
btree.update(8, "war8");
btree.inorder(function (node) { console.log(node.key+" "+node.value); });
console.log("print---");
btree.print();
console.log("---print");
btree.postorder(function (node) {console.log(node.key+" "+node.value); });
btree.preorder(function (node) {console.log(node.key+" "+node.value); });
/*    
{ root: [Function: getset_root],
  preorder: [Function: preorder],
  inorder: [Function: inorder],
  postorder: [Function: postorder],
  levelorder: [Function: levelorder],
  find: [Function: find],
  insert: [Function: insert],
  update: [Function: update],
  remove: [Function: remove],
  rotleft: [Function: rotatel],
  rotright: [Function: rotater],
  print: [Function: print],
  height: [Function: height],
  min: [Function: _min],
  max: [Function: _max],
  ismaxheap: [Function: ismaxheap],
  isminheap: [Function: isminheap] }
inorder:
key='2', value='ll'
key='1', value='Ich bin Links'
key='2', value='lr'
key='0', value='Ich bin die Wurzel'
key='2', value='lr'
key='1', value='Ich bin Rechts'
key='2', value='rr'
postorder:
key='2', value='ll'
key='2', value='lr'
key='1', value='Ich bin Links'
key='2', value='lr'
key='2', value='rr'
key='1', value='Ich bin Rechts'
key='0', value='Ich bin die Wurzel'
HEAPS:
0
1
2
2
1
2
2
[ { key: '0',
    value: 'Ich bin die Wurzel',
    parent: null,
    left: 
     { key: '1',
       value: 'Ich bin Links',
       parent: [Circular],
       left: [Object],
       right: [Object] },
    right: 
     { key: '1',
       value: 'Ich bin Rechts',
       parent: [Circular],
       left: [Object],
       right: [Object] } },
  { key: '1',
    value: 'Ich bin Links',
    parent: 
     { key: '0',
       value: 'Ich bin die Wurzel',
       parent: null,
       left: [Circular],
       right: [Object] },
    left: 
     { key: '2',
       value: 'll',
       parent: [Circular],
       left: null,
       right: null },
    right: 
     { key: '2',
       value: 'lr',
       parent: [Circular],
       left: null,
       right: null } },
  { key: '2',
    value: 'll',
    parent: 
     { key: '1',
       value: 'Ich bin Links',
       parent: [Object],
       left: [Circular],
       right: [Object] },
    left: null,
    right: null },
  { key: '2',
    value: 'lr',
    parent: 
     { key: '1',
       value: 'Ich bin Links',
       parent: [Object],
       left: [Object],
       right: [Circular] },
    left: null,
    right: null },
  { key: '1',
    value: 'Ich bin Rechts',
    parent: 
     { key: '0',
       value: 'Ich bin die Wurzel',
       parent: null,
       left: [Object],
       right: [Circular] },
    left: 
     { key: '2',
       value: 'lr',
       parent: [Circular],
       left: null,
       right: null },
    right: 
     { key: '2',
       value: 'rr',
       parent: [Circular],
       left: null,
       right: null } },
  { key: '2',
    value: 'lr',
    parent: 
     { key: '1',
       value: 'Ich bin Rechts',
       parent: [Object],
       left: [Circular],
       right: [Object] },
    left: null,
    right: null },
  { key: '2',
    value: 'rr',
    parent: 
     { key: '1',
       value: 'Ich bin Rechts',
       parent: [Object],
       left: [Object],
       right: [Circular] },
    left: null,
    right: null } ]
*************** btree inorder
key='1', value='A'
key='2', value='B'
key='3', value='C'
key='4', value='D'
key='5', value='E'
key='6', value='F'
key='7', value='G'
key='8', value='H'
key='9', value='I'
key='10', value='J'
key='11', value='K'
key='12', value='L'
key='13', value='M'
key='14', value='N'
key='15', value='O'
key='16', value='P'
key='17', value='Q'
key='18', value='R'
key='19', value='S'
key='20', value='T'
key='21', value='U'
key='22', value='V'
key='23', value='W'
key='24', value='X'
key='25', value='Y'
key='26', value='Z'
*************** btree postorder
key='26', value='Z'
key='25', value='Y'
key='24', value='X'
key='23', value='W'
key='22', value='V'
key='21', value='U'
key='20', value='T'
key='19', value='S'
key='18', value='R'
key='17', value='Q'
key='16', value='P'
key='15', value='O'
key='14', value='N'
key='13', value='M'
key='12', value='L'
key='11', value='K'
key='10', value='J'
key='9', value='I'
key='8', value='H'
key='7', value='G'
key='6', value='F'
key='5', value='E'
key='4', value='D'
key='3', value='C'
key='2', value='B'
key='1', value='A'
*************** btree preorder
key='1', value='A'
key='2', value='B'
key='3', value='C'
key='4', value='D'
key='5', value='E'
key='6', value='F'
key='7', value='G'
key='8', value='H'
key='9', value='I'
key='10', value='J'
key='11', value='K'
key='12', value='L'
key='13', value='M'
key='14', value='N'
key='15', value='O'
key='16', value='P'
key='17', value='Q'
key='18', value='R'
key='19', value='S'
key='20', value='T'
key='21', value='U'
key='22', value='V'
key='23', value='W'
key='24', value='X'
key='25', value='Y'
key='26', value='Z'
'BinaryTree': {
{1,'A'} 
{2,'B'} 
{3,'C'} 
{4,'D'} 
{5,'E'} 
{6,'F'} 
{7,'G'} 
{8,'H'} 
{9,'I'} 
{10,'J'} 
{11,'K'} 
{12,'L'} 
{13,'M'} 
{14,'N'} 
{15,'O'} 
{16,'P'} 
{17,'Q'} 
{18,'R'} 
{19,'S'} 
{20,'T'} 
{21,'U'} 
{22,'V'} 
{23,'W'} 
{24,'X'} 
{25,'Y'} 
{26,'Z'} 
}
1
2
3
3
4
5
2
3
4
1
6 das ist 6
7 das ist 7
8 war8
10.1 das bin ich
10.123 das ist .123
10.2 das bist du
10.2123 das ist .2123
10.2223 das ist .2223
10.3 das ist er
print---
'BinaryTree': {
{10.1,'das } 
{8,'war8'} {10.2,'das } 
{7,'das ist} {10.123,'da} {10.3,'das } 
{6,'das ist} {10.2223,'d} 
{10.2123,'d} 
}
---print
6 das ist 6
7 das ist 7
8 war8
10.123 das ist .123
10.2123 das ist .2123
10.2223 das ist .2223
10.3 das ist er
10.2 das bist du
10.1 das bin ich
10.1 das bin ich
8 war8
7 das ist 7
6 das ist 6
10.2 das bist du
10.123 das ist .123
10.3 das ist er
10.2223 das ist .2223
10.2123 das ist .2123
*/

Montag: Doubly Linked List. Mit Sentinel (head) statt mit head und tail Referenz.

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 node = head;
	var pos = 0;
	if (i > 0 && i < size + 1) {
	    do {
		++pos;
	        if (node.next) node = node.next;
		if (pos === i) return node.item;
	    } while (pos < i);
	} 
	return null;
    }
    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.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
*/

EcmaScript.next

Montag: Neben den anderen Teilnehmern der W3Conf gibt es auch einen Beitrag von kitcambridge, der neben einer Einführung in EcmaScript natürlich die bereits approveden Syntaxänderungen vorstellt. Ich finds interessant und es ist eine Inspiration mit dem Parser weiterzumachen. Interessant ist das destructuring feature, dass ich, wenn ein Objekt uebergeben wird, aus dem auf der Parameterzeile extrahieren kann.

	    // Interessant ist, das destructuring auf der Parameterzeile moeglich wird
	    
	    function href({ "href": link }) {
		console.log(link);
	    }
	    href({ name: "linux-swt.de", href: "http://linux-swt.de" });
	

Ich bin zudem noch glücklich ein weiteres sogenanntes "BindingPattern" gesehen zu haben. Um die in den Parser einzubauen, und AST-Nodes mit herzustellen, muss man sie auch verstehen, und wissen wo sie auftauchen (hier in der FormalParameterList(), die die FunctionDeclaration() bei den Parametern unterstützt, von der Grammatik abgeleitet) und wozu sie zu gebrauchen sind (hier wird einfach eine Variable Link aus einem Objekt extrahiert). Ich denke, wenn man jetzt null und false uebergibt, kriegt man entweder undefined oder einen TypeError.

	var object = {
	    methodeEins (arg1, ...args) {
	// neue Syntax
	    },
	    methodeZwei: function () {
	// alte Syntax
	    }
	};
	

Ich denke mal, auch hier wird der Parser (im Syntaxhighlighter der) die Methode nicht erkennen. Ich habe den Code fuer die neue Syntax schon angefangen gehabt, zusammen mit der ClassDeclaration(), den MethodDefinitions(), der SuperExpression(), aber glaube, das lief noch nicht. Kriegt man raus, wenn man auf "Abstract Syntax Tree" vom Hiliter klickt, sollten die beiden Methoden richtig eingelesen sein, stehen sie im Objektliteral.

Comrehensions, ArrowFunctions, GeneratorExpressions kann der Parser auch noch nicht. Die haerteste Nuss, die gar nicht schwer ist, aber die komplexesten Gebilde einfacher Destrukturierung hervorbringt ist aber das Extrahieren von Variablen. Wird eine ganz einfache Anweisung. Waren sie bisher alle.

Datenstrukturen

Hier ist das Dictionary vom letzten Sonntag nochmal aufbereitet, dass ich mit den Hashing Lektionen weitermachen kann. Ich habe Word und Definition entfernt, jetzt macht es ein Entry, oder Item. Der Key und Value speichert. Die Funktion hat mittlerweile Probing (guckt bei Kollision nach dem naechsten freien Slot) und eine Resize Funktion (die hier eher trivial ist, wobei man JS Arrays nichtmal dimensionieren muss. Der Logik nach machen wir das aber trotzdem, damit es quasi 1:1 ist.

Sonntag: Wir haben viel Fernseh geguckt. Ich hab nochmal kurz die Hash Table Lektion angemacht und mal die Folie gemacht.

/* 

    Update: Hier ist ja der Code nicht ganz von mir selbst, darum wie immer:
    Quelle: Codefolie: CS61B Hash Tables, von der Berkeley-Uni, auf YouTube, 
    CS61B ist ein DS und Algo Semester mit Shewchuck. 
    Das folgende Dictionary ist die einfachste Version vom Hashtable
    aus der Einführung und in JavaScript, statt in Java geschrieben.
    Ich glaube, ich hab die Compression Function (h) bereits hinzugefuegt.
    usw.
    Weiter ausgearbeitet wird das die Tage.
    
*/

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) {
    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) {
    	if (!(w instanceof Word)) w = new Word(w);
	var i = h(w.hashCode())
	return defTable[i] && (defTable[i] = null);
    }
    function h (hashCode) {
	return +hashCode % N;
    }
    var defTable = [];
    var me = this;
    if (!(me instanceof Dictionary)) return new Dictionary;
    me.insert = insert;
    me.find = find;
    me.remove = remove;
    me.h = h;	
    return Object.freeze(me);
}

var dict = new Dictionary(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
*/

Sonntag: Den Queue brauche ich fuer Level-Order Traversal. Ich hatte hiervor eine "level-depth" Funktion geschrieben, die aber nur einen Level eine Node breit auswertet. Die war vom ersten Durchgang halb im Gedaechtnis. Aber nur halb ist === falsch. Hier ist schonmal eine taugliche Warteschlange, auf dem listenbasierten Stack von gestern basierend.


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
*/

Samstag: Hier ist mal ein Stack als Liste anstatt als var stack = [].

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
*/

Freitag: Update: BinaryNode kriegt die Traversalfunktionen spaeter. Soll praktischer sein. Habe ich laut und deutlich gehoert. Update: Jetzt fehlen die essentiellen Operationen immernoch. Ich habe die ugly Struktur mit Memberfunktionen entfernt. Jetzt kann ich mit nem vernuenftigen Binaerbaum weitermachen.

if (typeof exports !== "undefined") {
    exports.BinaryTree = BinaryTree;
    exports.BinaryNode = BinaryNode;
}

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 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, w.left);
	    if (node.left) queue.push({node:node.left,level:level+1,left:true});
	    if (node.right) queue.push({node:node.right,level:level+1,left:false});    
	}
    }
    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) {
    }

    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 (node) {
	var tmp = node;
    }
    function rotater (node) {
	var tmp = node;
    }

    function is_ordered (node) {
	if (!node) node = root;
	if (node.left) {
	    if (node.left.key > node.key) {
		return false;
	    } else {
		if (!isOrdered(node.left)) return false;
	    }
	}
	if (node.right) {
	    if (node.right.key < node.key) {
		return false;
	    } else {
		if (!isOrdered(node.right)) return false;
	    }
	}
	return true;
    }
    
    function height (node) {
	var height = 1;
	while (node.parent) {
	    node = node.parent;
	    ++height;
	}
	return height;
    }
    
    function print (node) {
	var output = "{";
	var whole = "";
	var lastlevel = -1;
	var tabs = Array(8); // muss richtig gerechnet werden
	node = node || root;
	levelorder(function (node, level, left) {
	    if (level > lastlevel) {
		output += "";
		lastlevel += 1;	
		whole += output;
		console.log(output);
		tabs.pop();
		output = tabs.join("\t");
	    } 
	    if (left === false) output += "\\";
	    output += "{"+node.key+",'"+node.value+"')";
	    if (left === true) output += "/";
	    output += " ";
	});
	output += "\n";
	output += "}";
	whole+=output;
	console.log(output);
	return whole;
    }
    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;
    me.preorder = preorder;
    me.inorder = inorder;
    me.postorder = postorder;
    me.levelorder = levelorder;
    me.find = find;
    me.insert = insert;
    me.update = update;
    me.remove = remove;
    me.rotatel = rotatel;
    me.rotater = rotater;
    me.height = height;
    me.print = print;
    return Object.freeze(me);
}

Hier noch eine SList, die noch transformiert werden will, seht ihr den prototype?

// require("./slist").*
if (typeof exports !== "undefined") {
    exports.SListNode = SListNode;
    exports.SList = SList;
}

/* Linked Lists I */

// SListNode
// Eine Node in der SList
// SListNode
// - insertAfter (item)
// - remove
// - nth
// - isInvalidNode (rest folgt)
//

function SListNode (item, next, list) {
    if (!(this instanceof SListNode)) {
	return new SListNode(item, next);
    }
    this.item = typeof item !== "undefined" ? item : null;
    this.next = typeof next !== "undefined" ? next : null;
    this.list = typeof list !== "undefined" ? list : null;
    if (this.list)
    this.list.size += 1;
    
}
SListNode.prototype.insertAfter = function (item) {
    if (typeof item !== "undefined" && item !== null) {
	this.next = new SListNode(item, this.next, this.list);
    } else {
	throw new Error("item required");
    }
}
SListNode.prototype.remove = function () {
    this.list = null;
    this.next = null;
    return this;
};
SListNode.prototype.nth = function (i) {
    var j = 0;
    if (!this.list) {
	throw new Error("invalid node exception");
    }
    var l = this.list.head;
    do {
	j++;
	if (j == i) return l;j
    } while (l = l.next);
};
SListNode.prototype.isInvalidNode = function () {
    return this.list === null || this.list instanceof SList === false;
}


// SList
// Eine singly linked list
//
// SList
// - isEmpty()
// - front()
// - insertFront(item)
// and
// - removeFront()
// - length()
// - insertAt(i)
// - visitAll(visitor)
//
function SList (head) {
    this.size = 0;
    if (head) this.insertFront(head)
    else this.head = null;
    if (this.head) this.size = this.length();
}
SList.prototype.isEmpty = function () {
    return this.head === null;
};
SList.prototype.insertFront = function (item) {
    if (item instanceof SListNode) {
	this.head = item;
	this.head.list = this;
    } else {
	this.head = new SListNode(item, null, this);
    }
};
SList.prototype.front = function () {
    return this.head;
};
SList.prototype.removeFront = function () {
    var old;
    if (this.head && this.head instanceof SListNode) {
	old = this.head;
	this.head = this.head.next;
	old.list = null;
	return old;
    } else {
	if (this.isEmpty()) throw new Error("can not remove front - empty list");
    }
}
SList.prototype.length = function (node) {
    var size = 0;
    node = node || this.head;
    
    if (this instanceof SList && node instanceof SListNode /*&& node.list === this*/)
     {
	do {
	    ++size;
	} while (node = node.next);
        return size;
    } else {
	throw new Error("count - not a listnode" /* +" or not in this list"*/);
    }
}
SList.prototype.insertAt = function (pos, item, node) {
    var at = -1;
    node = node || this.head;
    if (node instanceof SListNode) {
	do {
	    ++at;
	    if (at === pos) { 
		node.insertAfter(item, this);
		break;
	    } 
	} while (node = node.next && at < pos);
    } else {
	throw new Error("not a listnode");
    }
}
SList.prototype.visitAll = function (visitor, node) {
    var pos = -1;
    if (typeof visitor === "function") {
	node = node || this.head;
	if (this instanceof SList && node instanceof SListNode)
	{
	    if (node.list !== this) throw new Error("wrong list to call visitor on node from");
	// if (node instanceof SListNode) {
	    do {
		++pos;
		visitor(node.item, pos);
	    } while (node = node.next);
	} else {
	    throw new Error("not a listnode");
	}
    } else {
	throw new Error("not a function");
    }
    return pos;
};

/* Ausprobieren...*/

// 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
*/

Parser weitermachen

Arrow Functions und, und, und.

Donnerstag: Ich habe eine Strategie für alle drei Schwierigkeitsgrade gefunden, wie Tic Tac Toe gelöst wird und kann damit genau sagen, wie meine programmierte Formel funktioniert. Ausserdem ist es mir so möglich, zu lernen, wie ich das Verhalten des Computerspiel(er)s fine tunen kann.

Update: Ich habe mir die Züge mittlerweile aufgeschrieben. In jedem Level gibt es andere Ich kann den Game Tree Search sich mittlerweile verrechnen lassen, dass der Computer meinen Zug nicht sieht. Oder andersrum gesagt, ich kann den Fehler jetzt nutzen und danach wohl ein besseres Tictactoe Muster schreiben.

    // Aufgabe Parser. Arrow Functions.
    
    let f = (x,y,z) => x + y + z;
    let res = f(1,2,3);
    res;
    
    // ergibt 6 wenn es fertig ist.
    

Archiv

  • Seit diesem Monat versuche ich: Datenstrukturen und Algorithmen zu lernen.
  • Die Einträge vom letzten Monat sind alle hier zu finden.
  • Die Einträge vom vorletzten Monat sind alle hier zu finden.
  • Die Einträge vom vorvorletzten Monat sind alle hier zu finden.
  • Die Einträge vom vorvorvorletzten Monat sind alle hier zu finden.
  • Die interessanten Sachen: spidermonkey | libuv

Diese Seite erfordert JavaScript und einen aktuellen Browser, um zu funktionieren.