14

私はSedgewick&Wayneによる「Algorithms、4th Ed」を読んでおり、その過程でJavaScriptで説明されているアルゴリズムを実装してきました。

私は最近、本で提供されているマージソートの例を使用して、トップダウンとボトムアップのアプローチを比較しました...しかし、ボトムアップの方が高速であることがわかりました(私は思います)。私のブログで私の分析を参照してください。-http ://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/

マージソートの一方の方法がもう一方の方法よりも高速である必要があるという議論を見つけることができませんでした。私の実装(または分析)に欠陥がありますか?

注:私の分析では、厳密には配列の比較/移動ではなく、アルゴリズムの反復ループを測定します。おそらくこれは欠陥があるか、無関係ですか?

編集:私の分析は実際には速度の時間を計っていなかったので、それが「より速く」実行されているという私の声明は少し誤解を招きます。私は再帰的方法(トップダウン)とforループ(ボトムアップ)を介して「反復」を追跡しています-そしてボトムアップはより少ない反復を使用しているように見えます。

4

3 に答える 3

17

マージソートの 1 つの方法が他の方法よりも高速であるべきだという議論を見つけることができませんでした。

ボトムアップとトップダウンのマージソート、およびその他のバリアントは、90 年代によく研究されてきました。簡単に言えば、個々のキーの比較回数としてコストを測定すると、最良のコストは同じ (~ (n lg n)/2)、トップダウンの最悪のコストは最悪のコスト以下です。ボトムアップのケース (ただし ~ n lg n の両方) およびトップダウンの平均コストは、ボトムアップの平均ケース (ただし両方 ~ n lg n) 以下です。ここで、「lg n」はバイナリ対数。違いは線形項に由来します。もちろん、n=2^p の場合、2 つのバリアントは実際にはまったく同じです。つまり、比較に関しては、トップダウンは常にボトムアップよりも優れています。さらに、トップダウン マージ ソートの「半々」分割戦略が最適であることが証明されています。研究論文は、Flajolet、Golin、Panny、

以下は、Erlang で書かれた著書Design and Analysis of Purely Functional Programs (College Publications、英国) で思いついたことです。

tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T)           -> T.

cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S,    T,      U) -> mrg(tms(S),tms(T)).

mrg(     [],    T)            -> T;
mrg(      S,   [])            -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg(  [X|S],    T)            -> [X|mrg(S,T)].

これは安定ソートではないことに注意してください。また、Erlang (および OCaml) では、メモリを節約したい場合、パターンでエイリアス(ALIAS=...) を使用する必要があります。ここでの秘訣は、リストの長さを知らずにリストの真ん中を見つけることです。これは、入力リストへの 2 つのポインターを処理する cutr/3 によって行われます。1 つは 1 ずつインクリメントされ、もう 1 つは 2 ずつインクリメントされます。したがって、2 番目が最後に到達すると、最初の 1 つは中間になります。(これは Olivier Danvy の論文から学びました。) この方法では、長さを追跡する必要がなく、リストの後半のセルを複製しないので、(1/2 )n lg n 余分なスペース、対 n lg n。これはあまり知られていません。

関数型言語や連結リスト (Knuth、Panny、Prodinger) にはボトムアップのバリアントが望ましいとよく言われますが、これは真実ではないと思います。

私はあなたと同じように、マージソートに関する議論が不足していることに困惑していたので、独自の調査を行い、それについて大きな章を書きました。現在、マージソートに関する資料を追加した新版を準備中です。

ところで、キュー マージ ソートやオンライン マージ ソートなど、他にもバリエーションがあります (後者については私の著書で説明しています)。

[編集: コストの尺度は比較の数であるため、配列とリンク リストの選択に違いはありません。もちろん、リンクされたリストを使用してトップダウンのバリアントを実装する場合は、キーの数を必ずしも知っているとは限らないため、賢くする必要がありますが、毎回少なくとも半分のキーをトラバースする必要があります。合計で (1/2)n lg n セルを再割り当てします (賢い場合)。リンクされたリストを使用したボトムアップ マージ ソートは、実際には追加のメモリ (n lg n + n セル) を必要とします。したがって、リンクされたリストであっても、トップダウンのバリアントが最良の選択です。プログラムの長さに関しては、マイレージはさまざまですが、関数型言語では、安定性が必要ない場合は、トップダウン マージ ソートをボトムアップ マージ ソートよりも短くすることができます。マージソートの実装の問題を議論する論文がいくつかあります。Katajinen と Larsson Traff (1997 年) によるMergesort プログラムの綿密な分析]

于 2012-09-09T10:11:23.587 に答える
4

より速いということは、より少ない「反復」を意味する場合は、そうです。実行時間について疑問がある場合は、おそらく。

その理由は、これらの 21,513 回の反復の一部が 22,527 回の反復より多く実行しているためです。

ソースを見ると、ダイアグラム内のリーフ ノードの一部が個別にソートされているのではなく、マージとソートの回数が減っているように見えますが、時間がかかります。

于 2012-04-14T13:24:52.440 に答える