上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

--/--|スポンサー広告||TOP↑
#2009/03/20 文章が全体的に説明不足、サンプルに本題と関係のない問題があったので、修正。


最近仕事で見かけたコードがちょっとひどかったので、その点をまとめてみる。
なお、下記のものはその遭遇した問題の概要を説明するためのサンプルであって、実際のものとは異なる。

以下に配列に格納された文字列をすべて結合する関数がある。

buf :バッファ
bufsiz :バッファ(buf)のサイズ
src :結合元の文字列の配列
num :結合する文字列の数
戻り値 :バッファを超えた場合1 そうでなければ0

int straraycat(char *buf, size_t bufsiz, const char * const *src, size_t num)
{
size_t buflen;
size_t i;

memset(buf, '\0', bufsiz);

for(i=0; i<num; i++)
{
srclen = strlen(src[i]);
buflen = strlen(buf);
if (buflen + srclen < bufsiz - 1)
{
strncat(buf, src[i], srclen);
}
else
{
return 1;
}
}
return 0;
}

ここでは問題を2つ挙げる。軽くソースを見てみよう。

まず、最初にsrclenを得ている。これは特に問題はない。
次にbufの文字列長を確認している。
ハイここでまず一つ目の問題点。
Cの場合文字列は特別な型ではなく、終端としてヌル文字を含むcharの配列に過ぎない。
よって、strlenはポインタの指す先頭からヌル文字になるまで一文字ずつチェックする。
これを繰り返すと大変効率が悪い。そして、求めるべき長さは、バッファはクリア済みであるために、実は自分が書き込んだバイト数そのものだ。
よって単にstrlen(src[i])の結果を合算しておけばよい。

次に、strncatしている。これが2つめの誤りだ。先に述べたとおり文字列終端を文字列の先頭から探すのは大変だ。
strncat(buf, src, num);

strncpy(buf + strlen(buf), src, num)
と、関数の呼び出しに関わるコストを除けば計算量が変わらない。
そして、問題のコードではすでに文字列の終端位置をstrlenで得ているのだから、
strncpy(buf + buflen, src, srclen)
でいいだろう。
さらに、上記の呼び出しでsrclenは対象文字列の長さそのものなので、
memcpy(buf + buflen, src, srclen);
とすべきだ。こうするとstrncpyでやっている終端文字のチェックが不要になるので高速化が期待できる。

そして、このように書き換えると出力先のヌル文字終端を一度も見ないようになるので、
冒頭のmemsetも不要になる。代わりに処理の最後にヌル文字を入れる。

これらを適用すると、


int straraycat(char *buf, size_t bufsiz, const char * const *src, size_t num)
{
size_t buflen = 0;
size_t i;

for(i=0; i<num; i++)
{
srclen = strlen(src[i]);
if (srclen + buflen < bufsiz - 1)
{
memcpy(buf + buflen, src[i], srclen);
buflen += srclen;
}
else
{
return 1;
}
}
buf[buflen] = '\0';
return 0;
}

となる。
関数の呼び出し回数と、その関数自体の期待されるコストが減少したのがわかるだろうか。
元のソースではこのような修正により、プログラム全体の処理時間が3割ほど減少した。

文字列処理用の標準関数を正しく使い分けよう。

なお、本来であれば戻り値はsize_t型で書き込みに成功したバイト数とするほうがより適切だろう。
そうすれば、この上位の結合関数を容易に書ける。しかし、今回はインターフェースが変わるものは認められないためやめた。(とはいっても、書き込み先の完全な0クリアはやめているのだが。)
また、Cとしては、ポインタへの直接的な加算でさらに高速化できるかもしれないが、この辺はスタイルが絡んでくるので、解説はしない。

これらは配列の長さを直接もたない、Cらしい問題といえる。そのほかの言語に見られる、大きさを持つ配列・文字列は、自身の長さを整数値として持っているので、その長さをいちいち計算することはない。
逆に性能上の問題からCを使わなければならないのであれば、このくらいのことは把握しておく必要がある。最初に書いたようなコードを書いてしまうようなら、C++ C# Java D そしてその他多くの文字列型を持つ言語を使う方がよっぽど処理が速くなるだろう。

Cが速いというのは、注意深いコーディングの末に得られるものであるという点を忘れてはならない。
スポンサーサイト

03/13|プログラムコメント(3)トラックバック(0)TOP↑
この記事にコメント
Cの初期値は保証されず
つっこみどころは多々あるけれど
とりあえず
buflenの初期化....
From: たまたま通った * 2009/03/19 11:20 * URL * [Edit] *  top↑
あー読み返したら、冒頭の変数の説明が謎の書式だし、そもそも説明なしの謎の変数があるし。確かにひどい。
後で適当に書き換えてみます。
とりあえず関数化しておくか。

ちなみに、高速化は計測して確認してます。この断片じゃなくて元のソースとその修正後のソースですが。
From: G.U.Nex * 2009/03/20 02:14 * URL * [Edit] *  top↑
管理人のみ閲覧できます
このコメントは管理人のみ閲覧できます
From:  * 2009/03/20 23:34 *  * [Edit] *  top↑
名前:
コメントタイトル:
メールアドレス:
URL:
コメント:

パスワード:
管理人だけに表示:
管理者にだけ表示を許可
この記事にトラックバック
プロフィール

G.U.Nex

Author:G.U.Nex
職業:プログラマ
趣味:ゲーム(PC、コンシューマ)、ネットサーフィン、ニコニコ動画視聴、プログラミング、鉄道全般
PHP, C, C++, VB(系), Java, JavaScriptを使える。
最近はRubyにはまってる。

最近の記事
最近のコメント
最近のトラックバック
月別アーカイブ
カテゴリー
ブロとも申請フォーム
ブログ内検索
RSSフィード
リンク
フリーエリア
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。