STLで文字列やベクトルを走査する時, 一番素直には, イテレータを使って
string::iterator it;
for (it = s.begin(); it != s.end(); it++)
; /* do something */
のように書けばいいが, これは終了条件で s.end() を毎回呼び出すので遅くなり
そうに見える。これを回避するためには, 少し工夫して
string::iterator it, end;
for (it = s.begin(), end = s.end(); it != end; it++)
; /* do something */
とすればいい.. のだが, 煩雑になるので, 速度が上と一体どのくらい違うのかが
気になっていた。
いっそのこと速度を気にするのであれば, イテレータを使うのをやめてしまって
const char *cp, *end;
for (cp = s.data(), end = cp + s.size(); cp < end; cp++)
; /* do something */
とする手もあるようだ。
下に行くほど速くなると考えられるが, 記述量は増える。
論よりrun, ということで,
*1
テストプログラムを書いて時間を測ってみた。
テストプログラムは以下のような感じで, for文の周辺だけが異なる。
自然言語処理の文字列は平均すると高々40文字くらいかな, ということで,
1000000回の繰り返しで時間を測ってみた。
#include <string>
#include <cstdio>
#include <cstdlib>
using namespace std;
int
main (int argc, char *argv[])
{
string s = "0123456789012345678901234567890123456789"; /* 40 chars */
string::iterator it;
int i, n, z = 0;
n = atoi(argv[1]);
for (i = 0; i < n; i++)
{
for (it = s.begin(); it != s.end(); it++)
z += *it;
}
printf("z = %d\n", z); /* -O2 時の最適化を防ぐために必要 */
}
結果は以下。
Type | 最適化なし | 最適化 -O2 |
---|
it != s.end() | 1.417s | 0.097s |
it != end | 1.044s | 0.052s |
const char *cp | 0.144s | 0.050s |
vanilla C | 0.141s | 0.049s |
面白いのは, 最適化のない場合は3番目のchar *を使った書き方が
明らかに速いが, -O2を使うと, 速度は普通にイテレータを使った場合とほとんど同じ
になる, ということ。(!)
イテレータは通常ポインタを使って実装されているから, 実際はほとんど同じになる
のかもしれない。なお, -O3, -O4で最適化した場合も, 速度は-O2とほとんど変わらな
かった。
また, イテレータを使う場合も, 毎回 s.end() と比較してもそれほど大きく遅くなる
ということはなく
*2
, せいぜい1.5〜2倍程度の違いになった。
ちなみに, vector<int>の結果は以下。vector<int>(10000) の全要素を10000回走査
するコードで比較してみた。
Type | 最適化なし | 最適化 -O2 |
---|
it != v.end() | 3.332s | 0.094s |
it != end | 2.488s | 0.094s |
const int *ip | 0.307s | 0.095s |
vanilla C | 0.357s | 0.092s |
この場合, 驚くべきことに it != v.end() と it != end の間に全く差がなく(!),
const int * を使ってアクセスするとごくわずかに遅くなりさえする。
文字列の場合もそうだが, イテレータで最適化した時のアクセス速度は, Cで
ネイティブに書いた時とほとんど同じのようだ。
ということで, 結論から言うと, 終端を表す end イテレータを定義して使えば充分で,
普通に it != end() としてもそれほど速度は落ちないか, 場合によっては全く同じ
になる, ということのようだ。
速度は測定してみないとわからないので, この実験は個人的にためになった。
追記
はてブに, 理由についてのコメントが
上がっている
ようです。
これにも関係しますが,
高林君
からもらったコメントで, STLの実装はほとんどヘッダファイルの中に書いてある
ということで, 手元の環境では /usr/include/c++/4.1.1/ にある bits/basic_string.h
を見てみました。end() の定義は
iterator
end()
{
_M_leak();
return iterator(_M_data() + this->size());
}
で, 単純にデータ先頭へのポインタ+長さを返す関数。ここで _M_leak() は
(const_iterator はこの _M_leak() の呼び出しがないことだけが違う),
void
_M_leak() // for use in begin() & non-const op[]
{
if (!_M_rep()->_M_is_leaked())
_M_leak_hard();
}
という定義。_M_is_leaked() は
bool
_M_is_leaked() const
{ return this->_M_refcount < 0; }
で, レファレンスカウントが負になっていないかをチェックしているだけで,
通常問題ないと思われる。
というわけで, s.end() の呼び出しは実質 s.begin()+s.size() と一緒で, それぞれも
当たり前だが, 構造体のメンバを参照しているだけ。
*3
最適化をかけると, こうした1〜2行の関数はインライン展開されるので, ほとんど
オーバーヘッドがなくなるのだと思う。
ちなみに, 高林君が (1) it++ より ++it の方が速い (2) const_iteratorの方が速い
かも, と教えてくれたので, it != end のバージョンを変えて時間を測ってみました。
記述 | 最適化なし | 最適化 -O2 |
---|
it++ | 1.0543 | 0.05302 |
++it | 0.8052 | 0.05297 |
const_iterator | 1.0577 | 0.05292 |
最適化しないと++itの方が速いですが, 最適化をかけるとほぼ全く同じ。
const_iteratorと普通のiteratorはこの場合は, どちらの場合も全く同じ速さになる
ようです。
*1: 今どきの人はBASICを知らないから, こういうのはピンと来ないんだろうか.. (^^;)
*2: この場合文字列は何万文字になったりすることはないため, これは場合による可能性
がある。下のvectorの場合参照。
*3: size() の定義は, return _M_rep()->_M_length; というもの。