|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４６６回 １０進変換の高速化 発行 ２００４年６月２５日（金曜日） 発行数 約２９００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 自らの意思で戦場に赴き、怪我をしたから国を告訴する。 それは新しい商売でしょうか。 それとも私のニュースは古いのでしょうか。 /*========================================================*/ 株日記 /*========================================================*/ 野村のバーチャル株式投資倶楽部 http://www2.nomura.co.jp/vstock/VirtualServlet? （ゲストでログインして Ayusya を探せば成績を参照できます） ★ここ一週間の Ayusya の成績 日曜日 1,005,811円です。（21,491番／96,025人中） 月曜日 1,005,189円です。（21,684番／96,725人中） 火曜日 1,013,536円です。（21,045番／97,376人中） 水曜日 1,012,593円です。（20,800番／98,066人中） 木曜日 1,008,535円です。（21,084番／98,655人中） なんだか、面倒くさくて手を入れてなかったので、大分と 下がってしまいました。 {magclick} /*========================================================*/ 今回のお題 ＜＜ １０進変換の高速化 ＞＞ /*========================================================*/ １０進数変換が、どうも遅すぎるようです。 どうなっているのでしょうか？ 現状は、このような処理になっています。 CString CXInt::toString( void ) { CXInt10 a; CXInt10 b; b.add( 1 ); int n; for( int i = 0; i < SIZE; i++ ) { if( n = m_buff[ i ] ) a.add( b.copy().mul( n ) ); b.mul( 256 ); // ２５６倍 } return a.toString(); } CXInt10& CXInt10::add( CXInt10& b ) { int c = 0; for( int i = 0; i < SIZE10; i++ ) { c = ( int )m_buff[ i ] + ( int )b.m_buff[ i ] + c; m_buff[ i ] = ( UCHAR )( c % 10 ); c /= 10; } return *this; } CXInt10& CXInt10::mul( int b ) { int c = 0; for( int i = 0; i < SIZE10; i++ ) { c = ( int )m_buff[ i ] * b + c; m_buff[ i ] = ( UCHAR )( c % 10 ); c /= 10; } return *this; } CString CXInt10::toString( void ) { char buff[ SIZE10 + 1 ]; // 最大の桁位置を求める for( int i = SIZE10-1; i > 0; i-- ) { if( m_buff[ i ] ) break; } // '0'を足しながらコピー for( int j = 0; i >= 0; i--, j++ ) { buff[ j ] = ( char )m_buff[ i ] + '0'; } buff[ j ] = 0; return CString( buff ); } うーん、とりあえず配列参照をポインタにして見ました。 現状 1.2+3.4=4.6 1.052秒 ポインタ後 1.2+3.4=4.6 0.941秒 うーん、あまり変りありませんね。 アルゴリズムを変えるのは大変なので、そのままにしておきたい ところです。 では、演算全体の実行速度と toFloatString の実行速度を 分けて調べましょう。 1.2+3.4=4.6 0.921s (0.921s) 括弧の中が、純粋に toFloatString にかかる実行速度です。 犯人は明らかですね。 しかし、この関数自体はループを持たない処理なのですが。 この関数内部に、TRACE で、処理速度を打ち出してみました。 int sw_cnt = 1; CStopWatch sw; TRACE( "%d,%s\n", sw_cnt++, sw.str() );＜これを仕掛ける トレース結果 1,0.000 2,0.000 3,0.000 4,0.251 5,0.251 6,0.251 7,0.301 8,0.301 9,0.932 10,0.932 11,0.932 12,0.932 13,0.932 ４の前、７の前、９の前、誰ですか？ ４の前 ret = a.toString(); ７の前 a.mul( CXInt().fromString( "1" + CString( '0', SMALL_BIT_SIZE ) ) ); ９の前 CString st = a.toString(); うーん、やっぱり toString ですか。 得に９の前、６００ミリ秒は、かかりすぎです。 CString CXInt::toString( void ) { UCHAR* pch = m_buff; UCHAR* pe = m_buff + SIZE; CXInt10 a; CXInt10 b; b.add( 1 ); int n; for( ; pch < pe; pch++ ) { if( n = *pch ) a.add( b.copy().mul( n ) ); b.mul( 256 ); // ２５６倍 } return a.toString(); } ループ１回に６００マイクロ秒かかっている、ということです ね。 ６００マイクロって、結構速い気がするのですが、１０２４回も ループが回っちゃうと、駄目ですね。 最大桁数位置を調べておいて、そこまでしか処理しないように しましょう。 int CXInt::GetLength() { int i = SIZE; UCHAR* pch = m_buff + SIZE - 1; for( ; pch > m_buff && *pch == 0; i--, pch-- ); return i; } UCHAR* pe = m_buff + GetLength(); 結果 0.611s おお、ちょっと速くなりましたね。 リリース版ではどうでしょうか。 結果 0.621s ポインタを使っているので、高速化のやりようがないのですね。 残念。 もう少し、早くしたいですね。 {magclick} /*========================================================*/ さいごに /*========================================================*/ 新C言語使いにおくるチョー基本講座 第１２回。 物質の最小単位は、原子です。 生ものの最小単位は、細胞です。 ではパソコンの最小単位はというと、それはトランジスタです。 トランジスタ、というのをご存知ですか？ トランスファーレジスターの略で、 「伝える人」という意味です。 何を伝えるかというと、電気を伝えます。 たとえば、あなたがお部屋の電気をつけたいとき、蛍光灯の 電源を ON にしますよね？ そうすると、電源から蛍光灯に電気が供給されて、光るという ことなのですが、 このスイッチの仕組みを小さくしたものが、トランジスタです。 トランジスタには、３本の足があります。 そのうちの２本が、電源と蛍光灯につながっています。 もう１本は、トランジスタ自身の電源です。 トランジスタに電源が入ると、２本の足の間に電気が通るように なります。 逆に、電源が入っていない状態だと、２本の足の間は絶縁され ます。 そうして蛍光灯をつけたり消したりします。 このトランジスタが１億個ほど集まって、 あなたのパソコンが動いています。 {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は６月２８日（月曜日）に、第４６７回をお送りします。 お題は「１０進変換の高速化２」 もう少し速くしたいです。 お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 パソコンの規模によりますが なんて大歓迎です。 {magclick} /*========================================================*/ /*========================================================*/ 発行者 あゆしゃ ホームページ::あゆしゃの世界 http://ayusya.hp.infoseek.co.jp/ ご意見・ご感想・ご質問メール mailto:ayusya@flamenco.plala.or.jp まぐまぐ::アイディー 0000020674 まぐまぐ::登録と解除 http://www.mag2.com/m/0000020674.htm まぐまぐ::バックナンバー http://jazz.tegami.com/backnumber/frame.cgi?id=0000020674 めーらっくす::アイディー MM3E1AEE285AB4F めーらっくす::登録と解除 http://www.mailux.com/mm_dsp.php?mm_id=MM3E1AEE285AB4F めーらっくす::バックナンバー★最近のものならこちらが便利★ http://www.mailux.com/mm_bno_list.php?mm_id=MM3E1AEE285AB4F |