問題タブ [bucket-sort]

アメリカン バケット ソートを実装しようとしています。Wiki には、「まず各ビンに入るオブジェクトの数を数え、次に各オブジェクトをバケットに入れる」と書かれています。

第 2 段階では、オブジェクトを適切なバケットに配置するときに、補助配列を使用する必要がありますか? 線形時間で配列要素を交換することでこれを行う方法はありますか?

Bucket sortに関するウィキペディアのページを読みました。この記事では、最悪の場合の複雑さは O(n²) であると述べています。しかし、最悪の場合の複雑さは O(n + k) で、k はバケットの数だと思いました。これは、この複雑さを計算する方法です。

1. 要素をバケットに追加します。リンクされたリストを使用すると、これは O(1) です
2. リストを調べて、要素を正しいバケットに入れる = O(n)
3. バケットのマージ = O(k)
4. O(1) * O(n) + O(k) = O(n + k)

何か不足していますか？

パフォーマンスのためにクイックソートを最適化しようとしていました。4M (1<<22) の整数項目 (それぞれ 4 バイト) の場合、72 の同時スレッド (72 コア) をサポートできるシステムで並べ替えるには、並列クイックソート アルゴリズムで 0.5 (0.499703) 秒かかります。並列クイックソートをさらに最適化する効率的な方法を知りたいです。また、特定のワークロードが与えられた場合に、すべての並べ替えアルゴリズムのリーグ テーブルがある場合、他の並べ替えアルゴリズムと比較することに興味がありますか?

4 桁ごとに 7 つの数字をソートする必要がある場合、最悪の場合、何回の比較が必要になりますか?(基数ソート) オプションは 40、38、47、280 です。

私の解決策 - 10 個のバケット (0 から 9)(リンクされたリスト) を取得しました。次に、i 桁のすべての数値について、その桁の値に対応するバケットに入れました。次に、それらの数値を配列に集めました。このプロセスがすべての数字に対して繰り返されるため、元の配列がソートされます。比較の総数 = 10*4=40 (対応するバケットを探すためにすべてのバケットを繰り返し処理したため、10)。

ここでの問題は、Timothy J Williams の本にあります。比較の数 = 桁数 * 数の数 * バケットの数 = 4*7*10=280 です。私は理解することができません。誰かがこれがどのように来たのか説明してもらえますか.

基数、カウント、およびバケットソートの定義を読んでいますが、それらはすべて以下のコードにすぎないようです:

私は正しくないことを知っているので、何が欠けているのでしょうか? Java または C での説明に役立つと思われる場合は、コードを示してください。

4 つのデータ セットがあります (ここでご容赦ください)。

• 1 番目のテーブル: matlab の txt 形式の 1 つの列に 10 個のティッカー (株式シンボル) のリスト。
• 2 番目のテーブル: 1 つの列の数値形式の日付 (倍精度形式で 10 日)。
• 3 番目のテーブル: 乱数の 10*10 データ セットがあります (簡単にするために 0 ～ 1 と仮定します)。(たとえば、EPS の 1 株あたりの利益)--つまり、ポートフォリオを構築するために、ランキングで高い EPS の成長を望んでいます。
• 4 番目の表: 別の 10*10 の乱数のデータ セットがあります (簡単にするために 0 ～ 1 と仮定します)。（たとえば、毎日の価格対収益率）-ポートフォリオ構築のために、ランキングで低いP / E比が必要です。

今: 特定の日のテーブル 1 の 3 つの銘柄 (最大値) と、テーブル 2 の下位 3 つの銘柄 (最小値) で構成される銘柄のポートフォリオを毎日ランク付けしたいと考えています。出力は、2 つの要因の組み合わせランキング (表 3 と 4 で説明) に基づいて、日ごと (この場合は 3 つ) のティッカーのリストである必要があります。

何か案は？要するに、私は 3 つのティッカーを持つトップ バケットで終わる必要があります...

C++ でバケットソート アルゴリズムを作成しようとしていますが、まったく機能しません。実行するたびに、多数の新しい数値が配列に追加されます。多くの場合、数十億のような非常に大きな数値が配列に追加されます。これがなぜなのか誰か知っていますか？コードは次のとおりです-（サイズ100の配列を0から〜37000の乱数で渡していることに注意してください。挿入ソート機能は完全に機能し、複数回テストされています）

誰かが間違っていることを指摘できれば幸いです。

以下のコードでは、Bucket Sort の実装をベンチマークしています。

このbucketsort関数は からの結果を使用します_bucketsortが、単一のリストにフラット化します。驚いたことに、このプロセス ( Map.toList) にはかなりの時間がかかります。

Criterion によるベンチマークの出力は次のとおりです。

私のbucketsort関数がより良く、できればより速く記述できたとしても、私は驚かないでしょう。しかし、今のところ、私はその方法を理解していません。

また、Haskell コードの改善やコメントは大歓迎です。

Javaでバケットソートを実装していますが、入力配列がランダムではなく（昇順または降順で）ソートされると、ソート（昇順）が速くなることがわかりました。どうしてこれなの？私が理解しているように、配列を通過し、各要素のインデックスで「集計」配列をインクリメントします。ソートされた入力でなぜ高速になるのかはわかりませんが、約 2 倍高速になるようです。

ありがとう

次のアルゴリズムを調査しています。

1. カウントソート
2. 基数ソート
3. バケットソート

3 つすべてが最良の場合でも線形時間で実行できることはわかっていますが、並べ替えをカウントする場合を除いて、それらのケースがいつ発生するかを理解するのに苦労しています。

これがソートのカウントに関する私の理解であり、可能であれば他の2つのアルゴリズムに対する答えが欲しいです:

ソートしたい情報の間に大きなギャップがない場合、カウントソートは線形時間で実行されます。たとえば、1、10^5、および 545 などは大きな配列を作成し、メモリとトラバーサルを使用して効率的ではないため、これはカウントソートを使用する「最悪のケース」になります。ギャップは小さいです。

線形時間が発生したときの基数とバケットソートの最良のケースの条件を理解するのを手伝ってくれる人がいれば、私は感謝しています。