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

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

ソートにおいて、ソート対象の配列に対するポインタを操作すれば、各関数の中でソート対象の配列が持つ要素に対するメモリを確保する必要が無くなる。もし、ソート対象の配列の要素の型がポインタよりも小さいサイズであれば、その要素に対するメモリを確保した方が良いが、例えばソート対象の配列の要素が構造体である場合は、その要素に対するメモリ量が大きいので、ダブルポインタでポインタをソート対象として扱うべきである。ポインタのサイズはプラットフォームに依存するので、sizeof()で確認する。

ダブルポインタを用いてポインタに対してメモリを確保するソート(sort())と、データの型に対してメモリを確保するソート(_sort())、それからライブラリのソート(qsort())、を比較してみた。ソート処理全体で確保した総メモリ量と、mallocを呼んだ回数をカウントしている。なお、構造体のソート対象のキー(age)以外は、参照もしないので、初期化すらしていない。ダブルポインタを用いる方がメモリ量が小さいし速い。ただ、やはりライブラリのソートの方がかなり速い。

なお、前回のプログラムでQuick sortのmalloc回数が多かったのは、ソート対象の配列数が1になった場合にreturnしていないため。

$ ./structsort 5000000
Size of Data struct : 68
Size of a pointer : 8
(Size of short: 2)
(Size of int: 4)
(Size of long: 8)

Quick sort (double pointer): 5.22 sec.
1045MB,3385634
Good. Sorted.

Quick sort : 6.48 sec.
8887MB,3385634
Good. Sorted.

Quick sort (library function) : 3.20 sec.
Good. Sorted.

実装はこちら Sort function optimized with double pointer · GitHub