言い出しっぺの法則。

404 Blog Not Found:algorithm - bucket sort - 比較しなければソートは相当速い
これほど素晴らしいアルゴリズムなのに、なぜlibcやLL言語の組み込みとして用意されていないのでしょう?
https://plus.google.com/103748274114027132441/posts/VmpVES1hFds - Shiro Kawai さんのコメント
他のソートアルゴリズムのような汎用のライブラリになってないのは、目的によってチューニングポイントが違って、それらにすべて対応するのを書くよりはその都度書いた方が簡単だから、かなあ。

というわけで書きました。

工夫のしどころ

JavaScriptの実装例とはだいぶ異なりますが、インターフェイスは似ております。

404 Blog Not Found:algorithm - bucket sort - 比較しなければソートは相当速い
工夫のしどころは二カ所。一つは。要素からキーを取り出すv2kと、そのキーから番号を取り出すk2iをユーザー指定できるようにしたこと。デフォルトではv2kは値をそのまま返し、k2iは呼び出しの深さに対応する文字のunicode番号を返すようにしてあります。別の言い方をするとMSD radix sortと同じ振るまい。JavaScript(に限らずスクリプト言語の組み込みsortの多く)はデフォルトが辞書順(lexicographic order)なのでそのまま代用できます。

これに対して、C版はこうです。

  int bucketsort(
    void **base,
    size_t nmemb,
    keyaccessor_t key,
    indexer_t     idx,
    comparator_t  cmp
  );

JSとは異なりCの配列は自分自身の長さなんて知らないので、明示的に指定する必要があります。keyidxはJSの場合と同じ。JSと違って省略はできませんが、NULLを渡すことでデフォルトの文字列ソートになります。

ただしもう一つcmpというのが加わっております。これはlibcのqsort()heapsort()heapsort()に渡す比較関数と同じシグネチャの関数です。「比較しないのが bucket sort の一番の美点なのに、なぜ?

それは一重に以下の手がCではあまりにコスト高だからです。

そしてもう一つが、重複キーを持つ要素を一旦連想配列(JavaScriptでは素のオブジェクト)に落とした上で、キーだけをソートしてからそのキーを使って連想配列に格納した要素を取り出していること。こうすることで、「バケツが一個しか使われなかった」状態が一意にソート終了となります。

このため当初STLでmapが使えるC++で加工かなあと思ったのですが、XSなどで使い回しやすくなることを狙って、なるべく他のファイルに依存しないものが欲しかった。Cでなんとかならないの…

と考えた結果が、「重複キーをまとめる」のではなく「重複キーがないかを必要に応じてチェックする」という手法。この部分は最悪 O(n) になってしまうのですが、動的に配列を作っては捨てするよりもこの方がずっと速くてメモリーにも優しいようです。cmpはこの部分で使っております。順位ではなくただキーが同一かどうかを確認するためのみ。

とはいえバケツはやはり安くはありません。連結リストとキューで実装したのですが、そのため元配列の倍のワークエリアが必要になります。バケツは勘定に入ってません。

というわけでバケツ数は256に固定でスタックに確保していますそのため。idxは0から255のバケツ番号を返す必要があります。よって符号なし整数の場合はたとえば以下のようにしてradixを取り出す必要があります。

int radix(void *v, size_t d)
{
    long n = (long) v;
    long r = (n >> ((sizeof(long) - d - 1) * 8)) & 0xff;
    return r;
}

しかし実際に試してみたところ、/usr/bin/dict/words程度(OS X Lionで235886語)でもsort(1)にもperl -e 'print sort <>'にも勝ちました(マニュアル参照)。メモリーの使用量もむしろ3割減。余談ですがOS Xのsort(1)の遅さにはびっくりです。余裕でperlに負けてます。

それでも後述のとおり、「まっとうな」Ubuntuのsortにも勝っております。

久々にCで書いたので、ところどころ変なところがあるかも知れません(Makefileとか)。pull requestうぇるかむということで。

Enjoy!

Dan the Bucket Sorter

Pod 2 HTML'd manual

NAME

bucketsort - bucket sort


SYNOPSIS

  #include "bucketsort.h"
  int bucketsort(
    void **base,
    size_t nmemb,
    keyaccessor_t key
    indexer_t     idx,
    comparator_t  cmp
  );


DESCRIPTION

The bucketsort() is an implementations of bucket sort.

base

The reference to the array of pointers to the element (or integers whose size equals to that of pointer) to be sorted in-place.

nmemb

The nember of elements in the array.

key

The function pointer which takes the reference to the array element and returns the reference to the key.

  void *key(void *element);

When NULL the default function is used which is defined as:

  inline void *identity(void *v)
  {
    return v;
  }

idx

The function pointer which takes the reference to the key and the recursion level of the caller and returns the integer value between 0 and 255, which is the bucket id.

When NULL the default function is used which is defined as:

  inline int charAt(void *v, size_t i)
  {
    char *s = (char *) v;
    return s ? strlen(s) > i ? s[i] : 0 : 0;
  };

In other words, default acts the same as the MSD radix sort with variable lengths.

cmp

The Function pointer which compares two keys. This is needed to allow elements with same keys. Its signature is the same as the one you pass to qsort(), mergesort() and heapsort() in libc.

When NULL, it defaults to strcmp().


EXAMPLE

See main.c which is included in the distro.


IMPLEMENTATION DETAILS

The bucket is implemented as a queue by linked lists. The whole array is converted to the linked list before sorted then written back to the array. If you like you can use the list sorter directly as:

  list_t bucketsort(
    list_t head,
    size_t nmemb,
    keyaccessor_t key,
    indexer_t     idx,
    comparator_t  cmp
  );

where:

  typedef struct {
    void *car, *cdr;
  } _cons_t, *list_t;


BENCHMARK

1e7.txt is created as:

  perl -MList::Util=shuffle 'print shuffle 1..1e7' > 1e7.txt

Mac OS X v10.7.2/iMac 12,2/Core i7

    % /usr/bin/time -l ./bucketsort 1e7.txt > /dev/null
            7.09 real         6.93 user         0.15 sys
     402980864  maximum resident set size
             0  average shared memory size
             0  average unshared data size
             0  average unshared stack size
         98408  page reclaims
             0  page faults
             0  swaps
             0  block input operations
             0  block output operations
             0  messages sent
             0  messages received
             0  signals received
             0  voluntary context switches
           183  involuntary context switches
    % /usr/bin/time -l /usr/bin/sort 1e7.txt > /dev/null
          150.39 real       150.10 user         0.25 sys
     559497216  maximum resident set size
             0  average shared memory size
             0  average unshared data size
             0  average unshared stack size
        136606  page reclaims
             0  page faults
             0  swaps
             1  block input operations
             1  block output operations
             0  messages sent
             0  messages received
             0  signals received
             3  voluntary context switches
           887  involuntary context switches
    % /usr/bin/time -l /usr/bin/perl -e 'print sort <>' 1e7.txt > /dev/null
           26.87 real        25.96 user         0.88 sys
    1579208704  maximum resident set size
             0  average shared memory size
             0  average unshared data size
             0  average unshared stack size
        434812  page reclaims
           126  page faults
             0  swaps
            18  block input operations
             6  block output operations
             0  messages sent
             0  messages received
             0  signals received
            46  voluntary context switches
           226  involuntary context switches

Ubuntu 11.10 AMD64 / VMWare@iMac

    $ time ./bucketsort 1e7.txt > /dev/null 
    real    0m9.059s
    user    0m8.825s
    sys     0m0.208s
    $ time sort 1e7.txt > /dev/null 
    real    0m33.136s
    user    0m31.514s
    sys     0m1.528s


RETURN VALUES

The bucketsort() function returns the value 0 if successful; otherwise the value -1 is returned and the global variable errno is set to indicate the error.


ERRORS

ENOMEM

When bucketsort() fails to allocate the memory needed to build the list, which is exactly twice the size of the original array since each element takes two pointers.


SEE ALSO

sort(3), qsort(3), megesort(3), heapsort(3), radixsort(3)

http://en.wikipedia.org/wiki/Bucket_sort