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() の定義は
というわけで, s.end() の呼び出しは実質 s.begin()+s.size() と一緒で, それぞれも 当たり前だが, 構造体のメンバを参照しているだけ。 *3 最適化をかけると, こうした1〜2行の関数はインライン展開されるので, ほとんど オーバーヘッドがなくなるのだと思う。
これにも関係しますが, 高林君 からもらったコメントで, 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 のバージョンを変えて時間を測ってみました。
最適化しないと++itの方が速いですが, 最適化をかけるとほぼ全く同じ。 const_iteratorと普通のiteratorはこの場合は, どちらの場合も全く同じ速さになる ようです。
記述 最適化なし 最適化 -O2 it++ 1.0543 0.05302 ++it 0.8052 0.05297 const_iterator 1.0577 0.05292