ちょっと改良。
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の中にマージできると思う。