「JavaScriptで整数問題を記述するライブラリ」を独立させてちょっと改良


ちょっと改良。

JavaScriptで整数問題を記述するAPIを改良:素数未満の素数の個数が素数であるような場合を求めよ - ソフトウェア勉強ログとサンプルコード
http://source-code-student.hatenablog.jp/entry/20150126/p1

JSに名前をつけて切り出して,「計算結果のキャッシュ」というデータ構造を導入。

また同じく「素数未満の素数の個数が素数」であるような数を求めている。 ====

<script src="./IntegerProblem.js"></script>


<input type="button" value="計算開始" onclick="calc()"><br>

<textarea id="d" cols="80" rows="20"></textarea>


<script>

function calc(){
	clear_log();

	// 素数を見つけよ
	find_all_primes_that( function( N ){ return (
		
		// この条件を満たすものを
		
		// N未満の素数の個数(素数計数関数)の値が
		prime_counting_function( N - 1 )
		
			// 素数であること
			.isPrime()
		
	);})
	
	// 結果を表示せよ
	.display()
	;

}



// 結果表示用

function log( s ){
	$("d").value = s + "\n" + $("d").value;
}

function clear_log( s ){
	$("d").value = "";
}


function $( dom_id ){
	return document.getElementById( dom_id );
}


</script>

IntegerProblem.js

/*
	
	IntegerProblem.js
	
	JavaScriptで整数問題を記述するためのライブラリ
	
	@author id:SourceCode-Student
	ver0.1, MIT License

*/


// --------- 整数問題の記述 --------- 


// ある素数を見つけよ(満たすべき条件は関数で渡す)
function find_all_primes_that( func ){
	return (
		new IntArr()
			.generate_primes( 1, TESTING_LIMIT )
			.filter( func )
	);
}


// 探索範囲の上限
var TESTING_LIMIT = 10000


// --------- 整数の探索ライブラリ --------- 


// 整数の配列のラッパ
var IntArr = function(){};
IntArr.prototype = {
	
	// 配列を内部に保持
	_arr : [],
	
	item : function( i ){
		return this._arr[ i ];
	},

	// ステップ刻みで配列を生成
	generate_by_step : function( i_start, i_end, i_step ){
		this._arr = [];
		for( var i = i_start; i <= i_end; i += i_step ){
			this._arr.push( i );
		}
		return this;
	},
	
	// ある範囲内で素数列を生成
	generate_primes : function( i_from, i_to ){
		var new_arr = this.generate_by_step( i_from, i_to, 1 )
			.filter(function(n){
				return n.isPrime();
			})
			//.display()
		;
		
		//log("素数列の生成が完了");
		return new_arr;
	},
	
	// 条件で絞込み
	filter : function( func ){
		this._arr = this._arr.filter( func );
		return this;
	},
	
	// 保持している配列の内容を表示
	display : function(){
		var tmp = [];
		for( var i = 0; i < this._arr.length; i++ ){
			tmp.push( /* i + ":" + */ this.item( i ) );
		}
		log( "[ " + tmp.join(", ") + " ]" );
		
		return this;
	}

};


// --------- 素数の計算ライブラリ --------- 


// キャッシュ回答機能付の計算結果格納庫
var CachedCalcResults = function(params){
	this.calc = params.calc;
	this._arr = [];
};
CachedCalcResults.prototype = {

	_arr : null,
	
	calc : null,
	
	// キャッシュ利用可で判定せよ
	answer : function( num ){
		var ans;
		
		if(
			( this._arr.length >= num )
			&&
			( this._arr[ num - 1 ] != null )
		){
			// 計算済みの問い合わせだったとき
			//log("cache hit : " + num);
		
			// キャッシュから回答
			ans = this._arr[ num - 1 ];
		}else
		if( this._arr.length < num ){
			// 保持している配列の範囲外の問い合わせがあったとき
			//log("too short : " + num);
			
			for( var i = this._arr.length; i < num - 1; i ++ ){
				this._arr.push( null ); // まだ計算しないでおく
			}
			
			var b = this.calc( num );
			this._arr.push( b );
			ans = b;
		}else
		//if( this._arr[ num - 1 ] == null )
		{
			// 保持配列の範囲内だが,未計算だったとき
			//log("delayed : " + num);
			
			var b = this.calc( num );
			this._arr[ num - 1 ] = b;
			ans = b;
		}
		
		//log("回答:" + ans);
		return ans;
	}
};


// 素数判定
Number.prototype.isPrime = function(){
	// できるだけキャッシュから回答する
	return primeCache.answer( this );
};

// 素数判定結果のキャッシュ
var primeCache = new CachedCalcResults({
	calc : function( num ){
		if( num < 2 ) return false;

		var m = Math.floor( num / 2 );
		for( var i = 2; i <= m; i ++ ){
			if( num % i == 0 ){
				return false;
			}
		}
		return true;
	}
});


// 素数計数関数
function prime_counting_function( n ){
	// ダブリ処理をなくすためにキャッシュから回答
	return primeCountingCache.answer( n );
}

// 素数計数関数の計算結果のキャッシュ
var primeCountingCache = new CachedCalcResults({
	calc : function( num ){
		var ans;
		if( num <= 1 ){
			ans = 0;
		}else{
			ans = this.answer( num - 1 )
				+ ( num.isPrime() ? 1 : 0 )
			;
		}
		//log("π:" + ans);
		
		return ans;
	}
});



// --------- 配列の拡張 --------- 


// 配列中で条件にマッチするものだけを残す
Array.prototype.filter = function( func ){
	var new_arr = [];
	this.each(function(){
		if( func( this ) ){
			new_arr.push( this );
		}
	});
	return new_arr;
};

// イテレータ
Array.prototype.each = function( func ){
	for( var i = 0; i < this.length; i ++ ){
		func.call( this[ i ], i );
	}
};

はまった点:

  • prototypeの中身を最初から[]にしていて,別のオブジェクトなのに配列の内容が共有されていて,なぜだ・・・と悩んだ。そして単純ミスでアチャーとなった。このミスはよくはまる。


今後の改善:

  • 「重いループを軽く動かすライブラリ」がとりあえず形になっているので,それをうまく組み合わせて,巨大な範囲の探索をブラウザ上で実行できるようにしたい。
  • たぶん,IntArrオブジェクトは不要だろう。HeavyArrayの中にマージできると思う。