問題タブ [mergesort]

私は最近、いくつかの基本事項をブラッシュアップしていて、リンクリストのマージソートがかなり良い課題であることに気づきました。優れた実装がある場合は、ここでそれを披露してください。

面接でこんな質問をされました。どちらも O(nlogn) ですが、ほとんどの人は Mergesort の代わりに Quicksort を使用しています。何故ですか？

昨日、クイックソートの実装に取り​​組んでいましたが、マージソート (これも実装しました) よりも実行時間が速いことを期待して実行しました。私は2つを実行しました.100要素未満の小さなデータセットではクイックソートの方が高速でしたが（動作することを確認しました）、マージソートはかなり迅速なアルゴリズムになりました. クイックソートはほとんどの場合、マージソートよりも「速い」と教えられていました。このトピックについてはいくつかの議論があることを理解していますが、少なくともこれよりも近いと予想していました。10000 要素を超えるデータ セットの場合、マージソートは 4 倍以上高速でした。これは予想されることですか、それともクイックソート コードにエラーがありますか?

マージソート:

クイックソート:

O(n log n)のMergeSortだと思います。

ただし、次の出力は一致しません。

4 つのノードのノードリストをシーケンス番号で並べ替えています。並べ替えは 6 回の比較を行っています。6 > (4 log(4)) なので困惑しています。誰かが私にこれを説明できますか？

PSマージソートですが、まだ結果がわかりません。

回答ありがとうございます。トム、私の数学を訂正してくれてありがとう。

私はマージソート関数を書いていますが、今はテストケース配列を使用しています (入力はありません - これは今のところ静的です)。配列を引数として渡す方法がわかりません。ここに私のコードがあります：

この mergeSort 関数は機能しないことに注意してください。それらをマージする方法がまだわかっていないためです (それが私の課題です)。それを処理する前に 2 つのベクトルを並べ替えたいのですが、引数として配列を渡す必要があるため、これをコンパイルできません。私はポインターを理解していないので、それが解決策である場合、私の言い訳は無知です。私は現在、C++ を第一言語としてプログラミングを学んでおり、言語の機能の基本的な理解しかできていません。助けてくれてありがとう。

私はC++（第一言語として）を教えてくれている友人の指導で再帰関数を書きました。しかし、私は何が起こっているのか本当に理解していません。彼は私（そしてSOコミュニティも）がマージソート関数を書くのを手伝ってくれました。

この関数では、次を割り当てます。

ここで何が起こっているのですか？パラメータとしてfarrayとsarrayを使用してmergeSortを呼び出し、値を変更します。マージソートはどこまで再帰的に実行されますか？再帰関数呼び出しまで？

バックグラウンド：

大きな (メモリに保持できない) タブ区切りファイルをクリーニングしています。入力ファイルをクリーンアップすると、メモリ内にリストが作成されます。1,000,000 エントリ (メモリ内で約 1GB) に達したら、(以下のデフォルト キーを使用して) 並べ替え、リストをファイルに書き込みます。このクラスは、ソートされたファイルを元に戻すためのものです。これまでに遭遇したファイルで動作します。これまでのところ、私の最大のケースは、66 個のソートされたファイルをマージすることです。

質問:

1. 私のロジックに穴がありますか (壊れやすい場所はどこですか)?
2. マージソートアルゴリズムを正しく実装しましたか?
3. 明らかな改善点はありますか?

サンプルデータ:

これは、次のファイルの 1 つの行を抽象化したものです。

'hash_of_SomeStringId\tSome String Id\t\t\twww.somelink.com\t\tOtherData\t\n'

要点は'SomeStringId'.lower().replace(' ', '')、ソートキーとして使用することです。

元のコード:

編集：ブライアンからの提案を実装すると、次の解決策が思いつきました：

2 番目の編集: John Machinの提案に従ってコードを更新しました。

ラフテスト_

同じ入力ファイル (2.2 GB のデータ) を使用:

• SortedFileMerger クラスは 51 分 (3068.4 秒) かかりました
• Brianの解決には 40 分 (2408.5 秒) かかりました
• John Machinの提案を追加した後、ソリューション コードは 36 分 (2214.0 秒) かかりました

私は C++ プログラマーです。機能的に考えることができるかどうかを確認するためにこのコードを書きました :) 改善するためのヒントはありますか?

Python のマージ ソート アルゴリズムと思われるものを実装しました。これまで Python でプログラミングしたことがないので、理解を深めるために、なじみのないコマンドを含むいくつかのリソースを使用しました。

ただし、そもそもマージソートも実装したことがないため、正しく実装できているかどうかもわかりません。ガイダンス、ヒント、または修正は大歓迎です。

これが私のマージ方法です：

一方、これが私のmergesortメソッドです：

助けてくれてありがとう！:)

Haskell は初めてで、いくつかの既知のアルゴリズムを実装しようとしています。

文字列にマージソートを実装しました。C および Java の実装と比較して、私の Haskell 実装のパフォーマンスには少しがっかりしています。私のマシン (Ubuntu Linux、1.8 GHz) では、C (gcc 4.3.3) は 1 000 000 文字列を 1.85 秒、Java (Java SE 1.6.0_14) は 3.68 秒、Haskell (GHC 6.8.2) は 25.89 秒でソートします。より大きな入力 (10 000 000 文字列) では、C は 21.81 秒、Java は 59.68 秒かかり、Haskell はスワッピングを開始し、数分後にプログラムを停止することを好みました。

私は Haskell を初めて使用するので、実装をより時間/スペース効率的にできるかどうか知りたいです。

ヒントを事前にありがとうジョルジオ

私の実装: