質問

長い文章になります。ご容赦ください。煮詰めると、質問です。 実行可能なインプレース基数ソートアルゴリズムはありますか？ ?

予備

膨大な数の 小型固定長 A"、"C"、"G"、"T "の文字だけを使った文字列（そう、ご想像のとおりです。 DNA を並べ替えたい。

今のところ、私は std::sort を使用しています。 イントロソート のすべての一般的な実装で STL . これはかなり有効です。しかし、私は、以下のように確信しています。 基数ソート は、私の問題設定に完全に適合しており、動作するはずです。 大いに 実際のところ、もっといいんです。

詳細

この仮定を非常に単純な実装でテストしたところ、比較的小さな入力（10,000のオーダー）については、これは真実でした（まあ、少なくとも2倍以上の速さです）。しかし、問題サイズが大きくなると、実行速度は著しく低下します ( N 5,000,000）。

理由は明白で、基数ソートはデータ全体をコピーする必要があるからです（実際、私の素朴な実装では複数回コピーしています）。これは、メインメモリに4GiBもの容量を入れてしまったことを意味し、明らかにパフォーマンスを低下させるものです。そうでなかったとしても、問題のサイズがさらに大きくなってしまうので、これだけのメモリを使う余裕はないのです。

使用例

理想的には、このアルゴリズムは2～100の任意の文字列長で、DNAとDNA5（ワイルドカード文字「N」を追加できる）、あるいは、DNAに IUPAC アンビギュイティコード (結果的に16個の異なる値になる)。しかし、これらのケースをすべてカバーすることはできないと理解しているので、速度が向上すればそれで満足です。どのアルゴリズムにディスパッチするかは、コードが動的に決定することができます。

研究内容

残念ながら ウィキペディアの基数ソートに関する記事 は役に立たない。インプレースバリアントについてのセクションは全くのゴミです。その 基数ソートに関するNIST-DADSのセクション はほとんど存在しない。という期待できそうな論文があります。 効率的な適応型インプレースラディックスソーティング MSL」というアルゴリズムが紹介されています。残念ながら、この論文も期待はずれでした。

具体的には、次のようなことがある。

まず、このアルゴリズムにはいくつかの間違いがあり、説明されていないことがたくさんあります。特に、再帰呼び出しの詳細が書かれていません（単に、現在のシフトとマスクの値を計算するために、何らかのポインタをインクリメントまたはリデュースしているのだと思われます）。また、関数 dest_group と dest_address を定義することなく これらを効率的に（つまりO(1)で）実装する方法がわかりません。少なくとも dest_address は些細なことではない)。

最後になりましたが，このアルゴリズムでは配列のインデックスと入力配列の中の要素を入れ替えることで，置換性を実現しています．これは明らかに数値配列にしか使えません。文字列で使う必要があります。もちろん、強い型付けをせずに、あるべきでない場所にインデックスを格納してもメモリが許容してくれると仮定して、先に進むこともできます。しかし、これは文字列を32ビットのメモリに収められる限りにおいてのみ有効です（32ビット整数と仮定します）。これはたった16文字です（16 > log(5,000,000)はひとまず無視しましょう）。

著者の一人による別の論文では、まったく正確な説明がなされていませんが、MSLのランタイムをサブリニアとしていますが、これは全くの誤りです。

おさらいすると : DNA文字列で動作するインプレース基数ソートの実用的な実装、または少なくとも良い擬似コード/記述を見つける希望はありますか？

どのように解決するのですか？

さて、ここではDNAのためのMSD基数ソートの簡単な実装を紹介します。 D言語で書かれているのは、私が最もよく使う言語であり、したがって愚かな間違いを犯す可能性が最も低いからですが、他の言語に簡単に翻訳することもできます。 これはインプレースですが 2 * seq.length は配列を通過します。

void radixSort(string[] seqs, size_t base = 0) {
    if(seqs.length == 0)
        return;

    size_t TPos = seqs.length, APos = 0;
    size_t i = 0;
    while(i < TPos) {
        if(seqs[i][base] == 'A') {
             swap(seqs[i], seqs[APos++]);
             i++;
        }
        else if(seqs[i][base] == 'T') {
            swap(seqs[i], seqs[--TPos]);
        } else i++;
    }

    i = APos;
    size_t CPos = APos;
    while(i < TPos) {
        if(seqs[i][base] == 'C') {
            swap(seqs[i], seqs[CPos++]);
        }
        i++;
    }
    if(base < seqs[0].length - 1) {
        radixSort(seqs[0..APos], base + 1);
        radixSort(seqs[APos..CPos], base + 1);
        radixSort(seqs[CPos..TPos], base + 1);
        radixSort(seqs[TPos..seqs.length], base + 1);
   }
}

明らかに、これは一般的なものとは対照的に、DNAに特化したものですが、高速であるべきです。

編集する

このコードが本当に動くのか気になったので、自分のバイオインフォマティクスコードの実行を待つ間、テスト/デバッグしてみました。 現在、上のバージョンは実際にテストして動作しています。 5塩基の配列が1000万個ある場合、最適化されたイントロソートよりも3倍くらい速いです。