なんか間違って全然違うコードはっててわらった。しんどい時はちゃんと寝ましょう。

個人的に 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);
    }
}
なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h