↑
なんか間違って全然違うコードはっててわらった。しんどい時はちゃんと寝ましょう。
個人的に list と set っていうデータ構造はこう、全然信用してないというか、あまりこう登場頻度が高くないとされている物体で、
- 今のアーキテクチャでは、何要素くらいから探索が vector より set の方が良くなるのか
- 今のアーキテクチャでは、何要素くらい移動する必要が発生すると挿入が vector より list の方が良くなるのか
- URL の群れがあったとして、何要素くらいから線型探索よりハッシュが速くなるのか
- メソッドテーブルを作るとして、何要素くらいから線型探索よりハッシュが速くなるのか
- vector と list の末尾挿入ってどのくらい差が出るのか
とかそのへんが気になっている。
最後のやってみた。
vector が 0.210 秒で list が 0.850 秒とかで、 vector の方が速かった。まぁそらそうだ。当たり前だと思う人で、償却定数時間とかの単語を知らない人は、このへん見てみるといいかも:
http://chasen.org/~taku/blog/archives/2007/02/_o1.html
#include <stdio.h> #include <time.h> #include <vector> #include <list> using namespace std; int main() { vector<int> v; list<int> l; { clock_t cl = clock(); for (int i = 0; i < 10000000; i++) { v.push_back(i); } printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC); } { clock_t cl = clock(); for (int i = 0; i < 10000000; i++) { l.push_back(i); } printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC); } }