mots quotidiens. | |
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp | by hns, version 2.10-pl1. |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
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 */とする手もあるようだ。 下に行くほど速くなると考えられるが, 記述量は増える。
#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() としてもそれほど速度は落ちないか, 場合によっては全く同じ
になる, ということのようだ。
速度は測定してみないとわからないので, この実験は個人的にためになった。
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; }で, レファレンスカウントが負になっていないかをチェックしているだけで, 通常問題ないと思われる。
ちなみに, 高林君が (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
% ./dna < /etc/fstab TTGAACGCCCGCGCTCTTGAGCCCTTGCATGCTCACGATCTTGCCCTCAATCAATAAATATTGAATACTTGCTCG\ CGCCCTTGCATGCAATAAATAAAGATTGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAA\ GAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGACCGCAGTCACTCTATAAAGAAAGAAAGAA\ AGAACGCCCGCGCGCCAGCCCTCATGCACTCTATCAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGACATAAAGA\ CATAGGAAATACCAACGAACCCACATACCTTATTGAGAGCTTGCTTGCACTCAAGAAAGAAAGAAAGAAAGAAAG\ AAAGAAAGAAAGAAAGAAAGAAAGAAAGATTGAGAGCTTGCTTGCACTCAAGAAAGAAAGAAAGAAAGAAAGAAA\ GAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGACCGCAGTCACTCTATAAAGAAAGAA (以下略)は以下のように書けるという話を前に聞いて, 面白いなと思っていた。
#include <stdio.h> int main() { char*s="ACGT",c,i; while((c=getchar())!=EOF) for(i=0;i<4;i++,c>>=2) printf("%c",s[c&3]); }1バイトは8ビットで"ACGT" *1 は2bitの情報量なので, これは単純に1バイトを順番に2ビットずつ ずらしながらDNAにエンコードしている。
% cat and.c #include <stdio.h> main(){ int c,i,d[256]; d['A']=0; d['C']=1; d['G']=2; d['T']=3; while ((c=getchar())!=EOF){ c=d[c]; for(i=1;i<4;i++) c |= d[getchar()] << i*2; putchar(c); } } % cat /tmp/dna AGGCTTGCTCTCAAGACAGCGATCCCGCAAGACGTCTTGCCCTCAAGATCGCCCGCGTGCACTCATGCCCGCCTGCCCGCGTGCGGAA % ./and < /tmp/dna how are you gentlemenただ, これはいかにもd['A']=0; d['C']=1; d['G']=2; d['T']=3;の部分が冗長。
これは'ACGT'(文字コード65,67,71,84)をそれぞれ0,1,2,3にマップしているだけ なので, 2進表現を考えると, 朝少し計算して, (c*3>>3)&3 で書けることに気づいた。 こうすると, 上のプログラムは Short coding的なテクニックを使って短くして, 2行で書ける。
main(){char c,i;while(c=getchar(),~c){c=(c*3>>3)&3; for(i=1;i<4;i++)c|=((getchar()*3>>3)&3)<<i*2;putchar(c);}}泉谷君が, さらにゴルフして1行にしてくれた。
i,b,c;main(){while(c=getchar(i/4?putchar(b),b=i=0:0),~c)b|=(c*3>>3&3)<<i++*2;}
-1は二進表現で111..11なので, ~cにすると-1のときだけ全部0(false)になる模様。
なるほど。
なお, 上のようなハッシュを計算するさらに一般的な超絶コードが,
"ビット演算 0x02"スレ
の
762-763
にあります。凄すぎる..。
"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];はslashdot.jpでも8月頭に 話題になっていたらしい。
今, 問題は512→9, 256→8, 16→4 のような数を返すこと。
実は, 必ずしも上の通りに値を返さなくても, 入力nに対してそれぞれ違う整数を
マップできれば, "...." の文字列の形をしたテーブルの対応する添字をアクセスすれば
所望の結果が得られる。
*2
よって上のコードの中心は "\1\2\3\010\6\4\011__\7\5" ではなくて, 掛けてある
0x5300000 (や0xCA030FF) をどうやって求めたか, ということ。
まずM系列とは, 一番簡単には, p個のビット列xを初期値として,
x[n] = x[n-p] ^ x[n-q] (p>qとする) の形でXORを取ることで生成される
1111000010011010111
のようなビット数列のことらしい。
[説明]
これをpビット毎に切り出すと, 周期2^p-1ですべて違ったビット列 1..2^p が現れる。
(自然言語処理では全く使わないので, 僕は聞いたことがなかった。)
ここで, 入力nは常に512や32のように 2^a の形をしているので,
n*■(謎の定数)は■をaビット左にシフトするという意味。
これが各a=1,2,..,9について常に異なった値になる→■にはM系列を使えばいい!
ということのようだ。
実際にはM系列は一意ではない&&問題は1<=a<=9を対象にしているため, a>=10ビット
以上シフトすることはないため, うまくM系列を選ぶと引くテーブル(文字列)を短く
することができる, というのが最後のコツの模様。
というわけでまとめると, 今回は与えられたキー集合に対する完全ハッシュ関数を 作ればよく(順番はテーブルを引くことで吸収する), 一般にはgperfのようなものを 使えばよいが, 今回入力nは常に2の巾乗→nを掛けることはビットシフト→M系列を ビットシフトすれば, 完全ハッシュが得られる, という流れのようです。
タイトル一覧 |