問題タブ [radix-sort]

先日、Javaで基数ソートの実装を作成することにしました。基数ソートは O(k*N) であるはずですが、各桁を 1 つの数値に分解するプロセスのために、最終的に O(k^2*N) になりました。前の数字を修正 (%) し、10 で割って後続の数字を削除することで、各数字を分解しました。これを行うためのより効率的な方法があるかどうか教授に尋ねると、彼はビット演算子を使用すると言いました。さて、私の質問は次のとおりです。Javaで各数値を分解するのに最も速い方法はどれですか。1）上記の方法。2) 数値を文字列に変換し、部分文字列を使用します。3) ビット操作を使用します。

3）の場合、それはどのように機能しますか？

これは長文です。我慢してください。要約すると、問題は次のとおりです。実行可能なインプレース基数ソートアルゴリズムはありますか?

予備

文字「A」、「C」、「G」、「T」のみを使用する小さな固定長の文字列が大量にあり(そう、ご想像のとおり: DNA )、それらを並べ替えます。

現時点では、 STLのすべての一般的な実装で、std::sortwhich uses introsortを使用しています。これは非常にうまく機能します。しかし、基数ソートは問題セットに完全に適合し、実際にははるかにうまく機能するはずだと確信しています。

詳細

私はこの仮定を非常に単純な実装でテストしましたが、比較的小さな入力 (10,000 のオーダー) の場合、これは真実でした (まあ、少なくとも 2 倍以上高速でした)。ただし、問題のサイズが大きくなると ( N > 5,000,000)、実行時間は大幅に低下します。

その理由は明らかです。基数ソートでは、データ全体をコピーする必要があります (実際には、私の単純な実装では複数回)。これは、メイン メモリに最大 4 GiB を入れたことを意味し、明らかにパフォーマンスが低下します。そうでなかったとしても、実際には問題のサイズがさらに大きくなるため、これほど多くのメモリを使用する余裕はありません。

ユースケース

理想的には、このアルゴリズムは、DNA と DNA5 (追加のワイルドカード文字「N」を許可する)、またはIUPAC 曖昧コードを含む DNA (結果として 16 の異なる値) に対して、2 から 100 の間の任意の文字列長で動作する必要があります。ただし、これらすべてのケースをカバーすることはできないことを認識しているため、速度が向上したことに満足しています。コードは、どのアルゴリズムにディスパッチするかを動的に決定できます。

リサーチ

残念ながら、基数ソートに関するウィキペディアの記事は役に立ちません。インプレース バリアントに関するセクションは完全にゴミです。基数ソートに関するNIST-DADS セクションはほとんど存在しません。アルゴリズム「MSL」を説明するEfficient Adaptive In-Place Radix Sortingという有望な論文があります。残念ながら、この論文も残念です。

具体的には、次のようなものがあります。

まず、アルゴリズムにはいくつかの誤りがあり、多くのことが説明されていません。特に、再帰呼び出しについては詳しく説明していません (現在のシフト値とマスク値を計算するために、ポインターをインクリメントまたは削減すると仮定しています)。また、関数dest_groupanddest_addressを定義せずに使用します。これらを効率的に実装する方法がわかりません (つまり、O(1) では、少なくともdest_address自明ではありません)。

最後になりましたが、このアルゴリズムは、配列インデックスを入力配列内の要素と交換することにより、インプレース性を実現します。これは明らかに数値配列でのみ機能します。文字列で使用する必要があります。もちろん、強力な型付けを台無しにして、インデックスが属していない場所にインデックスを格納することをメモリが許容できると仮定して先に進むこともできます。しかし、これは、文字列を 32 ビットのメモリに圧縮できる場合にのみ機能します (32 ビット整数を想定)。それはわずか 16 文字です (16 > log(5,000,000) であることは今のところ無視しましょう)。

著者の 1 人による別の論文では、正確な説明がまったく提供されていませんが、MSL のランタイムがサブリニアであり、完全に間違っています。

要約すると、動作する参照実装、または少なくとも DNA 文字列で動作する動作中の基数ソートの適切な疑似コード/説明を見つける希望はありますか?

整数または浮動小数点数の大きな配列がある場合、(C での) 並べ替えに適したアルゴリズム/実装は何ですか?

編集には少し遅れています...しかし、私は正確さとスピードを探しています。

1 から 10^6 までの数を大量に取るプログラムを作成して、C++ を改善しようとしています。各パスで数値を格納するバケットは、ノードの配列です (ノードは、値と次のノード属性を含む作成した構造体です)。

最下位の値に従って数値をバケットに並べ替えた後、1 つのバケットの末尾が別のバケットの先頭を指すようにします (順序を乱すことなく格納されている数値をすばやく取得できるようにするため)。私のコードにはエラー (コンパイルまたは実行時) はありませんが、残りの 6 回の繰り返しを解決する方法に関して壁にぶつかりました (数値の範囲を知っているため)。

私が抱えている問題は、最初に数値が int 配列の形式で radixSort 関数に提供されたことです。並べ替えの最初の繰り返しの後、数値は構造体の配列に格納されます。コードを作り直して、7回の反復でforループを1つだけにする方法はありますか?または、1回実行されるforループが1つ必要で、その下に6回実行されてから完全にソートされたものを返す別のループが必要ですか?リスト？

できればウイルス以外のオープン ソース ライセンスを使用する

いらっしゃいませ。配列を使用して通過する基数ソート方法がありますが、空のキューに格納する別の配列 (ビン) が必要です。ビンのキューを作成する方法について混乱しています。呼び出されたときに各桁の場所を見つける findPlace メソッドもあります。それで、ここに私が得たものがあります。誰かが私が欠けているものを見つけるのを手伝ってくれますか? お時間をいただきありがとうございます。

バケットを見つける方法も作成しました。それで、それを配列に入れる方法を知る必要があります。これを行うだけですか? part.add(getPlace(x, 場所));?

基数ソートを使用できるようにするためのデータの制約は何ですか？

整数の大きなリストをソートする場合、基数ソートを使用するのが適切でしょうか？基数ソートがこれ以上使用されないのはなぜですか？

float 型のフィールドを持つデータ構造があります。これらの構造体のコレクションは、float の値でソートする必要があります。これには基数ソートの実装がありますか。

そうでない場合、指数、符号、および仮数にアクセスする高速な方法はありますか。浮動小数点数を最初に仮数部、指数部、および前回の指数部でソートした場合。フロートを O(n) で並べ替えます。

基数ソートアルゴリズムで使用する n 桁の int から個々の桁を取得する最良の方法は何ですか? C/C++でそれを行うための特に良い方法があるかどうか疑問に思っています.一般的な最善の解決策は何ですか?

編集：明確にするために、文字列に変換して数字の配列のように扱う以外の解決策を探していました。

ソートアルゴリズムに関する試験に向けて勉強中です。友人が LSD 基数ソートに関するこのコードを教えてくれましたが、なぜ彼が 96、97、64 という数字を使用しているのか理解できません。LSD 基数ソートについていくつか読んだことがありますが、その仕組みがわかりませんでした。