JavaScript で素数の無限リストを作ってみる

もうだいぶ前になるが、Erlang で素数の無限リストを作った。今度は JavaScript で同じものを書いてみる。

方針は、前回同様、Priority Queue (Pairing Heap)を用いた Wheel Sieve を遅延リストで実装するというもの。

まず遅延リスト。以下のような感じになった。

// 遅延リストのコンストラクタ。head は先頭要素、next は残りの要素。
function LL(head, next) {
  this.head = head;
  this.next = next;
}
//空の遅延リスト
LL.emptyLL = { empty: true };
//先頭要素と別の遅延リストから新しい遅延リストを作る関数
LL.construct = function (car, cdr) {
  return new LL(car, function() { return cdr; });
}
//可変個の引数とって遅延リストに変える
LL.of = function() {
  var arr = Array.prototype.slice.call(arguments);
  return (arr.length == 0) ? LL.emptyLL 
       : (arr.length == 1) ? new LL(arr[0]) 
       : LL.construct(arr[0], LL.of.apply(this, arr.slice(1)));
}
LL.hasNext = function(list) { return list && list.next; }

LL.prototype.empty = false;

//index番目の要素を返す関数
LL.prototype.nth = function(index) {
  var primes = this;
  for (i = 0; i < index; i++) primes = primes.next();
  return primes.head;
}

次に倍数リストを保持する Priority Queue。

// Priority Queueのコンストラクタ。compositesは倍数リスト、lowersは
// このキューより優先度の低いキューの遅延リスト。
function PQ(composites, lowers) {
  this.composites = composites;
  this.lowers     = lowers ? lowers : LL.emptyLL; 
}
PQ.prototype.empty = false;

//他のキューより優先度が高いか判別する
PQ.prototype.lessThan = function(another) {
  return this.composites.head < another.composites.head;
}
PQ.emptyQueue = { empty: true };
PQ.empty = function(pq) { return !pq || pq.empty; }

PQ.prototype.join = function(lower) {
  return new PQ(this.composites, LL.construct(lower, this.lowers));
}
//2つのキューをマージする
PQ.merge = function(pq1, pq2) {
  return PQ.empty(pq1) ? pq2
       : PQ.empty(pq2) ? pq1
       : pq1.lessThan(pq2) ? pq1.join(pq2)
       :                     pq2.join(pq1);
}
// キューの遅延リストをまとめてマージする
PQ.mergeAll = function(queues) {
  if (queues.empty) return PQ.emptyQueue;
  if (!LL.hasNext(queues)) return queues.head;

  var rest = queues.next();
  var next = LL.hasNext(rest) ? rest.next():LL.emptyLL;
  return PQ.merge(PQ.merge(queues.head, rest.head), PQ.mergeAll(next));
}
//合成数の遅延リストと別のPriority Queue（オプション）から新しいキューを作る
PQ.enqueue = function(composites, q) {
  return PQ.merge(new PQ(composites), !q ? PQ.emptyQueue : q);
}
// 素数候補のの遅延リストから合成数の遅延リストを作る
PQ.composites1 = function(candidates) {
  return PQ.composites3(candidates.head, candidates.head, candidates);
}
PQ.composites2 = function(primes, candidates) {
  return PQ.composites3(primes, candidates.head, candidates);
}
PQ.composites3 = function(primes, candidate, candidates) {
  return new LL(primes * candidate, function() {
      return PQ.composites2(primes, candidates.next()); 
    }); 
}

上で書いた遅延リストとキューを使って、素数を生成するコードが以下。

前にやった時と同様に（また Haskell の Data.Numbers.Primes と同様に）ホイールを使うが、ホイールを生成するコード自体はここでは省略する。

// 始まりの数とホイールから数列を生成する関数
function spin(prev, wheel) {
  return new LL(prev, function() { return spin3(prev, wheel, wheel); });
}
function spin3(prev, wheel, original) {
  if (wheel.empty) return spin3(prev, original, original);
  var next = prev + wheel.head;
  return new LL(next, function() {
      var nextWheel = LL.hasNext(wheel) ? wheel.next() : LL.emptyLL;
      return spin3(next, nextWheel, original);
    });
}
// JavaScriptの配列と遅延リストを連結する関数
function concat(array, lazyList) {
  return (!array.length)
       ? lazyList
       : new LL(array[0], function() { return concat(array.slice(1), lazyList); });
}
// 候補となる数列と合成数の優先度付きキューから素数の遅延リストを生成する関数
function sieve(ns, pq) {
  if (!pq) return new LL(ns.head, function() {
      return sieve(ns.next(), PQ.enqueue(PQ.composites1(ns)));
    });
  var ms = pq.composites;
  if (ns.head %lt; ms.head) return new LL(ns.head, function() {
      return sieve(ns.next(), PQ.enqueue(PQ.composites1(ns), pq)); 
    });
  var updated = PQ.enqueue(ms.next(), PQ.mergeAll(pq.lowers));
  return (ns.head > ms.head) ? sieve(ns, updated) : sieve(ns.next(), updated);
}
//初期の素数リスト[2,3,5,7]と固定のホイール[4,2,4,2,4,6,2,6]から素数の遅延リストを生成する関数
function primes() {
  var wheel = spin(7, LL.of(4,2,4,2,4,6,2,6));
  return sieve(concat([2,3,5], wheel));
}
//100万番目の素数を標準出力
console.log(primes().nth(999999));

上記のコードを一個のファイルにまとめて実行してみると以下のような結果になった。

$ time node prime-test.js
15485863

real 1m13.130s
user 1m12.862s
sys 0m0.280s

うちのマシンでだいたい1分13秒。

Erlang でやった時とほぼ同じ時間だが、同じロジックの Haskellコードより圧倒的に遅い。コード量に関しても、かなり大差で JavaScript > Erlang > Haskell となる。

遅延評価がデフォルトではない言語で、無理やり遅延リストをやってるわけだから無理もないが、遅延がデフォの Haskellに比べると審美的な観点からもどんどん劣化していく。

とはいえ、JavaScript のウォーミングアップとしては、かなり良かった。

最初、関数をコンストラクタの中で定義していたりして、数時間かけても計算が終わらなかったり、メモリが足りなくなって落ちたりしていたが、いろいろ工夫して1分ちょいで終わるようになった。