A proposed solution to exercise 3.3 from Stepanov and Rose's From Mathematics to Generic Programming. The exercise asks us to graph the number of primes less than n using an analytic approximation.
π = (x) => x / Math.log(x).A Web Worker performs each test of increasing input size and reports back to the main thread with the number of primes found that are less than the input. Only one test actually needs to be run in order to graph the prime-counting function; however, by running each test separately in a WebWorker (each with a successively larger different input size), one can perform a complexity analysis of the various implementations of the Sieve of Eratosthenes.
Using Web Workers in this example also helps us avoid locking up the main user interface thread while the algorithm is executing.
xxxxxxxxxx<meta charset="utf-8"><script src="https://d3js.org/d3.v4.min.js"></script><svg width="960" height="500"></svg><script>var svg = d3.select("svg"), chart, width = svg.attr("width"), height = svg.attr("height"), margin = { left: 50, right: 50, top: 20, bottom: 20 }, worker = new Worker("./worker.js"), min = 1e1, max = 1e7, numTrials = 20, step = (max - min) / numTrials, results = [];chart = svg.append("g") .attr("transform", "translate(0" + "," + -20 + ")");var x = d3.scaleLinear() .domain([0, min]) .range([margin.left, +width - margin.right]);var y = d3.scaleLinear() .domain([0, Infinity]) // Reset after first test. .range([+height - margin.bottom, 10]);var y2 = d3.scaleLinear() .domain([0, Infinity]) // Reset after first test. .range([+height - margin.bottom, 10]);// Analytic Approximation.var π = function(x) { return x / Math.log(x); }axis = chart.append("g") .attr("transform", "translate(0," + y(0) + ")") .call(d3.axisBottom(x) .tickFormat(d3.format("d")));var line = d3.line() .x(function(d) { return x(d.n); }) .y(function(d) { return +y(d.count); });var analyticLine = d3.line() .x(function(d) { return x(d.n); }) .y(function(d) { return +y(π(d.n)); });var rect = svg.append("rect") .attr("x", 0) .attr("y", 0) .attr("width", 0) .attr("height", 3) .attr("fill", "rgb(240, 0, 0)");path = chart.append("path");// Run tests to generate primes, starting at those primes// less than 1,000 and ending at those primes less than 100,000,000.let tests = d3.range(min, max, step).map(function(d) { return { n: d}; });// Dispatcher.worker.onmessage = function(event) { switch (event.data.type) { case "end": return ended(event.data); }};// Start first test.worker.postMessage(tests.shift());// Render analytics when computation is done.function ended(data) { var yMax; results.push(data); // Progress bar tweening, remove when all tests have run. rect.transition().duration(200) .attr("width", results.length * width / numTrials) .on("end", function() { if (results.length === numTrials) { d3.select(this).remove(); } }); yMax = d3.max(results, function(d) { return d.count; }) || Infinity; y2Max = d3.max(results, function(d) { return d.elapsed; }) || Infinity; x.domain([0, results[results.length - 1].n]); axis.call(d3.axisBottom(x) .tickFormat(d3.format("d"))); // Update y-axis domain. y.domain([0, yMax * 1.1]); line.y(function(d) { return +y(d.count); }); y2.domain([0, y2Max * 1.1]); path.datum(results) .attr("d", line) .attr("fill", "none") .attr("stroke-opacity", 0.2) .attr("stroke", "#000") .attr("stroke-width", "2px"); // Render the final graph. if (results.length === numTrials) { label = chart.selectAll(".label") .data(results); chart.append("path") .datum(results) .attr("d", analyticLine) .attr("fill", "none") .attr("stroke-dasharray", "5, 5") .attr("stroke", "#eb9394") .attr("stroke-width", "2px"); label.enter().append("text") .attr("x", function(d) { return x(d.n); }) .attr("y", function(d) { return +y(d.count); }) .attr("text-anchor", "end") .attr("dx", -10) .attr("dy", -10) .attr("font-family", "helvetica") .attr("fill", "#000") .attr("fill-opacity", 0) .transition() .duration(400) .ease(d3.easeCircle) .attr("fill-opacity", 1) .text(function(d, i) { return d3.format(",")(d.count); }); circle = chart.selectAll("circle") .data(results); circle.enter().append("circle") .attr("cx", function(d) { return x(d.n); }) .attr("cy", function(d) { return +y(d.count); }) .attr("r", 5) .attr("fill", "#000"); elapsed = chart.selectAll(".elapsed") .data(results); elapsedCircle = chart.selectAll(".elapsedCircle") .data(results); elapsedCircle.enter().append("circle") .attr("cx", function(d) { return x(d.n); }) .attr("cy", function(d) { return +y2(d.elapsed); }) .attr("stroke-width", "1px") .attr("stroke", "#aaa") .attr("r", 3) .attr("fill", "#ffbf87"); path.attr("stroke-opacity", 1); } else { // Run the next test. worker.postMessage(tests.shift()); }}</script> https://d3js.org/d3.v4.min.js