エラトステネスのふるい on JavaScript-1.7/1.8
「エラトステネスのふるい」は、平行プログラミングの基礎的な例としても用いられる。この場合は、各ふるい(sieve)は最初に受け取ったものを素数とし、その担当の素数の倍数を受け取ったらふるい落とし、そうでないものを受け取ったら次のふるいへ渡すコードになる。そして各ふるいがactorとして自律する。このふるいをJS1.7以降のgeneratorで記述している。
<?xml version="1.0"?> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <script type="text/javascript;version=1.8">//<![CDATA[ // Sieve of Eratosthenes var sieve = function sieve(callback) { let prime = yield; if (prime === null) return; callback(prime); let succ = sieve(callback); succ.next(); for (let m = yield; m !== null; m = yield) { if (m % prime !== 0) succ.send(m); } succ.send(null); }; var doRun = function doRun(maxnum) { let writeTo = function (n) { document.getElementById("output").innerHTML += n + "<br/>"; }; let s = sieve(writeTo); s.next(); for (let i = 2; i < maxnum; i += 1) { s.send(i); } try { s.send(null); } catch (ex) {} }; //]]></script> </head> <body> <button type="button" onclick="doRun(100)">run to 100</button> <div id="output"></div> </body> </html>
参考のために、Haskellとかでよく見かけるタイプの遅延リスト式実装のcomprehension版もあげておく。この実装ではふるい(sieve)は、リストの先頭を素数とし、残りをその素数で割り切れないものだけで(遅延)リストつくって次のふるいに渡し、その結果を最初の素数につなげたリストを返す。
<?xml version="1.0"?> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <script type="text/javascript;version=1.8">//<![CDATA[ // Sieve of Eratosthenes // sieve (prime:gtor) = prime:(sieve [i | i <- gtor, i `mod` prime /= 0]) var sieve = function (gtor) { let prime = gtor.next(); yield prime; let sievedGtor = (i for (i in gtor) if (i % prime !== 0)); for (let p in sieve(sievedGtor)) yield p; }; var range = function (s, e) { for (let i = s; i < e; i += 1) yield i; }; var doRun = function doRun(maxnum) { let writeTo = function (n) { document.getElementById("output").innerHTML += n + "<br/>"; }; for (let p in sieve(range(2, 100))) writeTo(p); }; //]]></script> </head> <body> <button type="button" onclick="doRun(100)">run to 100</button> <div id="output"></div> </body> </html>
