ソートの速度比較
ふむふむ、NetBSD 由来の qsort が速いと。unsigned int の要素数 10,000,000 で試してみた。表中の数字は所要時間で単位は秒。
まず、Pentium M 2GHz の coLinux on Windows の gcc-4.0 で、 コンパイルオプションは -O2 だけ。
| ランダム | ソート済み | 逆順ソート済み | 大体ソート済み | |
|---|---|---|---|---|
| qsort | 5.08 | 4.29 | 4.45 | 4.05 |
| pgsql | 4.36 | 0.06 | 0.06 | 2.91 |
| qsortG | 3.29 | 1.70 | 1.81 | 2.11 |
| STL | 1.78 | 0.70 | 0.74 | 0.74 |
同じマシンの Windows で VC2005 で /O2 で コンパイル。
| ランダム | ソート済み | 逆順ソート済み | 大体ソート済み | |
|---|---|---|---|---|
| qsort | 4.547 | 1.890 | 1.656 | 2.203 |
| pgsql | 4.047 | 0.062 | 0.063 | 2.031 |
| qsortG | 4.047 | 0.141 | 1.125 | 1.454 |
| STL | 2.532 | 0.469 | 0.531 | 1.422 |
なお、qsort は 標準の qsort、pgsql は PostgreSQL-8.14 の src/port/qsort.c を取ってきて qsort => qsort_pg にしてあるも*1、qsortG は ここ にあるやつで*2、STL は std::sort を使ったやつ。
ということで、ソート済みと逆順ソート済みは PostgreSQL(NetBSD 由来) の qsort がえらい速い。けど全体的な速度を見れば std::sort に分がある感じかな。気が向いたら PostgreSQL の qsort を template にしてみよう。
一応ベンチマークを取ったコードを置いておく(コンパイルに boost が必要)。ベンチマークの取り方に問題あれば誰か指摘よろ。あ、やたら面倒くさいやり方をしているとかいうツッコミは勘弁ね。
#include <iostream> #include <functional> #include <vector> #include <boost/random/mersenne_twister.hpp> #include <boost/random/random_number_generator.hpp> #include <ctime> extern "C" { void qsort_pg(void *, size_t, size_t, int (*compare)(const void*, const void*)); void qsortG(void *, size_t, size_t, int (*compare)(const void*, const void*)); } static int compare_uint(const void *a, const void* b) { const unsigned int* i = reinterpret_cast<const unsigned int*>(a); const unsigned int* j = reinterpret_cast<const unsigned int*>(b); return *i < *j ? -1 : (*i == *j ? 0 : 1); } struct generate_random { void operator()(std::vector<unsigned int>& v, size_t size) const { boost::mt19937 mt(0); v.resize(size); for (std::vector<unsigned int>::iterator it = v.begin(); it != v.end(); ++it) { *it = mt(); } } }; struct generate_sorted { void operator()(std::vector<unsigned int>& v, size_t size) const { generate_random r; r(v, size); std::sort(v.begin(), v.end()); } }; struct generate_reverse_sorted { void operator()(std::vector<unsigned int>& v, size_t size) const { generate_random r; r(v, size); std::sort(v.begin(), v.end(), std::greater<unsigned int>()); } }; struct generate_nearly_sorted { void operator()(std::vector<unsigned int>& v, size_t size) const { boost::mt19937 mt; boost::random_number_generator<boost::mt19937> r(mt); generate_sorted s; s(v, size); for (size_t i = 0; i < size / 20; i++) { int j = r(size); int k = r(size); std::swap(v[j], v[k]); } } }; struct glibc_qsort { void operator()(std::vector<unsigned int>& v) const { qsort(&v[0], v.size(), sizeof(unsigned int), compare_uint); } }; struct pg_qsort { void operator()(std::vector<unsigned int>& v) const { qsort_pg(&v[0], v.size(), sizeof(unsigned int), compare_uint); } }; struct stl_sort { void operator()(std::vector<unsigned int>& v) const { std::sort(v.begin(), v.end(), std::less<unsigned int>()); } }; struct qsortg_qsort { void operator()(std::vector<unsigned int>& v) const { qsortG(&v[0], v.size(), sizeof(unsigned int), compare_uint); } }; template<typename Generate, typename Sort> void benchmark(const char* name, size_t size, Generate g, Sort s) { std::vector<unsigned int> v; g(v, size); clock_t start = clock(); s(v); clock_t end = clock(); std::cout << name << '\t' << (double) (end - start) / CLOCKS_PER_SEC << std::endl; } template<typename Generate> void benchmark_set(const char* name, size_t size, Generate g) { std::cout << "=== " << name << " ===" << std::endl; benchmark("libc", size, g, glibc_qsort()); benchmark("PostgreSQL", size, g, pg_qsort()); benchmark("qsortG", size, g, qsortg_qsort()); benchmark("STL", size, g, stl_sort()); std::cout << std::endl; } int main(int, char**) { size_t size = 10000000; benchmark_set("random", size, generate_random()); benchmark_set("sorted", size, generate_sorted()); benchmark_set("reverse sorted", size, generate_sorted()); benchmark_set("nearly sorted", size, generate_nearly_sorted()); return 0; }
