« substringsort.c の書き直し その4 | トップページ | libdivsufsort-1.2.0 (安定版) リリース »

Tandem repeat sorting algorithm

libdivsufsort-1.1.7」を公開。 substringsort の後に行っていたソートを Maniscalco's tandem repeat sorting algorithm (trsort) に変更しました。

この Tandem repeat sort は、Ranksort と Copy method (の一部) を組み合わせたようなアルゴリズムで、大抵のデータは高速にソートすることができます。が、最悪時間計算量は O(n^2 log n) になるため、divsufsort-1.1.7 ではそうなる前にソート法を Larsson-Sadakane sort へ切り替えて残りを処理しています。

これで、divsufsortの最悪時間計算量が O(n log n) になったはず・・。

|

« substringsort.c の書き直し その4 | トップページ | libdivsufsort-1.2.0 (安定版) リリース »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/154471/41473680

この記事へのトラックバック一覧です: Tandem repeat sorting algorithm:

« substringsort.c の書き直し その4 | トップページ | libdivsufsort-1.2.0 (安定版) リリース »