過去ログ
No．１１５９ 文字列の連結を高速化する
[戻る] [ホームページ]No.15049 |
文字列の連結を高速化する 投稿者---だん(2004/06/29 17:54:55) |
||
だんと申します。 早速質問させていただきます。 CString a; CString b; CString c; a = "xxx..."; (1MByteくらいの文字列) b = "yyy..."; (1MByteくらいの文字列) c = a + b; のような処理をたくさん書いているのですが 結構時間がかかってしまいます。 何か速い方法ってあるんでしょうか？ |
|||
| No.15052 |
Re:文字列の連結を高速化する 投稿者---あかま(2004/06/29 19:00:28) |
||
>何か速い方法ってあるんでしょうか？ 1Mというと最低100万回の代入があるので結構かかってしまいそうですね。 Cstringの実装がどうなっているか分かりませんが、メモリ領域が足りなくなったらreallocのような事をしているかもしれません。 Cには予めどうでもいいデータを2M分入れておいてreallocを回避するとかどうでしょうか。 もちろん処理系依存なのでうまくいくかわかりませんが。 プログラムが変わってしまいますが、一番いいのは文字列の連結をしないことだと思います。 例えば出力するだけなら、aとbを順番に出力するだけです。 cをポインタにしておいて、aとbの順番を記録しておくなどでうまい対策はできないでしょうか？ |
|||
| No.15053 |
Re:文字列の連結を高速化する 投稿者---だん(2004/06/29 19:13:55) |
||
回答ありがとうございます。 CStringで割付先アドレスを調べてみたのですが、 連結する度に変わっていました。 よって内部的にrealloc的なことがされていると思います。 |
|||
| No.15054 |
Re:文字列の連結を高速化する 投稿者---ぽこ(2004/06/29 19:45:10) |
||
>回答ありがとうございます。 >CStringで割付先アドレスを調べてみたのですが、 >連結する度に変わっていました。 >よって内部的にrealloc的なことがされていると思います。 c=a+bはまず、"a+b"によって中間のインスタンスが生成されます。 この時に2M文字のコピー(とメモリ確保)が発生します。 次に"c=中間のインスタンス"でさらに2M文字のコピー(とメモリ確保)が発生します。 もし、a,bの内容が壊れてもいいのであれば、a+=bとすることで少しはましになると思います。 #内容的にはCじゃないですね。。 |
|||
| No.15055 |
Re:文字列の連結を高速化する 投稿者---あかま(2004/06/29 19:57:41) |
||
MSDNリファレンスの「CString オブジェクトの内容の直接変更」 ってところに メンバ関数 GetBuffer および ReleaseBuffer は CString オブジェクトの内部文字バッファを直接操作して変更できます。 これらの関数は次の手順で使用します。 CString オブジェクトに対して GetBuffer を呼び出し、必要な長さのバッファを指定します。 GetBuffer が返すポインタを使用して CString オブジェクトに直接文字を書き込みます。 CString オブジェクトに対して ReleaseBuffer を呼び出し、CString の内部状態情報 (文字バッファの長さなど) を更新します。 CString オブジェクトの内容を直接操作した後は、必ず ReleaseBuffer を呼び出してから、その他の CString メンバ関数による操作を続けます。 なんてのがありましたが、 >c=a+bはまず、"a+b"によって中間のインスタンスが生成されます。 だとあまり意味ないかも。 GetBufferの後に c = a; c += b; で、中間インスタンスとやらを発生させないようにはできないかな？ |
|||
| No.15069 |
Re:文字列の連結を高速化する 投稿者---ＲＥＥ(2004/06/30 10:17:29) |
||
>c=a+bはまず、"a+b"によって中間のインスタンスが生成されます。 >この時に2M文字のコピー(とメモリ確保)が発生します。 ここはそうなりますが、 >次に"c=中間のインスタンス"でさらに2M文字のコピー(とメモリ確保)が発生します。 これは起きないはずです。 |
|||
| No.15072 |
Re:文字列の連結を高速化する 投稿者---ぽこ(2004/06/30 11:30:57) |
||
>>次に"c=中間のインスタンス"でさらに2M文字のコピー(とメモリ確保)が発生します。 > >これは起きないはずです。 ご指摘ありがとうございます。 VS.net2002のCStringT::operator=のリファレンスの解説に "コピー先の文字列 (演算子の左側の文字列) が、 新しいデータを格納するために十分な大きさである場合は、 新しいメモリ領域は割り当てられません。" とありましたので、代入時にもコピーが発生すると思っていました。 お手数ですがCStringT::operator=が実行される時の振る舞いを教えていただけないでしょうか? |
|||
| No.15076 |
Re:文字列の連結を高速化する 投稿者---ＲＥＥ(2004/06/30 13:25:11) |
||
>>>次に"c=中間のインスタンス"でさらに2M文字のコピー(とメモリ確保)が発生します。 >> >>これは起きないはずです。 > >ご指摘ありがとうございます。 >VS.net2002のCStringT::operator=のリファレンスの解説に > >"コピー先の文字列 (演算子の左側の文字列) が、 >新しいデータを格納するために十分な大きさである場合は、 >新しいメモリ領域は割り当てられません。" > >とありましたので、代入時にもコピーが発生すると思っていました。 >お手数ですがCStringT::operator=が実行される時の振る舞いを教えていただけないでしょうか? 参照カウンタを使用して、コピーを効率化しています。 結果的には、コピー先がその中間のインスタンスと同じメモリ領域を指します。 MSDNの下記のページの「CString への参照のカウント」をご覧ください。 http://www.microsoft.com/japan/msdn/library/default.asp?url=/japan/msdn/library/ja/vccore/html/_core_managing_string_data.asp |
|||
| No.15078 |
Re:文字列の連結を高速化する 投稿者---ぽこ(2004/06/30 14:56:25) |
||
>MSDNの下記のページの「CString への参照のカウント」をご覧ください。 > >http://www.microsoft.com/japan/msdn/library/default.asp?url=/japan/msdn/library/ja/vccore/html/_core_managing_string_data.asp REEさんが提示されたURLおよび、 CSimpleStringT& CSimpleStringT::operator=( const CSimpleStringT& strSrc ){} にて以下の点を確認しました。 ・バッファがロックされていればコピーする。 ・バッファがロックされていなければ参照カウンタを1増やす。 参照カウンタを増加するか否かの条件は、上記以外に内部でいろいろ判定しているみたいです。 とりあえず、文字列(を管理しているインスタンス)の無駄なコピーを防ぐ機構を確認できました。 ありがとうございました。 だんさん： 本スレッドの主題から外れてしまい、申し訳ありません。 |
|||
| No.15077 |
Re:文字列の連結を高速化する 投稿者---monkey(2004/06/30 14:10:15) |
||
>結構時間がかかってしまいます。 次のようなコードで試してみましたが，１回限りならば0.02秒未満で，ストレスを感じるほどのものではありませんでした． （VC++.NET2002, CPU:Pentium4:3GHz，RAM:1.5GB，かなりリッチな環境ではありますが^^;） unsigned SIZE = 1048576; // 1MB
CString a( 'x', SIZE );
CString b( 'y', SIZE );
CString c;
c = a + b;
どの程度の速さが求められているのか分かりませんが，連結・代入操作自体ではそれほど大きな改善は見込まれないでしょうから，全体のアルゴリズムの工夫により，メモリの確保や文字列操作の回数を減らすなどで対処することをお考えになった方が良さそうに思います． |
|||