コード最適化についての考察
文字列のリストとその出現数をカウントして多い方からN個取得する処理を考える。単純にやろうとすれば、とにかく文字列とその出現数をkey/valueとしてカウントしていき、最後にvalueでソートして多い方からN個取得すればいい。
ただし、Nが非常に小さい場合、このやり方は効率が悪い。つまり例えば、key/valueが1,000,000個あったとして、その中で多い方から5個取り出す場合、1,000,000個のリストをソートすることになり、それだけでO(nlogn)かかるが、Nが小さい場合にはこのソートは必要ない/ほとんど無駄なはずである。
以下の通り実装して、計算にかかる時間を測定した。
- take_top_n_by_sort() - 単純に全てのkey/valueをカウントして最後にvalueでソートする方法
- take_top_n_no_sort - ソートを使わず、出現数の多いN個を随時更新していく方法
- take_top_n_no_sort2 - 出現数の多いN個から最小の出現数を取得する処理をなるべく行わない方法
C++についていえば、このような用途でmapを使う必要性は無いと言える。mapはkeyがソートされたデータ構造となっているが、keyによるvalueの探索にはBinary SearchによるO(logn)が必要になる。一方、unordered_mapはハッシュを使用しており、探索はO(1)で済む。
また、Javaにはmapの実装としてTreeMapやHashMapがあるが、このような用途ではHashMapを使うべきだろう。他の言語でも、key/valueのデータ構造は必ずといって良いほど標準で実装されているが、C++のmapのようなものはあまり見ない。
ただ、これをMacとLinux(Google Compute Engine - vCPU 1)で実行してみたところ、Macの方がSortが10倍以上速いため、keyが5Mくらいでは、Sortを使った方法の方でも速くなった。Clang/LLVMではC++11におけるsort()
がかなりうまく最適化されているようだ。以下記事を見ても、Clangが最も速いことが分かる。
- 実装はこちら Take TOP N list from large amount of keys in C++11 · GitHub
- パラメータは、10,000,000個の文字列、各文字列の文字数は5、リストから5個取得
#define SIZE 10000000 #define CHARS 5 #define TOPN 5
- インプットデータは以下のように正規分布に従って乱数を生成することにより出現数に偏りを持たせているため、文字列の組み合わせ総数は11881376だがそれよりかなり少なくなっている
void make_input_data(vector<string>* out){ mt19937 mt(1); normal_distribution<double> dist(13.0,6.0); for(auto i=0;i<SIZE;i++){ string s; for(auto j=0;j<CHARS;j++){ s.push_back((char)(((int)dist(mt))%26+65)); } out->push_back(s); } }
- Macでの実行結果
$ g++ --version Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM version 7.0.2 (clang-700.1.81) Target: x86_64-apple-darwin14.5.0 Thread model: posix $ sysctl -a machdep.cpu machdep.cpu.max_basic: 13 machdep.cpu.max_ext: 2147483656 machdep.cpu.vendor: GenuineIntel machdep.cpu.brand_string: Intel(R) Core(TM) i5-4258U CPU @ 2.40GHz ... machdep.cpu.core_count: 2 machdep.cpu.thread_count: 4 $ g++ take_top_n.cpp -std=c++11 $ ./a.out Elapsed time for sort() with 5045629 keys : 815ms Elapsed time for take_top_n_by_sort() : 15689ms LMOOM LMKNK HLLMM MOKOO NPNKH Elapsed time for take_top_n_no_sort() : 47057ms NPNKH HLLMM LMKNK LMOOM MOKOO Elapsed time for take_top_n_no_sort_with_flag() : 15612ms NPNKH HLLMM LMKNK LMOOM MOKOO
- Linuxでの実行結果
$ g++ --version g++ (Debian 4.9.2-10) 4.9.2 Copyright (C) 2014 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 63 model name : Intel(R) Xeon(R) CPU @ 2.30GHz stepping : 0 microcode : 0x1 cpu MHz : 2300.000 cache size : 46080 KB physical id : 0 siblings : 1 core id : 0 cpu cores : 1 apicid : 0 initial apicid : 0 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 f ma cx16 sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm xsaveopt fsgsbase bmi1 a vx2 smep bmi2 erms bogomips : 4600.00 clflush size : 64 cache_alignment : 64 address sizes : 46 bits physical, 48 bits virtual power management: $ ./a.out Elapsed time for sort() with 5045954 keys : 10050ms Elapsed time for take_top_n_by_sort() : 25432ms NOLPL NOKMM PJOMO LMNMO NLOOM Elapsed time for take_top_n_no_sort() : 33195ms NOKMM NLOOM LMNMO PJOMO NOLPL Elapsed time for take_top_n_no_sort_with_flag() : 16060ms NOKMM NLOOM LMNMO PJOMO NOLPL
コンパイラによる最適化
- Macのg++に
-O3
をつけて実施した結果、およそ2倍くらい速くなる
$ g++ take_top_n.cpp -std=c++11 -O3 $ ./a.out Elapsed time for sort() with 4787637 keys : 331ms Elapsed time for take_top_n_by_sort() : 7743ms LMKNK LMOOM HLLMM MOKOO NPNKH Elapsed time for take_top_n_no_sort() : 19158ms NPNKH HLLMM LMKNK LMOOM MOKOO Elapsed time for take_top_n_no_sort_with_flag() : 8985ms NPNKH HLLMM LMKNK LMOOM MOKOO