Edwards JavaScript vom Hartz-IV Empfänger Homepage
Mathematische Irrtümer und Programmfehler vorbehalten. ;-)
Mathematische Irrtümer und Programmfehler vorbehalten. ;-)
Die Funktion ist aus [Balzert09] Lehrbuch der Softwaretechnik: Basiskonzepte und Requirementsengineering, 3. Auflage 2009. Der Java Code besagte, die Quadratwurzel zu berechnen. Eine Probe bestaetigt das.
function sqrt(x) {
var y0, y1, i;
if (x < 0.0) throw "error";
y1 = 1.0;
i = 1;
for (;;) {
y0 = y1;
y1 = 0.5 * (y0 + x / y0);
i++;
if (i > 50) throw "error2";
if (Math.abs(y1-y0) < 1e-6) return y1;
}
}
console.log(sqrt(25));
console.log(sqrt(2));
/*
5
1.414213562373095
*/
Dann war ich ja letzten schon nah dran, als ich bei der 6.006 Lecture Newtowns Method und High Precision Number Computing, versuche, diese zu ermitteln. Und in 6.000 Introduction to Computer Science and Programming kam eine andere verwandte Methode zum Naehern an die Wurzel dran. Wie man sieht, geht die hier aber wunderbar.
Ich moechte mir die RedBlackTrees nun programmieren und visualisieren. Ich habe das Kapitel ueber RedBlackTrees, was zur Vorlesung gehoert. Dadurch kann ich die Implementation in Kuerze vervollstaendigen.
In der aktuellen Abbildung kann man eindeutig erkennen, dass die RedBlackProperties, d.h. die mathematischen-programmatischen Eigenschaften des Baumes, verletzt werden. Eine rote Node kann keinen roten Parent haben.
Und nicht nur das Problem mit der 8. Der Baum ist noch ein Fall fuer den Debugger. Wenn ich beliebige Werte eingebe, funktioniert er nicht. Ich denke mal, da ich mit null Pointern statt einem NIL-Sentinel (dummy node) arbeite, dass beim rotieren oder recolorn mal ein Zugriff versagt. Man muss ja nur einen Case uebersehen und schon wirkt sich das auf viele Faelle aus.
ready(function (e) {
var canvas = document.querySelector("#rbt");
var context = canvas.getContext("2d");
var tree = new RedBlackTree();
tree.insert(7, "Hallo");
tree.insert(3, "Welt");
tree.insert(9);
tree.insert(18);
tree.insert(6);
tree.insert(23);
tree.insert(8);
tree.insert(15);
tree.draw(context);
});
Da ich den Baum komplett gekapselt habe, und keine Nodes leake, kann man den Context an den Baum uebergeben. Ich habe inzwischen ein weiteres Feld gefunden, was ich nicht richtig gelernt habe. Animation. Alle Algorithmen, die ich in den letzten 2-3 Monaten ausprobiert habe, sind fundamental fuer die Daten, aber zum malen habe ich, bis auf was Vektormathe und Winkelfunktionen im Anriss, noch keine Strategie.
Die folgende Routine fuehrt die Rotationen und das Rekolorieren durch und ist wie leftrotate und rightrotate auf jeden Fall mit einem Bug behaftet. Es kommen invalide Baeume raus.
function insert_fixup (z) {
var y;
var p, q;
while (z && (p = z.parent) && p.color === RED) {
q = p.parent;
if (q && p === q.left) {
y = q.right;
if (y && y.color === RED) {
p.color = BLACK;
y.color = BLACK;
q.color = RED;
z = q;
} else if (z === p.right) {
z = p;
leftrotate(z);
if (z.parent) z.parent.color = BLACK;
} else {
p.color = BLACK;
q.color = RED;
rightrotate(q);
}
} else if (q && p === q.right) {
y = q.left;
if (y && y.color === RED) {
p.color = BLACK;
y.color = BLACK;
q.color = RED;
z = q;
} else if (z === p.left) {
z = z.parent;
rightrotate(z);
if (z.parent) z.parent.color = BLACK;
} else {
p.color = BLACK;
q.color = RED;
leftrotate(q);
}
}
}
if (root) root.color = BLACK;
}
Brendan Eich erzaehlt auf der OWASP AppSecUSA 2012 The Same-Origin Saga.
Interessante Geschichte und viele Details, was frueher war, woher das kam, und welche Bedeutung vieles davon heute noch hat, wie document.write fuer Ads oder document.domain fuer die Same-Origin-Policy.
Der greatest common divisor (gcd) oder auf deutsch GgT laesst sich mit dem bekannten Euklidischen Algorithmus errechnen. Wenn q gleich 0 ist, dann gebe p zurueck, ansonsten rechne den Rest aus p % q aus, und gebe das Ergebnis des rekursiven Aufrufs von gcd mit q und r zurueck. Wenn r jetzt 0 ist, dann wird q direkt zurueck gegeben (Zeile 2, if q===0 return p).
function gcd(p, q) {
if (q === 0) return p;
var r = p % q;
return gcd(q, r);
}
function print(a,b) {
console.log(gcd(a,b));
}
print(1,2);
print(10,20);
print(40,30);
print(12,4);
print(444,400);
print(44, 40);
print(44444,4444);
print(127,254);
/*
1
10
10
4
4
4
4
127
*/
Aus [Sedgewick] Algorithmen in Java. Pearson Studium/Addison Wesley. Was ich als Algorithmen in C vor 10 Jahren mal hatte.
Gestern Abend habe ich es noch geschafft, "Divide and Conquer Recurrences" (18.062j Mathe für CS) zu wiederholen.
Die Türme von Hanoi habe ich vor zwei oder drei Monaten schon probiert, da war die Wikipedia zu schnell mit der Loesung, dass ich den Sinn der Mathematikaufgabe verpasst hatte. Diesmal habe ich sie im halbschlaf begriffen.
Man hat kurz ausprobiert. Fuer eine Scheibe T(1) braucht man 1 Move. Fuer 2 Scheiben T(2) braucht man 3 moves, fuer 3 Scheiben T(3) braucht man bereits 7 Zuege. Die Frage war, wie viele man fuer n Discs braucht?
Wenn man bis zur vorletzten Scheibe T(n-1) geht, dann die letzte Scheibe +1 bewegt, und dann wieder alle draufhebt T(n-1) kommt man auf 2*T(n-1) + 1.
Die Daten wurden ermittelt, indem man die ersten Scheiben bewegt und mitgezaehlt hatte. Ich hab sie mir von gestern bis heute merken koennen. Wollte eigentlich gestern abend schon was zu schreiben.
Formel durch Erraten (Clever Guessing): Bei den Daten T(1)=1, T(2)=3, T(3)=7, T(4) = 15, draengt sich die Vermutung auf, dass es sich um die Formel T(n) = 2^n - 1 handelt.
T(n) = 2*T(n-1) +1 = 2^n -1
Beweis durch Einsetzen (Substitution Method)..
Achtung: Die richtige Substitution schreibweise kann man hier lesen (Wikipedia). Das ist erstmal von mir so aufgeschrieben. Jetzt muss ich meine Schreibung auch noch anpassen.
Beispiel T(3): T(3) = 2*T(n-1) + 1 = 2*T(2) + 1 = 2 * 3 + 1 = 7; 7 = 2^3 - 1 = 8 - 1 Für drei Schreiben sind mindestens sieben Schritte zu verrichten.
Bei T(n) bei n = 64 sind 2^64 - 1 Schritte zu verrichten, das sind 18446744073709552000 Schritte bei 64 Scheiben. Quasi unloesbar in der Zeit eines Menschenlebens, jedenfalls sagte der Professor gestern auch, dass die Moenche wohl bis ans Ende der Welt zu tun hatten..
Mathematische Beweise muss ich noch was schriftlich ueben. In 6.046 oder 6.006 wird praktisch mit Algorithmen gerechnet, in 6.042/18.062j Mathe fuer Informatiker liegt der Schwerpunkt auf mathematischen Beweisen. Ich bin im Moment noch ein wenig unsicher, wie ich mir gerade bestaetigte. Denn die paar Zeilen obendrauf haette ich mit den Angaben bereits als perfekten Beweis formulieren koennen muessen. So steht er jetzt in meinem Deutsch da. Das ist noch falsch.
Eine Animation, die ich gestern im Anschluss ausprobieren wollte, habe ich entfernt. Ich habe mich der Funktion bewege der Wikipedia: Die Türme von Hanoi bedient, die ich letzten Monat mal ausprobiert hatte und dabei einen Fehler uebersehen. Die Ausgabe stimmte glaube ich mit der der Wikipedia ueberein, aber enthielt einen Fehler. Ich hab das noch nicht geprueft, wer jetzt den Fehler machte, jedenfalls darf ich das nochmal machen.
Uebrigens hat hanoi eine exponentielle Komplexitaet O(2n), was das Problem schon recht hart macht. Auch wenn es einfach ausschaut, wenn man die Loesung sieht, steckt da mathematisch noch ein gewisser Anspruch hinter, es als Lehrbeispiel zu verwenden..
Splay Trees kann man unter Spreizbaum nachlesen. Die Rotation durch den Parent nach rechts oder links habe ich nun mehrere male fuer verschiedene Baumtypen wiederholt, dass ich sie mir auch als allgemeingueltig merken kann. Vor zwei Monaten hatte ich solche Funktionen schonmal auf meiner Frontpage vermerkt, als ich gerade mit dem BST uebte. Das hier sind natuerlich neue. Da die Subtrees A und C nicht veraendert werden, habe ich sie weggelassen. Nur B wandert von der einen node rechts innen nach links innen und umgekehrt, da sich zwischen den beiden Nodes ihr Intervall befindet.
function rightrotate (x) { // rotiert x rauf nach p, p nach rechts (zick)
var p = x.parent;
var q = p.parent;
var B = x.right;
if (q !== null) {
if (q.left === p) q.left = x;
else if (q.right === p) q.right = x;
}
x.parent = q;
p.parent = x;
x.right = p;
p.left = B;
if (B) B.parent = p;
}
function leftrotate (p) { // rotiert p rauf nach x, x nach links (zack)
var x = p.parent;
var q = x.parent;
var B = p.left;
if (q !== null) {
if (q.left === x) q.left = p;
else if (q.right === x) q.right = p;
}
p.parent = q;
x.parent = p;
p.left = x;
x.right = B;
if (B) B.parent = x;
}
Ist genau so einfach wie Binary Search, was von dem O(log n) Verhalten des Baumen bzw. dem Vergleich in der find/search Methode O(log n) abstammt.
Einen sortierten Array in O(lg n) Zeit durchsuchen. Diese hier ermittelt die Position p des Elements. Man kann auch S[p].key vergleichen und ganze Records returnen, ist ja logisch.
function bsearch(k,S) {
return binary_search(k,S,0,S.length);
}
function binary_search(k, S, l, h) {
var el, p;
p = Math.floor((h-l) / 2) + l;
if ((el = S[p]) === k) return p;
else if (k < el) return binary_search(k, S, l, p-1);
else if (k > el) return binary_search(k, S, p+1, h);
return null;
}
Naechstes Beispiel. Und so stelle ich mir den ohne Rekursion vor. Randomisierung und testen adjacenter Elemente bringt Vorteile gegenueber dem, was hier geschiert, einfaches halbieren der Suchfelder. Aber was passiert, wenn ich den floor von 0/2 will? Gottseidank kommt 0 raus. Koennte also klappen. Heute gibt es mal eine ungetestete Schleife, hehe. (Nachdem ich + l hinter p = floor((h-l)/2) schrieb, wahrscheinlich.)
function binary_search(k, S, l, h) {
var el, p;
l = l || 0;
h = h || S.length;
do {
p = Math.floor((h-l) / 2) + l;
if ((el=S[p]) === k) return p;
if (k < el) h = p-1;
if (k > el) l = p+1;
} while (h-l > 0);
return null;
}
/hiphop - da mache ich mir schon lange Luft. Meine Alten hatten ja, ich bin ja dank ihnen Hartz-IV Empfaenger, dass wird meine Mutter garantiert noch freiwillig zugeben, wie auch einiges anderes, was sie mit mir angestellt haben, was man nichtmal mit seinen Feinden macht, mir auch nahegelegt, mal Psychologie zu lernen. Die zwei sind nicht nur Zeichens ihres Berufes Alkoholiker mit derben Ausdruecken. Nein, sie haben Jahre auf mir rumgehackt. Nur was sie von mir wollten, haben sie bis heute nicht bekommen. Liegt daran, dass ich mir nichts antuen kann und so. Nun gut. Dieses Semester wird mir eine Freude sein. Denn sie haben so einiges verbrochen, was mir nichtmal im Traum einfallen wuerde. Ich bin eher der, dem was nachgesagt wird, was dann hinterher doch nicht stimmt, den das aber mitgenommen hat, weil das unverschaemt ist. Wohlan.
Heute komme ich dazu. Ich hab zwar den ganzen Nachmittag verpennt. Aber jetzt habe ich Koordinaten hinzugefuegt und trenne Namen und Typen, was mir das Assoziieren von Objekten einfach macht. Man braucht nur Namen und src Property und dest Property (weglassen der dest prop zeigt auf dest name selbst) angeben. Fuer Handeingabe optimal kurz und aussagekraeftig.
(Schomal im voraus eingegeben, etwas spaeter sitzt das Diagram perfekt. Ich fange gleich erst an.)
Ich habe schon Ideen, wie man das soweit ausgestalten kann, dass man JavaScript Diagramme mit der Hand schreiben kann. Ebenso denke ich an Drag und Drop. Aber nur im kleinen, nicht im Rahmen eines fetten CASE Tools.
Oh, ref bei var oder die Assoziationslinie zur korrekten Property habe ich noch nicht, sie geht nur von der rechten Ecke von src an die linke Ecke von dest. Und ich wundere mich gerade, momentan ist sie gar unsichtbar. Dabei wird sie erst nach den Objekten, die erst berechnet werden, gezeichnet, damit ich weiss, wohin ich zeichnen will, dann kann ich die Objekte naemlich kurz nachgucken im diagram hash. Ich muss noch vieles schreiben, ebenso wie function. Ich sehe, ich hab schon zwei, drei Worte mehr definiert.
Eigentlich liessen sich, ist in UML aber absolut unueblich, ich meine, ist dort ein eigenes Element, ob die Tools das machen, kann ich gar nicht sagen, die Assoziationen aus den Property Angaben errechnen. Ich denke, das werde ich machen, statt type: "assoc". Man gibt nur die Namen an und ich gucke, ob sie nochmal im Diagramm existieren, oder nur Diagrammtext sind.
ready(function (e) {
var objects = [
{
type: "var",
name: "list",
ref: "l1",
x: 10,
y: 20,
},
{
type: "ListNode",
name: "l1",
data: {
item: "23.244",
next: "l2"
},
x: 50,
y: 70
},
{
type: "assoc",
src: "l1",
srcp: "next",
dest: "l2"
},
{
name: "l2",
type: "ListNode",
data: {
item: "46",
next: "l3"
},
x: 200,
y: 70
},
{
type: "assoc",
src: "l2",
srcp: "next",
dest: "l3"
},
{
type: "ListNode",
name: "l3",
data: {
item: "14.1",
next: "null"
},
x: 350,
y: 70
},
{
type: "function",
name: "glob_op",
args: ["a", "b", "c"],
returns: "number",
x: 150,
y: 20
}
];
var fp = new FunctionPlotter("#dia2", { width: 500, height: 200 });
fp.dia(objects);
});
Ich denke mal, srcp und destp bei den associations sind noch nicht perfekt gewaehlt. Aber ich muss Object, Array, Date, etc. anzeigen, function, var (let, const schon heute), und dann die Verbindungslinien zwischen den properties, Variabeln, Instanzen und schon ist alles gut. Dieses verdammte Keyboard hakt aber, dass ich, sieht man auch auf der Seite, eher zwei als zwanzig Zeilen schreibe, was im Code eher zweihundert ausmacht. Ist gerade urschwer, einen Buchstaben rauszukriegen.
Ich glaube, ich habe die Substitutionsmethode verstanden. Die und das Master-Theorem. 6.046j, 6.006 und 6.042 (Mathe) behandeln die Mathematik ausfuehrlich. Ich kann die schon vorwaerts und rueckwaerts pfeifen. Ich glaube, sogar schreiben. Und genau das will ich ueben. Ich werde das noch ein paar Monate lang machen.
Algorithmus: Fuer jedes Wort in doc1 und doc2. Q = Anzahl der Vorkomnisse in Doc 1, R = Anzahl in Doc 2, Summiere Q * R
Der Algorithmuskurs 6.006 beginnt mit einem Document Distance Algorithmus, mit dem ein Vektor zwischen zwei Dokumenten festgelegt wird, der ihre Aehnlichkeit anzeigt. In Anlehnung daran habe ich schonmal mit dem Code angefangen. Die Lektion werde ich aber wiederholen, um ihn dann zu schreiben. Die Funktionen difference und equality sind von mir. In Anlehnung ans Original sind da einige Moeglichkeiten drin. Ach, und der Prof. nutzt den Algorithmus, um Arbeiten zu kontrollieren. Ist doch cool, oder? Wer den DD Algorithmus kennenlernen will, sollte sich 6.006 angucken.
(function (global) {
function inc_counter(word, counter) {
var w;
if (typeof counter[word] === "number") counter[word] += 1;
else counter[word] = 1;
}
function count_words (doc) {
var counter = Object.create(null);
doc.split(/\s/).forEach(function (w) {
inc_counter(w, counter);
});
return counter;
}
function equality(c1, c2) {
var eq = Object.create(null);
Object.keys(c1).forEach(function (k) {
if (c2[k]) eq[k] = c1[k] / c2[k];
});
return eq;
}
function difference(c1, c2) {
var diff = Object.create(null);
Object.keys(c1).forEach(function (k) {
if (!c2[k]) diff[k] = c1[k];
else diff[k] = c1[k] - c2[k];
});
Object.keys(c2).forEach(function (k) {
if (!diff[k]) diff[k] = -c2[k];
});
return diff;
}
function docdist(doc1, doc2) {
var record = {};
if (typeof doc1 !== "string" || typeof doc2 !== "string") throw "docdist(d1,d2)";
record.count1 = count_words(doc1);
record.count2 = count_words(doc2);
record.difference = difference(record.count1, record.count2);
record.equality = equality(record.count1, record.count2);
return record;
}
Object.defineProperty(global, "docdist", { value: docdist, configurable: false, writeable: false });
if (typeof exports !== undefined) {
var fs = require("fs");
var doc1 = fs.readFileSync(process.argv[2],"utf8");
var doc2 = fs.readFileSync(process.argv[3],"utf8");
console.dir(docdist(doc1,doc2));
}
}(this));
/*
{ count1: { Ich: 1, bin: 1, schoen: 1, und: 1, 'toll.': 1, '': 1 },
count2: { Ich: 1, bin: 1, gross: 1, und: 1, 'stark.': 1, '': 1 },
difference:
{ Ich: -1,
bin: -1,
schoen: 1,
und: -1,
'toll.': 1,
'': -1,
gross: -1,
'stark.': -1 },
equality: { Ich: 1, bin: 1, und: 1, '': 1 } }
{ count1: { Ich: 1, bin: 1, schoen: 1, und: 1, 'toll.': 1, '': 1 },
count2: { Er: 1, ist: 1, anders: 1, '': 1 },
difference:
{ Ich: 1,
bin: 1,
schoen: 1,
und: 1,
'toll.': 1,
'': -1,
Er: -1,
ist: -1,
anders: -1 },
equality: { '': 1 } }
{ count1: { Ich: 1, bin: 1, schoen: 1, und: 1, 'toll.': 1, '': 1 },
count2: { Ich: 1, war: 1, schoen: 1, und: 1, 'stark.': 1, '': 1 },
difference:
{ Ich: -1,
bin: 1,
schoen: -1,
und: -1,
'toll.': 1,
'': -1,
war: -1,
'stark.': -1 },
equality: { Ich: 1, schoen: 1, und: 1, '': 1 } }
{ count1: { Ich: 1, bin: 1, gross: 1, und: 1, 'stark.': 1, '': 1 },
count2: { Er: 1, ist: 1, anders: 1, '': 1 },
difference:
{ Ich: 1,
bin: 1,
gross: 1,
und: 1,
'stark.': 1,
'': -1,
Er: -1,
ist: -1,
anders: -1 },
equality: { '': 1 } }
*/
Heftig waer, wenn es im JavaScript Object Hashtable so abgehen wuerde, aber ich denke, die ersten 4 oder 8 Properties wird es dann bestimmt gratis geben, weil das ja unmoeglich waere, wenn man properties zuweisen will...
Table Doubling. So nennt man das verdoppeln der Tabelle, wenn ein Ueberlauf droht. Das heisst, wenn der Table beim insert dann voll oder fast ist. Ein insert in einen Hashtable liegt so bei O(1) in Python. Wenn die Tabelle aber mit einem Eintrag beginnen wuerde, und sich dann auf 2 vergroessert, dann auf 4, dann auf 8, dann wuerde gerade die Spielerei mit 0-4 Properties, oder 0-8 Properties, sehr sehr teuer werden, da staendig der Hashtable vergroessert oder verkleinert werden wuerde.
function insert(k,v) {
if (size +1 === max) {
// Doubling the Table (-1 Dollar pro Bucket)
// resize + O(n) inserts
resize(size+1 * 2);
}
// insert O(1)
var code = h(k); // +2 Dollar pro insert (reicht fuer 1* Table Doubling)
table[code] = v;
}
Darum legt man Hashtables in Erwartung an eine reelle Groesse von vornherein guenstig an. Ich denke, auch bei JavaScript wird das {} so viel Platz bieten, dass ich mit vielen kleinen Objektliteralen im Schnitt mit dem Zugriff praktisch konstant auf die Keys bin wie bei konstant hardgecodeten Vergleichen mit den keys.
Die Amortized Analysis beschaeftigt sich mit dem Table Doubling im Grossen und im mathematischen Sinne. Besonderheit der Anwendung. Es wird in Dollar statt in Zeit gerechnet. Und durch eine kluge Verteilung von insert, delete und resize Operationen, kann man mit den konstanten Einkuenften der Zugriffe das Geld fuer das Tableresizing aufwenden (sprich hat man dann die Zeit fuer).
function resize(size) {
var oldTable = table;
table = new HashTable(size);
for (var i = 0; i < oldTable.length; i++) {
table.insert(oldTable[i]);
}
}
/* Das kostet beim resize nochmal O(n) bzw. alle Dollar. Alle alten Elemente muessen
einen neuen Schluessel fuer den neuen Table bekommen. Mitunter sind
das viele viele Elemente, die in eine neue Datenbank eingefuegt werden
wollen. */
Damals wird es um Hashtables in anderen Performancedimensionen gegangen sein. Die Analyse ist etliche Jahre alt. Aber bis heute ist Hashing eins der besten Verfahren, um Daten mit einem Schluessel zu speichern und wiederzufinden. Man errechnet aus dem Schluessel einen Code, und sollte der passende Slot belegt sein, rotiert der Code, er wird in so vielen Versuchen, wie er rotierte wiedergefunden (in der Grundlage), und es gibt Beweise und Praktiken fuer optimale Groessen und Verteilunge.
Die Amortized Analysis ist eine unterhaltsame Lehre. Sie liefert fundierte Kenntnisse und mathematische Beweise aus dem Umgang mit Hashtables. Man weiss genau, wie lange die Operationen im einzelnen brauchen. Und das kann man mathematisch bestimmt schon ab der 5. oder 6. Klasse verstehen. Jedenfalls kommt da nicht mehr vor als ein Bruch n/2 bzw. nichts schwereres.
Im weiteren hilft diese Analyse Sprachen wie JavaScript, optimal mit ihren internen HashTables umzugehen. Darum denke ich, mit um Objektliterale mit 1-8 Attributen keine Sorgen machen zu muessen, weil die Startgroesse des Hashes bestimmt optimaler gewaehlt ist.
Oh, ich bin gestern Abend eingenickt, bevor ich herausfand, ob ich dem Context translated habe. Dabei fiel mir bereits ein, der Plotter nutzt in Zukunft einen Stack fuer contexts. Dadurch kann ich einen Plotter fuer mehrere Views nehmen. Denn die Kosten fuer die Instanz werden immer groesser.
Wenn er mehrere Views (mind. 1 je Funktion) kann, und weiter ausreift, dan irgendwann kann ich auch Subprobleme und kleine Plotter raus machen. Aber jetzt kommt erstmal der Stack/View Fix, dann kann man einen plotter nehmen und bei jedem draw Aufruf auf ein anderes Element malen kann.
/* vorher */
var context;
/* nachher */
var contexts = [];
function pushContext() {
return contexts.push(context);
}
function popContext () {
context = contexts.pop();
return context;
}
Da macht auch das auslesen der canvasOptionen, die ich bereits anfing Sinn, weil man jeden dann gleich konfigurieren kann. Ich muss das noch verfeinern, dass alle Breiten und Farben korrekt eingestellt werden koennen, am besten, man kann sogar className angeben :-).
return this; gefaellt vielen an jQuery, dass es auch Sinn macht, weil man neue Canvas Objekte oder ViewElemente (erzeuge Canvas darin) angeben kann.
var fp = new FunctionPlotter();
fp.plot({ el: "#plot1", width: ... }).plot({ el: "#plot2", ... });
Das ist cooler, als wenn ich jetzt jedesmal ein neues FunctionPlotter Objekt erzeuge. Denn je oefter ich das Tool anwende, um so mehr Daten wuerde ich gerne schnell anzeigen.
Hier bin ich gestern abend eingeschlafen, bevor ich die zweiten fuenfzehn Minuten opfern konnte.
Ich habe schon seit 2006 nichts mehr im Sinne vom Softwareengineering nach Elsevier (damals Spektrum) gemacht.
Ich hardcode jetzt kurz eine Funktion, die eine JSON nimmt um Objekte, Assoziationen zu zeichnen. Nicht in UML, sondern in meiner JavaScript Notation.
Das kann ich dann verfeinern, um Objektliterale, Arrays und Functions abzubilden, sowie Variablen, Pfeile und Notizen.
Die Abbildung zeigt zwei Objekte, die einseitig assoziiert sind, indem die Variable next auf das naechste Objekt zeigt. Das beschreibt zugleich eine linked list.
--
Eine Assoziationlinie ist auch gezeichnet. Ich habe inzwischen ein korrektes Objekt fuer jede Diagrammkomponente mit aktuellem Status im Kopf. Gestern habe ich die Linie einfach salopp dazwischen gezeichnet. Aber ich weiss, wo ich die Daten (x,y, aber auch Drag-und-Drop) speicher.
Und - Eingabe ist JSON statt xml, intuitiv fuer viele.
Auch in 6.046j dran kommen SkipLists. Das sind linked Lists, beziehungsweise mehrere, von denen die "hoeheren", in groesseren Abstaenden verlinkt sind, dass man zum Beispiel jede 100. = 10 Nodes (L4), 50. = 20 Nodes (L3), 10. = 100 Nodes (L2), 5. = 200 Nodes (L1), alle 1000 (L) Nodes ansteuern kann. Man kann dabei lineare Suchgeschwindigkeiten unterschreiten, indem man durch kluge Entscheidung viele Elemente der Liste (L) ueberspringt.
Im 6.046j kommt das Beispiel New Yorker U-Bahn, die local line und xpress line per SkipList verbindet, dran. Ob die BVG das mit dem TXL und dem 123 so auf unserer Strecke macht? Ich denke nicht. Die haben ihre eigenen Graphen, Listen, Bäume, PriorityQueues, das ist sicher. Aber das ist ein fantastisches Beispiel komplexer Software, die auf vernuenftige Linked List zurueckgreift.
Habe in etwa sowas Code wie beim Redblack Tree angefangen. Code kommt, wenn er mit nem Beispiel laeuft.
Einen Überblick über die Selbstlernerkurse habe ich mittlerweile auch.
Die Mathefakultaet habe ich "leergezogen" (den April mit 6.6k und den Rest mit den 5GB fuer Mai) und werde ich machen, aber auch die Faecher Psychologie, Solid State Chemistry, und Microeconomics (hatte ich viele deutsche dtv, Vahlen, Schaeffer-Poeschel, wrw frueher) tun es mir genau so an.
Ich denke, im naechsten Monat komme ich zu Physik I + II + III. Angucken, anwenden dauert etwas laenger.
Im 6er Department (EECS) habe ich ein paar Vorteile, weil ich die Informatiklektionen meist schonmal gelesen hatte, als ich juenger war. Dennoch bin ich sicher, mit Electronics und Circuits und erst recht mit Signals und Systems noch was fuers Leben zu lernen.
Ich denke, hier kann ich studieren, bis ich 40 bin. Und dann kann ich das mal richtig machen. Bis dahin werde ich aber wohl auch HTML5 gelernt haben.
Damit ich das auf dem Schirm hab.
Ich muss noch mit den Dreiecken weitermachen
Ich hab noch ein paar Probleme mit den Winkelfunktionen.
Vermutung Also ich bemerke den gesuchten Fehler. Ich habe es vom falschen Winkel aus berechnet. Der Winkel, in dem die Hypothenuse den Mittelpunkt des Kreises, gemessen an der x Achse, schneidet, den habe ich verwendet. Ich wollte aber damit nur die Anpassung der Koordinaten um jeweils ihren Sinus und Kosinus. Das Dreieck, das muss ich mit den Winkeln des Dreiecks berechnen.
Vermutung Darum der Fehler. Ich bin einfach nicht drauf gekommen. Jetzt habe ich gerade das Objekt uebergeben, die Winkel ausprobiert, und mir war klar, was ich definitiv falsch machte. Denn der Alpha Winkel des Dreiecks, bei Gamma = 90°, der ist gar nicht mehr in der Formel drin. Die Koordinaten werden falsch berechnet. Darum liegt das nicht auf dem Kreis, sondern ist nur ein Dreieck. Ein in zwei Beziehungen vom Winkel abhaengiges Dreieck, von dem Winkel von der x-Achse ab, mit dem die Hypothenuse durch M vom r des Kreises geht.
Ich glaube ich habe das mit dem Weglassen der Konstanten und niederen Terme verstanden. Die Multiplikation mit der Konstante habe ich nun x-mal wiederholt. Ich glaube, hier liegt eine Ordnung von O(n), gar Θ(n) vor, da sich mit c bzw. d sowohl Ober-, als auch Untergrenze finden lässt.
Ich muss es nur noch nichtig beschriften (und noch ein paar mal lernen). Zur Zeit ist es das folgende Objekt. Davor hatte ich noch T, O, Omega (weiter unten oder April). Inzwischen habe ich ein wenig dazugelernt, daß ich es mir zumindest anders wünsche.
fp.compare_asymptotes({
n: Math.pow(2, 4),
scale: 10,
prec: 0.1,
f: function (n, N) {
return 2* n;
},
g: function (n, N) {
return n;
},
c: 2.1,
d: 1.9
});
Idee fuer die automatische Analyse. Wenn ich C neu waehle, und sie N uebersteigt, dann aendert sich der Test von O(N) dann zum Test auf O(N^2). Und umgekehrt bei C < N^-1. Und so aehnlich. Muß ich mir mal weiter ausdenken, ob das geht.
Das wird mal ein Red Black Tree mit function recolor (x) {}
Wenn man in den folgenden BST jetzt 1..10 einfuegt gibt es einen O(n) "Baum" mit
height n statt lg n, weil das eigentiche rot-schwarze noch nicht drin ist. Ich bin mir
nicht sicher, ich glaube anhand meine Faerbung und Hoehe verbiete ich die Aufnahme der
neuen Keys. Ich hab die paar Minuten ueberhoert. Hehe. Aber das laest sich nachholen.
Stimmt. Es sind Erweiterungen von BST-insert und BST-remove, wo LEFTROTATE, RIGHTROTATE
und RECOLOR und ein Coin zu flippen beim Colorieren. In jedem Fall balanciert er durch
Rotation.
Fuer O(n) Hoehe kann man beim BST entweder einen un(!)sortierten Array einfuegen, oder den sortierten in zufaelliger Reihenfolge und dann mit inorder arbeiten. BST-insert ist so auch als Randomized-BST-insert oder der Baum ueberhaupt als Random-BST bekannt. Auf das zufaellige Einfuegen bei geordneten Keys bin ich auch bereits gekommen, weil ich ebenfalls diesen O(n) Baum bemerkt habe, der so hoch ist, wie es Elemente gibt.
Der naechste Baum ist was anders. Jetzt fehlen die RB-Eigenschaften aber noch komplett, die eine ist, dass er wohl immer die Hoehe lg n hat. Ich muss die Lektion nochmal gucken. Dann praesentiere ich diesen Code mit RB-Eigenschaften in einer laufenden Fassung.
function RedBlackTree () {
"use strict";
var BLACK = "BLACK";
var RED = "RED";
var root = null;
var height = 0;
function Sentinel (p) {
return new RedBlackNode(null, null, p, null, null, BLACK);
}
function RedBlackNode (k, v, p, l, r, color) {
if (!(this instanceof RedBlackNode)) return new RedBlackNode(k,v,p,l,r,color);
this.parent = p || null;
this.key = k !== undefined ? k : null;
this.value = v !== undefined ? v : null;
this.color = color || BLACK;
this.left = l || null;
this.right = r || null;
return Object.seal(this);
}
function size (node) {
if (!node) return 0;
return size(node.left) + size(node.right) + 1;
}
function insert_node (k,v,node) {
if (node.key === k) {
return false;
}
if (k < node.key) {
if (node.left) return insert_node(k,v, node.left);
else node.left = new RedBlackNode(k, v, node, null, null);
return true;
}
if (k > node.key) {
if (node.right) return insert_node(k,v, node.right);
else node.right = new RedBlackNode(k, v, node, null, null);
return true;
}
return false;
}
function insert (k,v, node) {
node = node || root;
if (!root) {
root = new RedBlackNode(k,v, null);
return true;
} else {
return insert_node(k,v, node);
}
}
/*
RB-Props
1. a node is either red or black
2. root and leaves are all black
3. Every red node has a black parent.
4. All simple path (repats no vertices)
from a node x to descendendant leaf of x have
same #number of black nodes
(gucke alle pfade (l + r) runter. Alle sollten
die gleiche Hoehe haben! Das muss eingehalten werden.)
black_height(x) does not include x itself
*/
function recolor () {
}
function rightrotate (x) { // rotiert x rauf nach p, p nach rechts
var p = x.parent;
var q = p.parent;
var B = x.right;
if (q !== null) {
if (q.left === p) q.left = x;
else if (q.right === p) q.right = x;
}
x.parent = q;
p.parent = x;
x.right = p;
p.left = B;
if (B) B.parent = p;
}
function leftrotate (p) { // rotiert p rauf nach x, x nach links
var x = p.parent;
var q = x.parent;
var B = p.left;
if (q !== null) {
if (q.left === x) q.left = p;
else if (q.right === x) q.right = p;
}
p.parent = q;
x.parent = p;
p.left = x;
x.right = B;
if (B) B.parent = x;
}
function remove_node (n) {
var p = n.parent;
return n.value;
}
function remove (k, node) {
var n = find_node(k, node);
if (n) return remove_node(n);
return false;
}
function replace_value(k,v,node) {
if (!node) throw "replace_value";
if (node.key === k) {
node.value = v;
return true;
}
return false;
}
function replace(k,v, node) {
var record = find_node(k,node);
if (record) return replace_value(k,v,record);
return false;
}
function find_node(k, node) {
node = node || root;
if (k === node.key) return node;
if (k < node.key) {
if (node.left) return find_node(k, node.left);
}
if (k > node.key) {
if (node.right) return find_node(k, node.right);
}
return false;
}
function find(k) {
var node = find_node(k);
if (node) return node.value;
}
function inorder(f, node) {
node = node || root;
if (node.left) inorder(f, node.left);
if (typeof f === "function") f(node.key, node.value, node.type, size(node));
else throw "inorder function fails";
if (node.right) inorder(f, node.right);
return true;
}
function print () {
return inorder(function (k, v, t,s) {
console.log("+ node: key="+k+", value="+v+", type="+t+", size="+s);
});
}
var me = this;
me.insert = insert;
me.remove = remove;
me.replace = replace;
me.find = find;
me.inorder = inorder;
me.print = print;
return Object.freeze(me);
}
var rb = new RedBlackTree();
console.log("print");
rb.insert(1, "Hi");
rb.insert(2, "Hallo");
rb.insert(3, "Gut");
console.log("find");
console.log(rb.find(2));
console.log("print");
rb.print();
/*
print
find
Hallo
print
+ node: key=1, value=Hi, type=BLACK, size=3
+ node: key=2, value=Hallo, type=BLACK, size=2
+ node: key=3, value=Gut, type=BLACK, size=1
*/
Es wird noch ein Weilchen dauern, bis das ein Redblacktree ist. Aber auch diesen sollte man mal ausprobieren. Moeglicherweise kann man ihn einsetzen. Ausserdem hilft sein seltsames Design, das Design von Bäumen zu verstehen.
Das war jetzt BST insert in 30 Sekunden, oder BST find in 30 Sekunden programmiert, aber den 2. Level habe ich noch nicht. Vollstaendig kann ich das erst, wenn ich sie auch aus dem FF balancieren kann. So in 3-4 Varianten, AVL, Splay und RB, und 2-3-4 zum Beispiel.
Samstag war ich mit Racker da, heute am Montag fahren wir nochmal. Alles in Ordnung. Sogar viel besser, als ich erst dachte. Wir waren um 21 Uhr wieder zuhause, dabei waren wir schon um 14 Uhr da. Das war ein toller Ausflug für mich. Gestern war Racker auch total gut gelaunt. Ich freue mich schon auf den Nachmittag, denn die Praxis ist einsame Spitze.
Natürlich vergesse ich jetzt kurz was zu coden und amüsiere mich so. Von 6.046j schleicht die vorletzte Lektion auf meine Platte. Alles ist im Lot. Für meine soziale Situation quasi hervorragend.
Wo ich auf den Schnittkonstanten object[key] glotze, sehe ich aber auch Funktionen, in denen if (ch === "A" || c === "B") vorkommt, die quasi je konstant sind. Ich denke, hiermit kann man ein paar object[key] Zugriffe noch auf kleineren Code, die aktuelle Variable zu vergleichen, bringen. Das wird wohl dann noch cheaper sein.
Was vernuenftiges, das gesamte Programm betreffend, erhalte ich aber auch nur, wenn ich die Generierung der Spans und das Einfuegen aller anderen Elemente auch ueberarbeite. Tokenizer und Scanner sind aber zwei voellig unabhaengige Komponenten im Code, dass man sie jederzeit ohne den Highlighter einsetzen kann. Man kann sie praktisch mit Copy + Paste in ein eigenes Modul verwandeln. Bei denen habe ich wie sonst auch dran gedacht.
Der Plotter ist hingegen eine durcheinandergeratene Sammlung von Funktionen geworden, aber ich Gedenke, als naechstes anstatt O, T und Omega einfach c, n0, f(n) und g(n) zu verwenden und das richtig zu beschriften und zu bounden. Jetzt sehe ich die Beschriftung mit O, T und Omega schon als falsch an. Jedenfalls muss man da was richtiges Eintragen, mit c, n0, f(n) und g(n) kann man das aber bereits richtig angeben, dass man es ablesen kann. Das Weglassen von niedrigeren Termen und den Konstanten fuer die O Bezeichnung kann man mit O(g(n)) statt mit function O dann auch nachvollziehbar zeigen. Kann man doch so nachvollziehen, oder?
Die Analyse dann Heiter bis SWT..
Hier ist also das options Objekt neu zu formulieren, und dann natuerlich der Programmablauf. Nervig waere das, wenn ich fuer das Stueckchen Code erstmal einen Programmablaufplan zeichnen muesste. Darum verzichte ich auf Notationen. Aber richtig ist, ein Drag-und-Drop-Diagramm-Tool, mit Codegenerator, das waere mal wieder eine Steigerung. Den Parser kann man da auch gebrauchen und einbauen, da muss man nicht alles doppelt schreiben.
Oder nicht ganz so ernst.
Graphentheorie. Der kürzeste Pfad ist die kleinste Summe ∑ aller Gewichte w der Edges E im Graphen G = {V,E}, zwischen dem Knoten u (Start) und v (Ziel). Der Dijkstra Algorithmus behandelt positive Integer. Der Bellmann-Ford Algorithmus kann auch negative Zahlen. Einfache Mathematik aber abstraktes Beispiel Integer.
Klingt schwer? Gut. Ich stelle mal meine Vereinfachung vor. Wir stellen uns die Gewichte als richtige Strecken und Pfade als richtige Gesamtstrecken vor. Die Edges haben Gewichte wie 1km, 2km, 3km, oder auch -3km, was einen Umweg auf der Gesamtstrecke von -3km signalisiert.
Vorher hatte ich es geschafft, aus reiner Faulheit, Objektliterale zu nutzen, mit einem Array.indexOf() auf eine EXTRA-Suche um jeweils O(n) PRO keyword gebracht. Ich glaube, ich weiss jetzt, was Array.indexOf(keyword) kostet. O(n). Jedesmal neu bis zum jeweiligen Keyword durchzulaufen, oder ganz und -1 returnen. Vermutung: object[key] ist schneller. Moeglicherweise genausoschnell, aber das ist vermutet, wie ein array[0], wenn der [0] der gleiche HashingAlgorithmus zu Grunde liegt wie dem object[key], es handelt sich um JavaScript. Behauptung: Im Schnitt (on average) erreiche ich mit object[key] quasi konstante O(1) Zeit um das Keyword zu finden und abzugleichen auf einem dann bereits in O(n) laufenden Tokenizer/Parser.
var keywords = [ "if", "else" ];
if (keywords.indexOf("else") > -1) {}
Gestern: Als ich gerade meinen ersten Strukturen von Array nach Objekt aenderte, war ich zuversichtlich. Gerade habe ich die anderen Funktionen gesehen, fuer die einzelnen Operatoren. Ich denke, ich lerne meinen Teil aus der Algorithmenklasse gerade. Denn ich koennt den unendlich optimieren. Das wird genaugenommen einige Stunden (oder eine oder zwei reines umschreiben) dauern. Mit der klemmenden Tastatur und dem lahmen Rechner aber noch eine bis drei länger. Der Code ist lang und der Editor wird langsamer.
var keywords = {
"if":true,
"else":true
};
var punctuators = {
"=":true,
"==":true,
"===":true,
...
};
var whitespaces = {
"\u000a":true,
"\u000d":true,
"\u2028":true
};
if (keywords["else"]) {}
Anstelle von punctuators.indexOf("===") > -1 compute ich in Zukunft noch punctuators["==="]. Wenn ich jetzt die Engine dahinter schreiben wuerde, &implies; wuerde ich die Behauptung und wahrscheinlich die Vermutung erfuellen (Und diese implikation ist richtig, weil ich die Engine nicht geschrieben habe/schreiben würde).
Ich glaube das Ding ist bereits sichtbar schneller. Die grossen alten JavaScript Dokumente schleichen nicht mehr. Das Einfuegen der Elemente im DOM und das sich verlaengernde Dokument geht deutlich schneller auf meinem alten Rechner, aber springen tut so ein langes Dokument trotzdem.
Das Menue muesste zum Beispiel als Overlay Feld und Menue designt werden, dass sich die Laenge nicht mehr veraendert. Sowas kann man da machen. Anderseits war das auch nur eine Idee und kein geplantes Program. Auf Blatt Papier nach Lehrbuch habe ich vor zehn Jahren versucht. Heute spiel ich mal mit ner Idee rum, dieses "oh ich habe ein geiles Softwareengineeringbuch gelesen" Image habe ich vor ein paar Jahren mit der letzten Wohnung verloren, als ich ein halbes Jahr kein Hartz IV kriegte und meine reichen Eltern nicht einlenkten, sondern die Folge mitprovozierten. Die Bücher mußte ich alle stehen lassen. Meine Eltern habe ich später aus entsprechenden Gründen dann auch verlassen. Die Geschichte erzaehle ich uebrigens als MC Edwin Hold von Zeit zu Zeit.
Die neue Billigtastatur hakt nach ein paar Anschlägen schon stärker als die alte!!! Muß ich wohl auf den Scheck warten, bis ich wieder programiere.
Klemmende Tasten. Diese Tastatur hatte 2,99EUR gekostet. Ich schliesse die andere wieder an. Ich muss jeden 2. Buchstaben doppelt mit festem Aufdruck wiederholen. Ich hab damit nichtmal diese Frontpage neu schreiben koennen, und habe das gleiche noch mit /hiphop vor.
Samstag. Ich fahre mit Racker zum Tierarzt. Vielleicht hoere ich mir unterwegs 6.046j im MP3-Player an. Kommt auf Racker an. Davon gibt es Audio. Ich habe die Asymptoten, sowie das korrekte weglassen von Konstanten und lower-order terms zur Errechnung der Big O Formel jetzt 100% begriffen. Ist gar nicht schwer.
Sobald ich neue Tasten habe, mache ich aber mit dem Parser weiter. Die Regex Grammatik fehlt noch und die Korrektur, alle keywords.indexOf(token) und /key|word|if|else/.test(token) eliminieren (es macht den Parser quadratisch). Und einiges andere, um es fast (schnell) zu machen, hardcoden (siehe function probe()). Oder heute abend (hehe, ich hab schon lange Bock drauf, weiter zu coden).
Schon in ein paar Tagen geht es weiter mit Grafiken, ich bin mit den Dreiecken doch noch nicht fertig. Die letzten liegen nicht auf dem Einheitkreis. Ich hab da noch voll Spass dran.
Noch eine Introduction to Algorithms?
Jawohl. Die Dritte. Diese ist vor allem mathematiklastig. Und auch als Audio für unterwegs verfügbar. Da kann man dann genau zuhören, habe ich mit Lektion 2 schon gemacht und mir die Big O Notation endlich auswendig gelernt. Mit passenden Konstanten c so dass c * f(n) &LessSlantEqujal; g(n). und so.
Lil O und Klein Omega (ℴ und ω) sind nicht nur < oder > c * f(n), sondern auch so definiert, das es fuer ALLE c gilt und nicht nur ausgesuchte, wie bei O und Ω moeglich ist.
Das wird gleich noch richtig schwierig (sieht nur aus, zum wiederholen sind die Audios gut fuer morgens auf den Weg). Randomized Quicksort und Randomized Select werden analysiert. Was ich jetzt weiss ist, wie ich das k-te Element finde.
War schon am überlegen aufzustehen, und randomized Quicksort und Randomized Selection Sort zu schreiben. Randomizd heisst, dass der Pivot zufaellig gewaehlt wird.
Ich will mein angefangenes Dokument irgendwie auch fortsetzen. Das war vor zwei Monaten, als ich CS61B und 6.006 nacheinander gemacht (<=>mit Algorithmen angefangen, vor zehn Jahren hatte ich ein Buch darüber, Algorithmen in C) hatte. Und natürlich gehoert das zu neinen Favoriten. Vor allem die Analyse meiner eigenen ist mir dadurch bereits sehr sehr nahe gekommen. Ich werde einiges lassen, zum Beispiel "in syntax.js und Array.indexOf(key) statt object[key]".
Noch eine Introduction to Algorithms.
Oh dieses Arbeitsamt. Nicht nur, daß sie vergassen, meinen Scheck überhaupt loszuschicken.
Anstatt mir das Geld auszuzahlen, haben wir einen Abschlag bekommen, den wir uns dann geteilt haben. Die Mitarbeiterin hatte mir versprochen, daß der Scheck dann bis Mittwoch da ist. Ist er nicht.
War ja auch logisch. Seit wann schaffen die es in drei Werktagen?
Kurz was unsinniges, bevor ich wieder bei der Sache bin. Ich wollte dem Plotter noch was zum benchmarken beibringen. Ich hab dann was eingehackt, was meiner eigentlichen Idee, die Messung in der zu messenden Funktion durchzufuehren (measures.push(Date.now())), nicht nachkommt, aber auch einen verblueffenden Graphen zeigt.
Ich hab jetzt acht Mathesemester (alle) (plus Zusatzmaterial, wie Highlights of Calculus (a Big Picture)), die kann ich gar nicht auf einmal machen. Das Gucken von Physik I, II, III werde ich diesen Monat nicht mehr schaffen. Aber darauf freue ich mich, wie auf die anderen Courses, die da offen sind. Ich hab jetzt erstmal zu tun, durch die Mathematik durchzukommen.
Achso, 6.033 habe ich erst gestern entdeckt. Computer Systems Engineering beginnt mit dem
Linker. So konnte ich von der symtab direkt bis text, rodata, data, symtab neu ordnen. Der Kurs wird
noch interessant.
Ich vermute, danach werde ich wieder C/C++ probieren, wie frueher. Denn auch JS "only" wird
irgendwann wieder (leicht) zu wenig, zu langweilig, auch weil man seine JS Engine in C++
schreiben sollte. Oder was anderes.
Der Linux Kernel war frueher ein Hobby. Ich hatte Addison-Wesley und O`Reilly Bücher wie
Linux Kernelprogrammierung, Understanding the Linux Kernel, Linux Device-Drivers. Ich glaube
zwar nicht, da noch reinzukommen. Aber es war mal noch alles offen. Vor ein paar Jahren. Nur
hatten meine Alten meine Zukunft da bereits beschlossen.
Jetzt muss ich erstmal Mathe nachholen. Der Plotter kann noch keine Benchmarks und fuer die ersten Versuche der Differentiation habe ich Verbesserungen, weil ich es ein wenig besser verstehe, als an dem Tag.
Neben der Matrize mit den fixen Attributen ist mir nun noch die mit dem Array eingefallen, sie ist dynamisch und man kann rows: und cols: angeben. Den Rest erledigen Algorithmen. Damit meine ich aus Kontrollstrukturen wie for zusammengesetzte (meist hoffentlich) lineare Operationen auf dem Array.
In 18.06SC Lineare Algebra gibt es eine Menge ueber Matrizen zu lernen. Das Loesen von linearen Gleichungen ist das wichtigste, was Matrizen koennen, oder?
/*
Mat4x4 (Anriss)
Umstaendliche Variante.
Benutzt je ein definiertes Attribut pro Determinante.
Jede Zahl wird einzeln zugewiesen.
Parameter sind explizit.
Der Construtor kann dank der instanceof Zeile aber noch
mit apply gerufen werden und uebergibt dann selbst explizit an new.
Jedenfalls muss man so jede Matrix einzeln schreiben.
Darum habe ich mir was neues ausgedacht.
*/
function Mat4x4 (a1,a2,a3,a4, b1,b2,b3,b4, c1,c2,c3,c4, w1,w2,w3,w4) {
"use strict";
if (this instanceof Mat4x4 === false) {
return new Mat4x4(a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,w1,w2,w3,w4);
}
this.set.apply(this, arguments);
return Object.seal(this);
}
Mat4x4.prototype = Object.freeze({
constructor: Mat4x4,
set: function(a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,w1,w2,w3,w4) {
this.a1 = a1; this.a2 = a2; this.a3 = a3; this.a4 = a4;
this.b1 = b1; this.b2 = b2; this.b3 = b3; this.b4 = b4;
this.c1 = c1; this.c2 = c2; this.c3 = c3; this.c4 = c4;
this.w1 = w1; this.w2 = w2; this.w3 = w3; this.w4 = w4;
return this;
}
});
/*
Matrix (Anriss)
benutzt eine rows und cols property.
und einen typed array (ansagbar)
und liest speichert mit index-algorithmen.
Parameter sind direkt Arrays. Oder ein Options Objekt, mit mehreren Angaben.
Was besser ist als Parameter, deren Reihenfolge sich keiner merken kann.
Vielleicht ist Float64 zu gross fuer die meisten defaults, aber das kann ich
nicht feststellen, keiner nutzt die ;-)
*/
function Matrix (options) {
"use strict";
if (!(this instanceof Matrix)) return new Matrix(options);
if (typeof options !== "object") throw "options object {rows,cols[,d]} expected";
if (!options.rows) throw "rows: missing";
this.rows = options.rows;
if (!options.rows) throw "cols: missing";
this.cols = options.cols;
this.d = options.arrayType ? new options.arrayType(this.rows * this.cols) : new Float64Array(this.rows * this.cols);
Object.freeze(this);
if (options.d) this.set(options.d);
}
Matrix.prototype = Object.freeze({
constructor: Matrix,
set: function (d) {
if (Array.isArray(d[0]) || d[0].length) {
/* [
[1,0,0]
[0,1,0]
[0,0,1]
] */
for (var r = 0, l = this.rows; r < l; r++) {
for (var c = 0, m = this.cols; c < m; c++) {
this.d[r*m + c] = d[r][c];
}
}
} else {
/* [1,0,0,0,1,0,0,0,1] */
for (var i = 0, l = this.rows * this.cols; i < l; i++) {
this.d[i] = d[i];
}
}
return this;
}
});
var m = new Matrix({ rows: 2, cols: 2, d: [[1,0],[0,1]] });
console.dir(m);
/*
{ rows: 2,
cols: 2,
d:
{ '0': 1,
'1': 0,
'2': 0,
'3': 1,
BYTES_PER_ELEMENT: 8,
get: [Function: get],
set: [Function: set],
slice: [Function: slice],
subarray: [Function: subarray],
buffer:
{ '0': 0,
'1': 0,
'2': 0,
'3': 0,
'4': 0,
'5': 0,
'6': 240,
'7': 63,
'8': 0,
'9': 0,
'10': 0,
'11': 0,
'12': 0,
'13': 0,
'14': 0,
'15': 0,
'16': 0,
'17': 0,
'18': 0,
'19': 0,
'20': 0,
'21': 0,
'22': 0,
'23': 0,
'24': 0,
'25': 0,
'26': 0,
'27': 0,
'28': 0,
'29': 0,
'30': 240,
'31': 63,
byteLength: 32 },
length: 4,
byteOffset: 0,
byteLength: 32 } }
*/
Wie man sehen kann, beginnt die zweite Matrix dynamisch. Die enstsprechenden Transpose und Invertfunktionen kann man algorithmisch schreiben. Die Codeterminanten oder wie die hiessen, die kann man auch berechnen. In dem Kurs Lineare Algebra gibt es eine Menge Operationen, die man implementieren kann zu lernen. Und wenn man zum Beispiel Computergrafik berechnen will, braucht man einige Grundlagen daraus.
Wenn man damit Grafikkoordinaten verrechnen will, stelle ich mir das so vor, dass ich gfx.skewY(vertices, deg(20)) schreibe und dann intern die entsprechende Berechnung mit jedem Punkt durchgefuehrt wird. Intern wird eine der Matrizen verwendet und dann durch alle vertices durchgeroutet. Nicht ueberall brauche ich dabei die Matrix, aber manchmal schon. Sie ist aber als System zur Loesung von Gleichungen gedacht.
Dem Canvas sollte ich das Visualisieren der Gleichungen beibringen, so wie sie an der Tafel stehen.
Jetzt schreibe ich viele Section Tags.
Das php Script, was in das Index Template eine handvoll Files einsetzt, das liegt seit ich dieses php/mysql Dokument letztes Jahr geschrieben hab ungenutzt rum.
<?
$app = new Application("commentsapp", "comments");
?>
Beim Starten from Scratch werden andere Anforderungen an das Skript bewußt;. Im uralten Dokument lamp.php probiere ich den Datenbankzugriff, nachdem ich die gelöscht hatte. Es waren nur alte unbenutzte Installationen von Blogs, Wiki, Foren. Spammer hatten das alte Forum lahmgelegt, und weil der Abuse Alarm losging, habe ich nach ein paar Stunden schwitzen, was denn los sei, die Datenbank geloescht. Leider hatte mich die Lust auf PHP (obwohl ich die Sprache super finde) direkt wieder verlassen.
var x = 10, y = 11;
var z = {x,y};
JSON.stringify(z);
Mich hatte die Lust, JavaScript zu lernen gepackt. Das lässt mich auch heute nicht los. Wenn man auf ToValue(ast) klickt, fuehre ich erst den Tokenizer, dann den Parser aus. Der Parser baut aus den Tokens einen AST. Und dann fuehrt ToValue(ast) den AST aus. Heraus kommt das stringifizierte Objektliteral, was ich bereits der EcmaScript 6 Spezifikization entnahm. Wie man sieht, schreibe ich {x,y} statt {x:x,y:y}. Wenn man auf eval im Browser klickt, gibt es in einem ES5 Browser von heute einen SyntaxError.
Keine Sicherheitslücke, sondern das aktuelle Objektliteral. EcmaScript 6 ist für nächstes Jahr bereits geplant, und am Ende dieses Jahres wird eine fast fertige Spezifikation vorgestellt, die nächstes Jahr dann bereits zum neuen Standard wird.
Und das Destructuring Assignment, von dem bereits geredet wird, wird eines der fettesten neuen Features der Sprache, um viele lange Zeilen Code zu vermeiden, denn man spart sich das doppelt und dreifache Zuweisen von Variablen, dadurch, dass man sie in einem Schritt rausholt oder einsetzt und die Variablen dazu gleich mit erzeugt. {x,y} ist gegenüber {x:x,y:y} eine Vereinfachung. Aber das ist noch nichts.
Dennoch hatte mich das JavaScript Fieber so sehr gepackt, dass ich einen ersten Parser schrieb. Das war im Januar. Am Ende des Februars und den Maerz habe ich dann Datenstrukturen und Algorithmen gemacht. Das Dokument dazu ist nur noch nicht so fertig. Dadurch konnte ich mittlerweile die Komplexität des Parsers ermitteln. Ich fasse mich kurz, das computen von object[key] ist im Schnitt am guenstigsten und [].indexOf(key) und /(Reg|Exp)/.test(key) verlieren hier beide.
Der Graph zeigt eine Komplexitaetsanalyse, aber es geht noch besser. Also in CS61B habe ich bereits f(n) ∈ O(g(n)) kennengelernt. Und auch, dass man mit der Konstante c in der Form c * g(n) eine Obergrenze für f(n) festlegt. Diese Obergrenze nennt man O (Order, O von, Big O, in der Ordnung von). Zum Zeichnen von T(n) oder f(n) habe ich selbige einfach angegeben. Die Form der Konstante C wird hier aber nicht beachtet. Beim ersten Versuch hatte ich C * n bzw 1/2C * n in O und Omega ausprobiert, habe das aber nicht weiter vertieft. Es gibt keine C Konstante im options-Objekt, womit der Plot konfiguriert wird wird. Es gibt O, Omega und T statt f und g. Ich denke, mir hier nochmal Gedanken machen zu wollen. Und zu wiederholen. Anlass ist eine Wiederholung von CS61B und 6.006 mit 6.046j.
Also ich werde das ganze Script und Css erstmal inlinen. Ich hatte schon "(Even) Faster Websites" geschrieben (so als Angeberslogan) und dann nochmal ueberlegt, das kleine Ende der Datei zu blockieren. Doch da ich alles HTML und CSS bereits ueber dem Script hab ist die Illusion bereits perfekt.
Lets try it. Alle paar JavaScript Files inlinen. Nach allem anderen. Das CSS natürlich im Head, damit die Styles direkt applied werden koennen. Als wuerde man noch auf das Laden der anderen warten. Vielleicht ist es sogar even slower. Vielleicht blockiert es Chrome, waehrend alle anderen Responsive sind. Wer weiss? Vielleicht ist es fast. Vielleicht slower. Vielleicht auch egal.
Der Gedanke, wo es Sinn macht, den zu verlieren, der handelt vom Caching. Die ge-inline-ten Skripte und CSS koennen nicht mehr im HTTP-Cache aufgelistet werden.
Letzter Inhalt: april
Dort sind alle bislang gemachten Sachen einsehbar.