画像の色数を求めたりヒストグラムを作るためのソートをいろいろ実装してみた

algorithm practice programming

画像の色数を求めるにはハッシュ的なものを使うよりもソートした方が速いという話です。


また、ヒストグラムを高速に作ろうとすると色の深度に応じてメモリを食います。RGBそれぞれが8ビットだと64MBほどメモリを食います。対してソートでやろうとすると、画素数分だけで済むのでメモリ的にも優しいです。


そんなわけで、ソートです。上記ではクイックソートを使ってますが、クイックソートが最善手とは限りません。最近はメモリが豊富なので、バケツソートや分布数え上げソートや基数ソートも十分実用的です。どれがいいだろう、というわけでいくつか試してみました。クイックソート、分布数え上げソート、基数ソートを手持ちのMac Book Airで試してみました。コードはこちら。


4バイトの符合なし整数をソートするという簡単なコードです。以下のソートを比べています。

  • 標準Cライブラリのクイックソート
  • 手書きのクイックソート
  • 分布数え上げソート（最後のコピー処理がmemcpy）
  • 分布数え上げソート（最後のコピー処理がforループ）
  • 分布数え上げソート（最後のコピー処理がmemcpy、ポインタを使ってループを少し最適化）
  • 基数ソート（バイト単位）
  • 基数ソート（バイト単位、ポインタを使ってループを少し最適化）
  • 基数ソート（バイト単位、ポインタを使ってループをさらに最適化）
  • 基数ソート（ワード単位）


結果としては、概ねワード単位の基数ソートが最も速かったです。つうわけで、画像処理ではワード単位の基数ソートを使うのがよさそうです。基数ソートは少しだけ工夫しました。基数ソートでは、普通は単位毎に結果をコピーするのですが、ダブルバッファリングすることでその手間をなくしました。画素数が大きくなればなるほど効いてくるはずです。以下は、Mac Book Air 2.13 GHz Intel Core 2 Duo, Memory 4 GB 1067 MHz DDR3で実行した結果です。まずは実機での結果。

QVGA 24bpp 320x 240 (size = 76800, range = 16777216)
qsort : 0.023937 [sec]
quick_sort : 0.022483 [sec]
counting_sort : 0.211722 [sec]
counting_sort2 : 0.146360 [sec]
counting_sort3 : 0.133482 [sec]
radix_sort : 0.006259 [sec]
radix_sort2 : 0.005574 [sec]
radix_sort3 : 0.005545 [sec]
radix_sort4 : 0.004007 [sec]

VGA 24bpp 640x 480 (size = 307200, range = 16777216)
qsort : 0.105436 [sec]
quick_sort : 0.092361 [sec]
counting_sort : 0.184831 [sec]
counting_sort2 : 0.184686 [sec]
counting_sort3 : 0.169230 [sec]
radix_sort : 0.025758 [sec]
radix_sort2 : 0.024495 [sec]
radix_sort3 : 0.023203 [sec]
radix_sort4 : 0.015684 [sec]

XGA 24bpp 1024x 768 (size = 786432, range = 16777216)
qsort : 0.288884 [sec]
quick_sort : 0.260471 [sec]
counting_sort : 0.274694 [sec]
counting_sort2 : 0.272200 [sec]
counting_sort3 : 0.257774 [sec]
radix_sort : 0.069239 [sec]
radix_sort2 : 0.066146 [sec]
radix_sort3 : 0.060907 [sec]
radix_sort4 : 0.040482 [sec]

Nexus S 24bpp 480x 800 (size = 384000, range = 16777216)
qsort : 0.134426 [sec]
quick_sort : 0.118140 [sec]
counting_sort : 0.198503 [sec]
counting_sort2 : 0.198470 [sec]
counting_sort3 : 0.182864 [sec]
radix_sort : 0.033405 [sec]
radix_sort2 : 0.031146 [sec]
radix_sort3 : 0.029891 [sec]
radix_sort4 : 0.019964 [sec]

Mac Book Air 24bpp 1440x 900 (size = 1296000, range = 16777216)
qsort : 0.492288 [sec]
quick_sort : 0.439028 [sec]
counting_sort : 0.376246 [sec]
counting_sort2 : 0.370595 [sec]
counting_sort3 : 0.353696 [sec]
radix_sort : 0.113894 [sec]
radix_sort2 : 0.110131 [sec]
radix_sort3 : 0.102530 [sec]
radix_sort4 : 0.069099 [sec]

iMac 24bpp 2560x1440 (size = 3686400, range = 16777216)
qsort : 1.493648 [sec]
quick_sort : 1.320081 [sec]
counting_sort : 0.833016 [sec]
counting_sort2 : 0.819314 [sec]
counting_sort3 : 0.810189 [sec]
radix_sort : 0.332729 [sec]
radix_sort2 : 0.316817 [sec]
radix_sort3 : 0.292213 [sec]
radix_sort4 : 0.200232 [sec]

同じマシンでWindows XP on Virtual Boxで実行した結果がこちら。

QVGA 24bpp 320x 240 (size = 76800, range = 16777216)
qsort : 0.016000 [sec]
quick_sort : 0.000000 [sec]
counting_sort : 0.485000 [sec]
counting_sort2 : 0.765000 [sec]
counting_sort3 : 0.719000 [sec]
radix_sort : 0.000000 [sec]
radix_sort2 : 0.031000 [sec]
radix_sort3 : 0.000000 [sec]
radix_sort4 : 0.016000 [sec]

VGA 24bpp 640x 480 (size = 307200, range = 16777216)
qsort : 0.093000 [sec]
quick_sort : 0.047000 [sec]
counting_sort : 0.687000 [sec]
counting_sort2 : 0.844000 [sec]
counting_sort3 : 0.828000 [sec]
radix_sort : 0.062000 [sec]
radix_sort2 : 0.047000 [sec]
radix_sort3 : 0.047000 [sec]
radix_sort4 : 0.047000 [sec]

XGA 24bpp 1024x 768 (size = 786432, range = 16777216)
qsort : 0.234000 [sec]
quick_sort : 0.188000 [sec]
counting_sort : 0.656000 [sec]
counting_sort2 : 0.781000 [sec]
counting_sort3 : 0.812000 [sec]
radix_sort : 0.188000 [sec]
radix_sort2 : 0.235000 [sec]
radix_sort3 : 0.171000 [sec]
radix_sort4 : 0.109000 [sec]

Nexus S 24bpp 480x 800 (size = 384000, range = 16777216)
qsort : 0.125000 [sec]
quick_sort : 0.063000 [sec]
counting_sort : 0.625000 [sec]
counting_sort2 : 0.719000 [sec]
counting_sort3 : 0.813000 [sec]
radix_sort : 0.047000 [sec]
radix_sort2 : 0.046000 [sec]
radix_sort3 : 0.047000 [sec]
radix_sort4 : 0.047000 [sec]

Mac Book Air 24bpp 1440x 900 (size = 1296000, range = 16777216)
qsort : 0.359000 [sec]
quick_sort : 0.282000 [sec]
counting_sort : 0.563000 [sec]
counting_sort2 : 0.906000 [sec]
counting_sort3 : 0.969000 [sec]
radix_sort : 0.297000 [sec]
radix_sort2 : 0.281000 [sec]
radix_sort3 : 0.250000 [sec]
radix_sort4 : 0.156000 [sec]

iMac 24bpp 2560x1440 (size = 3686400, range = 16777216)
qsort : 0.719000 [sec]
quick_sort : 0.766000 [sec]
counting_sort : 0.765000 [sec]
counting_sort2 : 1.234000 [sec]
counting_sort3 : 1.188000 [sec]
radix_sort : 0.797000 [sec]
radix_sort2 : 0.640000 [sec]
radix_sort3 : 0.563000 [sec]
radix_sort4 : 0.390000 [sec]


次は、画像処理向けの高速なmemcmp、memcpy、bzeroあたりをやってみましょうかね。