読者です 読者をやめる 読者になる 読者になる

Sortアルゴリズムの消費メモリについて

Sortアルゴリズムの消費メモリについて(続) - Tech random memoranda

Sortアルゴリズムを自分で書いてみるとそれぞれの特性が良く分かってくる。メモリを最も消費しないのは、Bubbleソートのようにソート対象の配列を直接触っていけるような、時間がかかるが単純なアルゴリズムの場合。

ただ、そのようなアルゴリズムを優先すべきアプリケーションはなかな思いつかない(配列が小さければ消費メモリを気にすることはないだろうし、消費メモリを気にすることがないなら計算量を考慮するから)。組み込み系で、消費メモリを小さくすることが最優先されるような場合は、必要になるかもしれない。

では、QuickソートとMergeソート、どのくらいメモリを使うのだろうか。前回の安直なプログラムと、与えられたソート対象の配列のメモリ領域をなるべく直接変更しながらメモリ量を抑えるプログラム、を書いて比較。 mallocをラップして、確保したメモリ量の総和と、mallocを呼んだ回数を、それぞれのアルゴリズムでカウントして比較する。

mallocのラップ関数は以下。

unsigned long mem_size;
unsigned int malloc_cnt;

void* _malloc(size_t size){
    mem_size += size;
    malloc_cnt ++; 
    return malloc(size);
}

Macで実行した結果がこちら。

$ ./three_sorts 10000000
Quick sort : 8.67 sec.
Sorted check OK.
mem_size = 4024MB, malloc_cnt = 30000000
Merge sort : 7.25 sec.
Sorted check OK.
mem_size = 2669MB, malloc_cnt = 29999997

$ ./two_sorts_low_memory 10000000
Quick sort : 6.56 sec.
Sorted check OK.
mem_size = 1563MB, malloc_cnt = 10000000
Merge sort : 3.91 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999

メモリ割り当て(mallocを呼ぶ回数)が少なくなるとその分速くなる。メモリ割り当てにはそれ相当の時間がかかるからだ。

Mergeソートの場合だと、malloc_cntが一回少ないので、その分メモリ量が抑えられている。 良くわからないが、配列が非常に大きいので、その一回が使用するメモリ量を大きく引き離す結果になっているのだろうと予測。結局この一回が、速度差に影響している気がしてならないが。

→ Quick sortにおいて、ソート対象の配列数が1の場合、関数を抜けるべきところを実行してしまっているため、malloc_cntが多くなってしまっている。

ソート対象のサイズが100,000,000でも今回はMergeソートの方が遅くなる現象は発生していない。

$ ./two_sorts_low_memory 100000000
Quick sort : 77.14 sec.
Sorted check OK.
mem_size = 17042MB, malloc_cnt = 100000000
Merge sort : 42.81 sec.
Sorted check OK.
mem_size = 10169MB, malloc_cnt = 99999999

実装はこちら Optimized for memory usage · GitHub