ダブル配列のライブラリを公開しているページです. An Implementation of Double-Array Trie URL: http://linux.thai.net/~thep/datrie/datrie.html Darts: Double-ARray Trie System URL: http://chasen.org/~taku/software/darts/ Dame URL: http://www.void.in/wiki/Dame Tiny Double-Array Library URL: http://nanika.osonae.com/TinyDA/index.html Dynamic Double-Array Library URL: http://nanika.osonae.com/DynDA/index.html
一般にソートアルゴリズムの計算量はソート対象となるデータ数NについてO(N^2)とかO(NlogN)等で評価する。数値データのソートであれば特に問題はないのだが、文字列データの場合は一回の比較に対して文字列長Mに比例する計算量O(M)がかかってしまう。例えばクイックソートであればO(NlogN)ではなくO(MNlogN)となる。よってMが非常に大きい場合はソート性能の劣化を招く。 文字列ソートに付いてはBently&Sedgewickのマルチキー・クイックソート(multikey-quicksort)という改良版クイックソートが存在する。このソート法は、ある工夫によって一回の比較を文字列長Mに依存しない形で実現している。 例えば文字列appleとapplicationの比較について考える。 # 先頭の文字を比較 [a]pple = [a]pplication # 2文字目を比較 a[p]p
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く