言い出しっぺの法則。
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の配列は自分自身の長さなんて知らないので、明示的に指定する必要があります。keyとidxは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)
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。