コード最適化についての考察

文字列のリストとその出現数をカウントして多い方から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のようなものはあまり見ない。

ただ、これをMacLinux(Google Compute Engine - vCPU 1)で実行してみたところ、Macの方がSortが10倍以上速いため、keyが5Mくらいでは、Sortを使った方法の方でも速くなった。Clang/LLVMではC++11におけるsort()がかなりうまく最適化されているようだ。以下記事を見ても、Clangが最も速いことが分かる。

solarianprogrammer.com

#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