« 2007年2月 | トップページ | 2007年4月 »

substringsort.c の書き直し その4

libdivsufsort-1.1.6」を公開。 Internal buffer と D&C を用いた高速なマージを導入したおかげで、 substringsort の最悪時間計算量が O(n log m) になりました。 (n は入力の長さ、m はtypeB*suffixの数)

現在、 divsufsort のライセンスを LGPL から MIT/X11 License に変更しようか検討中・・。

| | コメント (0) | トラックバック (0)

substringsort.c の書き直し その3

libdivsufsort-1.1.5」を公開。

ちょっと前から作っていた Multikey Introsort がようやく完成したので、とりあえず組み込んでみました。 速さは・・、幅優先な Introsort とたいして変わらず。 orz。

新しい Merge アルゴリズムの方はほぼ完成しているので、 substringsort.c の書き直しは次で終わる予定です。

| | コメント (0) | トラックバック (0)

substringsort.c の書き直し その2

libdivsufsort-1.1.4」 を公開。 Ternary Quicksort と Heapsort を組み合わせた Introspectivesort、 Kiwielさんの Two-stage double-index controlled terunary partition などを実装しました。

| | コメント (0) | トラックバック (0)

substringsort.c の書き直し その1

libdivsufsort-1.1.3」 を公開。 今回は、深さ優先の Multikey Quicksort を 幅優先のシンプルな Ternary Quicksort に置き換えて、 pivot選択を Median-3, Median-5, Median-3-3 の三段階に変更しました。

あとは、Introsort を実装して、 Merge と drsort を書き換えるだけ・・先は長い。。

| | コメント (0) | トラックバック (0)

« 2007年2月 | トップページ | 2007年4月 »