ToDo:
師匠が書いてた文章読み飛ばしてたなーと思って読んだ
http://morihyphen.hp.infoseek.co.jp/log2/200707.html#2007-07-22
ら、前ざっと見た時と同じ疑問が生まれてきたんだけど、 最後に
と思ったけど、これって最初にサイズ調べておくのとどう違うの？
書いてあった。
興味あるのは今の環境だとどっちが速いのかなぁということかな。 なんか realloc の方が速いくらいなんじゃないかとか思うけど、 なんとなく realloc がイヤなのは激しく同感で、 C++ とか realloc を隠して罪悪感を隠蔽してくれるのはすばらしい。
カプセル化ってのは罪悪感を encap なんとか (←なぜかつづれない)していると言ってよい。
#include <stdlib.h>
#include <time.h>
#include <set>
#include <vector>
using namespace std;
int main() {
set<int> m;
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 100; j++) {
m.insert(rand());
}
}
vector<int> v;
clock_t s = clock();
for (int i = 0; i < 10; i++) {
//copy(m.begin(), m.end(), back_inserter(v));
v.resize(m.size());
copy(m.begin(), m.end(), v.begin());
}
printf("%f\n", 1.0 * (clock()-s) / CLOCKS_PER_SEC);
}
とかだと前者 1.6 秒後者 1.3 秒か。 set::size は O(1) でできちゃうので まぁ realloc があると少しはパフォーマンスに影響するってことだろう。
えーとつまりツリー構造にはサイズを保持しとくっていう結論に。
いや個々の要素の長さが固定で 1 だからっていうような話もあるけど まぁそれも中身の長さの総量を記録しておけばいいのだけど まぁそれも pretty print とかのためにそんな情報残しておくわけがない。
にしてもまぁ 100万回もランダム生成して木構造につっこんでバランスツリー調整して、 その100万要素のツリーを10回もなめつつ1000万要素のvectorを 文句も言わず作ってくれるコンピュータさんはえらいと思う。
俺はこういう偉い人に対して 「お前のようなヤツがいるから他の子への仕事の要求が上がるんだよ!」 とか言ってるわけで、 まぁなかなかむずかしいところ。
(01:40)
http://shinh.skr.jp/m/?date=20070730#c03
まぁめどいのでとりあえずさっきのコードを Linux on Celeron 1.7GHz で。
size を外部に持つずるいヤツが 4.37 秒で、 realloc しまくるヤツが 5.15 秒で、 最初に数えとくやつが 8.57 秒。
さっきの Core2Duo とかよりキャッシュの乗り方とか 悪かったりすると変わるかなーと思ったんだけどだいたい似たような割合やね。
さっきのはまとめると 1.3秒 1.6秒 2.6秒 。
直感的に同じメモリに対して realloc 繰り返すのは 速そう(だしなんか速いと聞いた気もする) んだけどそれにしても、直感的に差がありすぎてうさんくさい。
まぁカンばっかりなのでまた今度。
(21:57)
やっぱりそうなのか!
http://arena.nikkeibp.co.jp/article/column/20070607/1000581/?P=2
Windows XPと同じように、Windows Vistaも使い込むと遅くて重くなる。特に、
で、それなんでなの。というのが長年の疑問。
95系みたいに使い込むと不安定になるとかよりはマシなのかもしれないけど。
(22:02)
| 前 | 2007年 7月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 | ||||
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
「罪悪感をencap なんとか」、いい言葉ですね。僕も今後使っていきます。（使う場面無いですが）
「最初にサイズ調べておく」のは、どっかに記録しておくのではなく、mallocする前に、tree_size()とかの関数で長さだけ計算しておく、というほうの意味でした。下らないねたであることに変わりはないですが。
あと、ここ一年ぐらい仕事で直感で見つけたボトルネックはことごとく間違えているので僕の最適化話は信用しないほうがいいです…
「通常」って書いてしまうと、きっと良くないですね…。書き直したほうがいいような気がしてきました。
あ、はい先に長さだけ記録して行く、ってのはわかってたんですが、とりあえず malloc*1 と realloc*log(n) を比較してみたかった、という感じでした(両方やれよという感じですが)。で一応サイズを別に測るのに近そうなのを雑にやってみたのですが、
for (int i = 0; i < 10; i++) {
int x = 0;
for (set<int>::const_iterator ite = m.begin(); ite != m.end(); ++ite) {
x++;
}
v.resize(x);
copy(m.begin(), m.end(), v.begin());
}
これだと 2.6 秒ということで、なんかえらい遅いですね。ほえほえ set のイテレータがボトルネックかいや、という感じです。
私も realloc には根拠もなく不信感を抱いてたのですが、もうちょい信用して良いものなのかなと根拠レス気味に思いました。
あと時々無意味に C で書きたくなるのは罪悪感も関係してそうな気がなんとなくしています。
うえー。数えるよりreallocするほうがだいぶ速い、というのは結構意外ですね。ちゃんとベンチマークしましょう。> 自分
意外というより正直うさんくさいと思ったので自前の tree でもうちょい確実に比較してみた方が良さげですね。