Skip to content

Commit 56b7461

Browse files
marijnhmarijnh
committed
Add files needed to show Chapter 22 in the sandbox
1 parent 58d8d09 commit 56b7461

File tree

6 files changed

+373
-1
lines changed

6 files changed

+373
-1
lines changed

‎bin/chapter_info.js‎

Lines changed: 32 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ var fs = require("fs");
66

77
var output = [], failed = false;
88

9-
var allSolutions = fs.readdirSync("code/solutions/").filter(function(file) { return !/^2[01]/.test(file); });
9+
var allSolutions = fs.readdirSync("code/solutions/").filter(function(file) { return !/^2[012]/.test(file); });
1010

1111
var dir = fs.readdirSync(".");
1212
dir.sort();
@@ -119,6 +119,37 @@ dir.forEach(function(file) {
119119
output.push(chapter);
120120
});
121121

122+
output.push({
123+
title: "How JavaScript is so Fast",
124+
number: 22,
125+
start_code: "<!-- This chapter exists in the paper book, not in the online version -->\n\n<script>\n runLayout(forceDirected_simple, treeGraph(4, 4));\n</script>\n",
126+
include: ["code/draw_graph.js", "code/chapter/22_fast.js"],
127+
exercises: [
128+
{name: "Pathfinding",
129+
file: "code/solutions/22_1_pathfinding.js",
130+
number: 1,
131+
type: "js",
132+
code: "function findPath(a, b) {\n // Your code here...\n}\n\nvar graph = treeGraph(4, 4);\nvar root = graph[0], leaf = graph[graph.length - 1];\nconsole.log(findPath(root, leaf).length);\n// → 3\n\nleaf.connect(root);\nconsole.log(findPath(root, leaf).length);\n// → 1\n",
133+
solution: fs.readFileSync("code/solutions/22_1_pathfinding.js", "utf8")
134+
},
135+
{name: "Timing",
136+
file: "code/solutions/22_2_timing.js",
137+
number: 2,
138+
type: "js",
139+
code: "",
140+
solution: fs.readFileSync("code/solutions/22_2_timing.js", "utf8")
141+
},
142+
{name: "Optimizing",
143+
file: "code/solutions/22_3_optimizing.js",
144+
number: 3,
145+
type: "js",
146+
code: "",
147+
solution: fs.readFileSync("code/solutions/22_3_optimizing.js", "utf8")
148+
}
149+
]
150+
});
151+
152+
122153
if (allSolutions.length) {
123154
console.error("Solution files " + allSolutions + " were not used.");
124155
failed = true;

‎code/chapter/22_fast.js‎

Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
function GraphNode(pos, edges) {
2+
this.pos = new Vector(Math.random() * 1000,
3+
Math.random() * 1000);
4+
this.edges = [];
5+
}
6+
GraphNode.prototype.connect = function(other) {
7+
this.edges.push(other);
8+
other.edges.push(this);
9+
};
10+
GraphNode.prototype.hasEdge = function(other) {
11+
for (var i = 0; i < this.edges.length; i++)
12+
if (this.edges[i] == other)
13+
return true;
14+
};
15+
16+
function treeGraph(depth, branches) {
17+
var graph = [];
18+
function buildNode(depth) {
19+
var node = new GraphNode();
20+
graph.push(node);
21+
if (depth > 1)
22+
for (var i = 0; i < branches; i++)
23+
node.connect(buildNode(depth - 1));
24+
return node;
25+
}
26+
buildNode(depth);
27+
return graph;
28+
}
29+
30+
var springLength = 40;
31+
var springStrength = 0.1;
32+
33+
var repulsionStrength = 1500;
34+
35+
function forceDirected_simple(graph) {
36+
graph.forEach(function(node) {
37+
graph.forEach(function(other) {
38+
if (other == node) return;
39+
var apart = other.pos.minus(node.pos);
40+
var distance = Math.max(1, apart.length);
41+
var forceSize = -repulsionStrength / (distance * distance);
42+
if (node.hasEdge(other))
43+
forceSize += (distance - springLength) * springStrength;
44+
var normalized = apart.times(1 / distance);
45+
node.pos = node.pos.plus(normalized.times(forceSize));
46+
});
47+
});
48+
}
49+
50+
function runLayout(implementation, graph) {
51+
var totalSteps = 0, time = 0;
52+
function step() {
53+
var startTime = Date.now();
54+
for (var i = 0; i < 100; i++)
55+
implementation(graph);
56+
totalSteps += 100;
57+
time += Date.now() - startTime;
58+
drawGraph(graph);
59+
60+
if (totalSteps < 4000)
61+
requestAnimationFrame(step);
62+
else
63+
console.log(time);
64+
}
65+
step();
66+
}
67+
68+
function forceDirected_forloop(graph) {
69+
for (var i = 0; i < graph.length; i++) {
70+
var node = graph[i];
71+
for (var j = 0; j < graph.length; j++) {
72+
if (i == j) continue;
73+
var other = graph[j];
74+
var apart = other.pos.minus(node.pos);
75+
var distance = Math.max(1, apart.length);
76+
var forceSize = -1 * repulsionStrength / (distance * distance);
77+
if (node.hasEdge(other))
78+
forceSize += (distance - springLength) * springStrength;
79+
var normalized = apart.times(1 / distance);
80+
node.pos = node.pos.plus(normalized.times(forceSize));
81+
}
82+
}
83+
}
84+
85+
function forceDirected_norepeat(graph) {
86+
for (var i = 0; i < graph.length; i++) {
87+
var node = graph[i];
88+
for (var j = i + 1; j < graph.length; j++) {
89+
var other = graph[j];
90+
var apart = other.pos.minus(node.pos);
91+
var distance = Math.max(1, apart.length);
92+
var forceSize = -1 * repulsionStrength / (distance * distance);
93+
if (node.hasEdge(other))
94+
forceSize += (distance - springLength) * springStrength;
95+
var applied = apart.times(forceSize / distance);
96+
node.pos = node.pos.plus(applied);
97+
other.pos = other.pos.minus(applied);
98+
}
99+
}
100+
}
101+
102+
function forceDirected_novector(graph) {
103+
for (var i = 0; i < graph.length; i++) {
104+
var node = graph[i];
105+
for (var j = i + 1; j < graph.length; j++) {
106+
var other = graph[j];
107+
var apartX = other.pos.x - node.pos.x;
108+
var apartY = other.pos.y - node.pos.y;
109+
var distance = Math.max(1, Math.sqrt(apartX * apartX + apartY * apartY));
110+
var forceSize = -repulsionStrength / (distance * distance);
111+
if (node.hasEdge(other))
112+
forceSize += (distance - springLength) * springStrength;
113+
114+
var forceX = apartX * forceSize / distance;
115+
var forceY = apartY * forceSize / distance;
116+
node.pos.x += forceX; node.pos.y += forceY;
117+
other.pos.x -= forceX; other.pos.y -= forceY;
118+
}
119+
}
120+
}
121+
122+
function forceDirected_novector(graph) {
123+
var forcesX = [], forcesY = [];
124+
for (var i = 0; i < graph.length; i++)
125+
forcesX[i] = forcesY[i] = 0;
126+
127+
for (var i = 0; i < graph.length; i++) {
128+
var node = graph[i];
129+
for (var j = i + 1; j < graph.length; j++) {
130+
var other = graph[j];
131+
var apartX = other.pos.x - node.pos.x;
132+
var apartY = other.pos.y - node.pos.y;
133+
var distance = Math.max(1, Math.sqrt(apartX * apartX + apartY * apartY));
134+
var forceSize = -repulsionStrength / (distance * distance);
135+
if (node.hasEdge(other))
136+
forceSize += (distance - springLength) * springStrength;
137+
138+
var forceX = apartX * forceSize / distance;
139+
var forceY = apartY * forceSize / distance;
140+
forcesX[i] += forceX; forcesY[i] += forceY;
141+
forcesX[j] -= forceX; forcesY[j] -= forceY;
142+
}
143+
}
144+
145+
for (var i = 0; i < graph.length; i++) {
146+
graph[i].pos.x += forcesX[i];
147+
graph[i].pos.y += forcesY[i];
148+
}
149+
}
150+
151+
var mangledGraph = treeGraph(4, 4);
152+
mangledGraph.forEach(function(node) {
153+
var letter = Math.floor(Math.random() * 26);
154+
node[String.fromCharCode("A".charCodeAt(0) + letter)] = true;
155+
});

‎code/draw_graph.js‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
// The familiar Vector type.
2+
3+
function Vector(x, y) { this.x = x; this.y = y; }
4+
5+
Vector.prototype.plus = function(other) {
6+
return new Vector(this.x + other.x, this.y + other.y);
7+
};
8+
Vector.prototype.minus = function(other) {
9+
return new Vector(this.x - other.x, this.y - other.y);
10+
};
11+
Vector.prototype.times = function(factor) {
12+
return new Vector(this.x * factor, this.y * factor);
13+
};
14+
Object.defineProperty(Vector.prototype, "length", {
15+
get: function() {
16+
return Math.sqrt(this.x * this.x + this.y * this.y);
17+
}
18+
});
19+
20+
// Since we will want to inspect the layouts our code produces, let's
21+
// first write code to draw a graph onto a canvas. Since we don't know
22+
// in advance how big the graph is, the `Scale` object computes a
23+
// scale and offset so that all nodes fit onto the given canvas.
24+
25+
var nodeSize = 8;
26+
27+
function drawGraph(graph) {
28+
var canvas = document.querySelector("canvas");
29+
if (!canvas) {
30+
canvas = document.body.appendChild(document.createElement("canvas"));
31+
canvas.width = canvas.height = 500;
32+
}
33+
var cx = canvas.getContext("2d");
34+
35+
cx.clearRect(0, 0, canvas.width, canvas.height);
36+
var scale = new Scale(graph, canvas.width, canvas.height);
37+
38+
// Draw the edges.
39+
cx.strokeStyle = "orange";
40+
cx.lineWidth = 3;
41+
graph.forEach(function(origin, i) {
42+
origin.edges.forEach(function(target) {
43+
if (graph.indexOf(target) <= i) return;
44+
cx.beginPath();
45+
cx.moveTo(scale.x(origin.pos.x), scale.y(origin.pos.y));
46+
cx.lineTo(scale.x(target.pos.x), scale.y(target.pos.y));
47+
cx.stroke();
48+
});
49+
});
50+
51+
// Draw the nodes.
52+
cx.fillStyle = "purple";
53+
graph.forEach(function(node) {
54+
cx.beginPath();
55+
cx.arc(scale.x(node.pos.x), scale.y(node.pos.y), nodeSize, 0, 7);
56+
cx.fill();
57+
});
58+
}
59+
60+
// The function starts by drawing the edges, so that they appear
61+
// behind the nodes. Since the nodes on _both_ side of an edge refer
62+
// to each other, and we don't want to draw every edge twice, edges
63+
// are only drawn then the target comes _after_ the current node in
64+
// the `graph` array.
65+
66+
// When the edges have been drawn, the nodes are drawn on top of them
67+
// as purple discs. Remember that the last argument to `arc` gives the
68+
// rotation, and we have to pass something bigger than 2π to get a
69+
// full circle.
70+
71+
// Finding a scale at which to draw the graph is done by finding the
72+
// top left and bottom right corners of the area taken up by the
73+
// nodes. The offset at which nodes are drawn is based on the top left
74+
// corner, and the scale is based on the size of the canvas divided by
75+
// the distance between those corners. The function reserves space
76+
// along the sides of the canvas based on the `nodeSize` variable, so
77+
// that the circles drawn around nodes’ center points don't get cut off.
78+
79+
function Scale(graph, width, height) {
80+
var xs = graph.map(function(node) { return node.pos.x });
81+
var ys = graph.map(function(node) { return node.pos.y });
82+
var minX = Math.min.apply(null, xs);
83+
var minY = Math.min.apply(null, ys);
84+
var maxX = Math.max.apply(null, xs);
85+
var maxY = Math.max.apply(null, ys);
86+
87+
this.offsetX = minX; this.offsetY = minY;
88+
this.scaleX = (width - 2 * nodeSize) / (maxX - minX);
89+
this.scaleY = (height - 2 * nodeSize) / (maxY - minY);
90+
}
91+
92+
Scale.prototype.x = function(x) {
93+
return this.scaleX * (x - this.offsetX) + nodeSize;
94+
};
95+
Scale.prototype.y = function(y) {
96+
return this.scaleY * (y - this.offsetY) + nodeSize;
97+
};
98+
99+
// The `x` and `y` methods of the `Scale` type convert from graph
100+
// coordinates into canvas coordinates.

‎code/solutions/22_1_pathfinding.js‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
function findPath(a, b) {
2+
var work = [[a]];
3+
for (var i = 0; i < work.length; i++) {
4+
var cur = work[i], end = cur[cur.length - 1];
5+
if (end == b) return cur;
6+
end.edges.forEach(function(next) {
7+
if (!work.some(function(work) { return work[work.length - 1] == next; }))
8+
work.push(cur.concat([next]));
9+
});
10+
}
11+
}
12+
13+
var graph = treeGraph(4, 4);
14+
var root = graph[0], leaf = graph[graph.length - 1];
15+
console.log(findPath(root, leaf).length);
16+
// → 4
17+
18+
leaf.connect(root);
19+
console.log(findPath(root, leaf).length);
20+
// → 2

‎code/solutions/22_2_timing.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
function findPath(a, b) {
2+
var work = [[a]];
3+
for (var i = 0; i < work.length; i++) {
4+
var cur = work[i], end = cur[cur.length - 1];
5+
if (end == b) return cur;
6+
end.edges.forEach(function(next) {
7+
if (!work.some(function(work) { return work[work.length - 1] == next; }))
8+
work.push(cur.concat([next]));
9+
});
10+
}
11+
}
12+
13+
var graph = treeGraph(6, 5);
14+
var startTime = Date.now();
15+
console.log(findPath(graph[0], graph[graph.length - 1]).length);
16+
console.log("Time taken:", Date.now() - startTime);

‎code/solutions/22_3_optimizing.js‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
function withIDs(graph) {
2+
for (var i = 0; i < graph.length; i++) graph[i].id = i;
3+
return graph;
4+
}
5+
var graph = withIDs(treeGraph(8, 5));
6+
7+
function findPath_ids(a, b) {
8+
var work = [[a]];
9+
var seen = Object.create(null);
10+
for (var i = 0; i < work.length; i++) {
11+
var cur = work[i], end = cur[cur.length - 1];
12+
if (end == b) return cur;
13+
end.edges.forEach(function(next) {
14+
if (!seen[next.id]) {
15+
seen[next.id] = true;
16+
work.push(cur.concat([next]));
17+
}
18+
});
19+
}
20+
}
21+
22+
var startTime = Date.now();
23+
console.log(findPath_ids(graph[0], graph[graph.length - 1]).length);
24+
console.log("Time taken with ids:", Date.now() - startTime);
25+
26+
function listToArray(list) {
27+
var result = [];
28+
for (var cur = list; cur; cur = cur.via)
29+
result.unshift(cur.last);
30+
return result;
31+
}
32+
33+
function findPath_list(a, b) {
34+
var work = [{last: a, via: null}];
35+
var seen = Object.create(null);
36+
for (var i = 0; i < work.length; i++) {
37+
var cur = work[i];
38+
if (cur.last == b) return listToArray(cur);
39+
cur.last.edges.forEach(function(next) {
40+
if (!seen[next.id]) {
41+
seen[next.id] = true;
42+
work.push({last: next, via: cur});
43+
}
44+
});
45+
}
46+
}
47+
48+
var startTime = Date.now();
49+
console.log(findPath_list(graph[0], graph[graph.length - 1]).length);
50+
console.log("Time taken with ids + lists:", Date.now() - startTime);

0 commit comments

Comments
 (0)