 |
| クラス | ソートアルゴリズム |
|---|---|
| データ構造 | トライ |
| 最悪のパフォーマンス | 自分の） |
| 最悪の場合の空間複雑度 | 自分の） |
| 最適 | ? |
バーストソートとその派生は、文字列をソートするためのキャッシュ効率の高いアルゴリズムです。従来の基数ソートの派生ですが、一般的な文字列の大規模なデータセットに対してより高速です。2003年に初めて公開され、その後、最適化されたバージョンもいくつか公開されました。[ 1 ]
バーストソートアルゴリズムは、文字列のプレフィックスをトライ木に格納し、ソートされた一意のサフィックス（バケットと呼ばれる）を含むポインタの拡張可能な配列をエンドノードとして使います。いくつかのバリエーションでは、文字列の末尾をバケットにコピーします。バケットが所定のしきい値を超えると、バケットはトライに「バースト」するため、このソートは「バースト」と呼ばれます。より新しいバリエーションでは、メモリ使用量を削減するために、より小さなサブバケットを持つバケットインデックスが使用されています。ほとんどの実装では、バケットの内容をソートするために、3元基数クイックソートの拡張であるマルチキークイックソートが使用されています。入力を共通のプレフィックスを持つバケットに分割することで、キャッシュ効率の高い方法でソートを行うことができます。
バーストソートは、 MSD基数ソート[ 1 ]に似たソートとして導入されましたが、キャッシュを考慮し、トライ構造の特性により関連する基数が互いに近い位置に格納されるため、より高速です。これは、実世界でよく見られる文字列の特性を利用します。漸近的には基数ソートと同じで、時間計算量はO ( wn )（wはワード長、nはソート対象の文字列数）ですが、メモリ分散が優れているため、大規模な文字列データセットでは2倍の速度になります。これは「大規模な文字列セットをソートする最も高速なアルゴリズム」と謳われています。[ 2 ]
参考文献
- ^ a b Sinha, R.; Zobel, J. (2005). 「動的トライを用いた大規模文字列セットのキャッシュを意識したソート」(PDF) . Journal of Experimental Algorithmics . 9 : 1.5. CiteSeerX 10.1.1.599.861 . doi : 10.1145/1005813.1041517 . S2CID 10807318 .
- ^ 「バーストソート: 大規模な文字列セットをソートする最速のアルゴリズム | Hacker News」。
- バーストソートの派生（C-バーストソート）はバーストソートよりも高速です：Sinha, Ranjan; Zobel, Justin; Ring, David (2006年1月). 「コピーを用いたキャッシュ効率の良い文字列ソート」（PDF） . Journal of Experimental Algorithmics . 11 (1.2): 1.2. CiteSeerX 10.1.1.85.3498 . doi : 10.1145/1187436.1187439 . S2CID 3184411.オリジナル（PDF）から2007年10月1日にアーカイブ。 2007年5月31日閲覧。
- バーストソートで使用されるデータ型：Heinz, Steffen; Zobel, Justin; Williams, Hugh E. (2002年4月). 「バーストトライ：文字列キーのための高速で効率的なデータ構造」（PDF） . ACM Transactions on Information Systems . 20 (2): 192– 223. CiteSeerX 10.1.1.18.3499 . doi : 10.1145/506309.506312 . S2CID 14122377.オリジナル（PDF）から2013年12月5日にアーカイブ。 2007年9月25日閲覧。
- Sinha, Ranjan; Zobel, Justin (2003). 「大規模文字列集合の効率的なトライベースソート」(PDF) .第26回オーストラレーシアコンピュータサイエンス会議議事録. 第16巻. オーストラリアコンピュータ協会. pp. 11– 18. CiteSeerX 10.1.1.12.2757 . ISBN 978-0-909-92594-9. 2012年2月8日にオリジナル（PDF）からアーカイブ。2007年9月25日閲覧。
- Sinha, Ranjan; Wirth, Anthony (2010年3月). 「エンジニアリングバーストソート：高速インプレース文字列ソートに向けて」(PDF) . ACM Journal of Experimental Algorithmics . 15 (2.5): 1– 24. doi : 10.1145/1671970.1671978 . S2CID 16410080 .
外部リンク
- Javaでのバーストソートの実装: burstsort4j
- Judy配列はコピーバーストソートの一種です: C実装
