最近のキーワード

2006年06月19日

上限を決めずに素数を生成(JavaScript版)

JavaScriptでも書いてみた。(コードは冗長になるが高速にしたものも追加) 「キミならどう書く 2.0 - ROUND 1 -」のJavaScript版。メモリと時間が許す限りどこまででも求めます。
?? 個目の素数は ?? です。」
100までの素数:[]

高速化したもの:
?? 個目の素数は ?? です。」
100までの素数: []

ソース:

// もとのバージョン
function Prime(){
  this.hash = [];
  this.n = 0;
  this.succ = function(){
    if (this.n == 0) {
      this.n = 1;
      return 2;
    };
    var n = this.n;
    var s = null;
    while (true) {
      n ++;
      if (s = this.hash[n]) {
        s();
        delete this.hash[n];
      }
      n ++;
      if (s = this.hash[n]) {
        s();
        delete this.hash[n];
      }
      else {
        var i = n;
        var j = n;
        var h = this.hash;
        var f = function(){
          var k = i + j;
          var g = h[k];
          if (g) {
            g();
          }
          h[k] = f;
          j += n;
        }
        f();
        this.n = n;
        return n;
      }
    }
  }
}

// 高速化したもの (コードが冗長になるが仕方ない)
function Prime2(){
  this.h = new Object();
  this.n = 0;
  this.next = function(){
    if (this.n == 0) {
      this.n = 1;
      return 2;
    };
    var n = this.n;
    var b = null;
    var h = this.h;
    while (true) {
      n ++;
      if (b = h[n]) {
	var m = n + b
        while(h[m]) {
          m += b
        }
        h[m] = b;
        delete h[n];
      }
      n ++;
      if (b = h[n]) {
	var m = n + b
        while(h[m]) {
          m += b
        }
        h[m] = b;
        delete h[n];
      }
      else {
	var m = n + n;
        while (h[m]) {
          m += n;
        }
        h[m] = n;
        this.n = n;
        return n;
      }
    }
  }
}
追記いろいろ:
  • 履歴は連想配列の値をとってくればOK。
  • Ruby版では、1.9のmathn.rbより圧倒的に高速。
  • FirefoxよりIEの方が速いみたい。
【関連する記事】
posted by ttate at 02:23| 🌁| Comment(0) | TrackBack(0) | JavaScript | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。