« 2008年2月 | トップページ | 2008年12月 »

2008/08/23

10万までの素数をJavaScriptで求める



Pavilion Desk 秋冬モデル TFTモニタセットが5万円台から!

先ほど、「JavaScriptで素数を計算する」を書きましたが、5万までぐらいの素数であれば計算できても、それ以上になるとIE7の場合、「このスクリプトの実行を中止しますか? このページのスクリプトが、Internet Explorerの実行速度を遅くしています。スクリプトを実行し続けると、コンピュータが反応しなくなる可能性があります。」という警告メッセージが表示されてしまう問題について触れました。

詳しく調べてみると、このメモリー不足に起因する?警告メッセージは、document.writeの部分をコメントにすると、表示されなくなることが分かりました。ループ処理の中で、素数が見つかり次第、その都度document.writeしているのが問題だったようです。そこで、一旦document.writeする文字列を配列に入れ、後でjoinしてまとめてdocument.writeするようにしたところ、警告メッセージが表示されることなく、IE7でも12万ぐらいまでの素数を求めることができるようになりました。2倍以上、性能がよくなったわけです。IE6+XP SP2の環境でも12万までの素数を、警告メッセージが表示されることなく求められるようになりました。

ex. 素数を求めるJavaScript3(改良版)
設置例は下記です。

●10万までの素数をJavaScriptで求める
http://shimax.cocolog-nifty.com/test/sosuu_utf8.html

なお、Mac版IEではarray.pushが使えないため、その部分も書き直しました。ただ、array.pushを使わないほうが、他のブラウザでも約0.1秒ほど速くなりました。調べてみると、ずばりの記述がありました。

(参照)●array.push(obj) より array[array.length] = obj の方が高速である - IT戦記
http://d.hatena.ne.jp/amachang/20060309/1141900856



Pavilion Notebook PC dv2805 夏モデル 人気のモバイルサイズが5万円台!

| | コメント (0) | トラックバック (0)

JavaScriptで素数を計算する



【格安パソコンなら!ソーテックオンラインショップ!】

実に半年振りに記事を書きます。3月の頭にある案件が入って、それにかかりっきりだったため、記事を書く時間を取れなかったのが第一の理由です。この期間、アクセス数は半分以下に減ってしまった。とほほ。

さて、何を書こうかと考えましたが、かなり前に、書こうかなと思って調べていた「素数をJavaScriptで求める」方法について考えてみたいと思います。巷では、「3の倍数と、3のつく数」というのが流行っているようですが、もう少し難しくして、「素数の時だけ馬鹿になる」というのがあったら面白いかもしれません。

素数をJavaScriptで求める方法として最初に考えたのが、下記のようなコードです。

ex. 素数を求めるJavaScript
ところが、この方法はあまり効果的ではありません。その証拠に、上記の例では10,000までに存在する素数を調べていますが、この範囲を広げると、例えばInternet Explorer 7(Vista Basic上で)では、13,281以上に設定しますと、



のような警告ダイアログが表示されました。「いいえ」を押せば、最終的にはJavaScriptで求められるのですが、気持ちのいいものではありません。

そこで、次のように考えました。97という数字が素数でないとすれば、因数分解できるはずですから、√97を10と考えれば、10までの数の間に必ず約数が現れるはずです。もし現れなければ、それは素数です。

ex. 素数を求めるJavaScript2
このプログラムで試してみると、50,000までの素数を調べるようにしても、IE7で上記の「このスクリプトの実行を中止しますか? このページのスクリプトが、Internet Explorerの実行速度を遅くしています。スクリプトを実行し続けると、コンピュータが反応しなくなる可能性があります。」という警告メッセージは出なくなりました。(ただし、53,281までに範囲を広げると警告メッセージが表示されました。Windows XP+IE6 SP2の場合は47,281以上で警告メッセージが表示されました。この違いがIEのバージョンの違いによるものか、OSの違いによるものなのか、それともパソコンのスペックに影響されているのかはまだ調べ切れていません。ただ、日によって計測結果が微妙に異なりますし、パソコンのメモリと大きく関係してそうです。)

しかし、Googleで「素数 JavaScript」を調べてみると、他の方のJavaScriptだともっと広い範囲のJavaScriptを問題なく調べられています。一例を紹介させていただきますと、

● 素数表作成JavaScript
http://hp.vector.co.jp/authors/VA004808/primescr.html

では、Vista + IE7で、75,000までの素数を調べても、上記の警告メッセージは表示されませんでした(76,564以上で警告メッセージが表示されました)。むむむ。悔しいです。

さらに調べてみると、素数をリストアップする速度は無茶苦茶遅いものの、「このスクリプトの実行を中止しますか? ・・・」の警告メッセージがIE7でも一切表示されないJavaScriptもありました。まだまだ研究しなければならないようです。

ちなみに、方法2を使って50,000までの素数を調べるようにした場合、各種ブラウザで以下のような計測結果になりました(時間はJavaScriptで計算。)。

ブラウザ計測時間
Firefox 3.0.1(Vista)1.1秒から1.3秒(平均1.14秒)
Opera 9.52(Vista)1.2秒から1.3秒(平均1.28秒)
Safari(Tiger)1.7秒(平均1.7秒)
IE7(Vista)1.8秒から1.9秒(平均1.82秒)
IE6 SP2(XP)50,000までの素数を調べようとすると、「このスクリプトの実行を中止しますか? 」の警告メッセージが表示され、正確に計測することが不可能。42,000までの素数を調べるのには、平均2.3秒という結果でした。
IE 5.23(Tiger)3.8秒から3.9秒(平均3.82秒)

(Mac版IEではarray.pushが使えないので、一部コードを書き換えてテストしました。array.pushを使わないほうが、他のブラウザでも、概ね0.1秒ほど速くなりました。
Opera 9.27(Vista)3.9秒から4.1秒(平均4.04秒)
Firefox 2.0.0.16
(Vista)
7.3秒から7.5秒(平均7.36秒)
Netscape 7.1(XP)11.2秒から11.4秒(平均11.26秒)


Firefox及びOperaともバージョンアップによって、やはりJavaScriptの実行速度が上がっているようです。

| | コメント (0) | トラックバック (0)

« 2008年2月 | トップページ | 2008年12月 »