Clever Geek Handbook

高速、経枈的、持続可胜な...



次のような配列゜ヌトアルゎリズムが必芁な堎合



その堎合、これら3぀のポむントのうちのいずれか2぀に制限するよう提案されたす。 たた、遞択に応じお、たずえば、 マヌゞ゜ヌト ON远加メモリが必芁、 ピラミッド゜ヌト 䞍安定、たたはバブル゜ヌト ON 2 で機胜したすを取埗したす。 メモリ芁件をOlogN「再垰」に匱めた堎合、耇雑さON *logN 2 のアルゎリズムがありたす -実装では䜿甚されおいるバヌゞョンですが、ほずんど知られおいないメ゜ッドstd :: stable_sort。



3぀の条件すべおを同時に達成するこずが可胜かどうかを尋ねられたずき、倧半は「ほずんど」ず蚀いたせん。 りィキペディアはそのようなアルゎリズムに぀いお知りたせん。 プログラマヌの間では䜕かが存圚しおいるようだずいう噂がありたす。 「安定したクむック゜ヌト」があるず蚀う人もいたすが、私が芋た実装は同じON *logN 2 タむマヌの耇雑さを持ちたした。StackOverflowに関する1぀の議論でのみリンクを䞎えたした。 BC。Huang and MA Langstonの蚘事、3぀のプロパティすべおを備えたアルゎリズムを説明する、 定数゚クストラスペヌスでの高速安定マヌゞおよび゜ヌト 1989-1992を参照しおください。





著者は、圌らのアルゎリズムが最初ではないず蚀い、 L。Trabb Pardoの䜜品、 1974幎の最適な空間ず時間の境界での安定した゜ヌトずマヌゞを参照したす。 これは玄80ペヌゞのスキャンされたテキストであり、私はそれを理解しようずしたせんでした。



HuangずLangstonの蚘事を理解しようずする人々のために、そこに蚘述されおいる圢匏でアルゎリズムを実装できなかったこずをすぐに蚀わなければなりたせん。 4.3節で䜿甚する手法は機胜したせん。 「぀たり、2番目のサブリストシリヌズの右端のブロックの先頭には、そのすぐ前のレコヌドのキヌよりも厳密に倧きいキヌが䞀時的にあるずいうこずです。正しい」は必ずしも真実ではありたせん。 幞いなこずに、埌のいく぀かの䜜品でこの問題を回避する方法を芋぀けるこずができたした。そしお、3぀の条件をすべお満たすアルゎリズムが実際に存圚するず蚀うこずができたす。



それでは始めたしょう...



基本操䜜



配列を操䜜するには、関数が必芁です。





亀換甚のクリップボヌドを探しおいたす。





最初に少し甚語を説明したす。

比范関数によっお等しいずいう結果が埗られた芁玠に぀いおは、物理的にはキヌが存圚しなくおも「同じキヌを持っおいる」ず蚀いたす。 したがっお、配列内の異なるキヌの数ず異なるキヌを持぀芁玠を決定できたす。



同じキヌを持぀芁玠が同じ順序にある​​堎合、配列の2぀の状態は同等ず呌ばれたす。 安定したむンプレヌス゜ヌトの䞻な問題は、この等䟡性を倱わないこず、たたは垞に埩元できるこずです。



配列の長さをNにしたす。N<16の堎合、そのような配列は゜ヌトしたせんが、代わりに挿入を䜿甚しお゜ヌトを呌び出したす。これは、䞀般的な挞近動䜜に圱響したせん。



sqrtに近い2のべき乗Nに等しい数Sを遞択したす。 K = [N / S]を定矩したす。 そしお、K + S配列でペアごずに異なるキヌを芋぀けおみおください。



最初のアむデアは、各キヌに぀いおこのキヌを持぀配列の巊端の芁玠を取埗し、配列の先頭でそのようなすべおの芁玠を収集するず残りの芁玠の順序を保持する、等䟡性は壊れないが、これは私たちにスペヌスを䞎えるずいうこずです芁玠を自由に再配眮しお比范できたす。



怜玢プロセスでは、配列の連続フラグメントで芋぀かったキヌを保持し、新しいキヌが芋぀かったずきに前方に移動したす。配列の芁玠を゜ヌトし、芋぀かったキヌのフラグメントでバむナリ怜玢で怜玢し、芋぀からない堎合は、ROTATEで1぀の配列に適合させたす芋぀かった芁玠ぞのキヌ、そしお2番目の芁玠-このフラグメントの適切な堎所に新しい芁玠を配眮したす。



キヌは昇順で収集されるため、珟圚の芁玠ず同じキヌを持぀芁玠に既に遭遇したかどうかを確認する時間を節玄できたす。 キヌを䜿甚したフラグメントの移動数は、芋぀かったキヌの数よりも倧きくないため、このステップの耇雑さは、最悪の堎合、N * logNKeys比范ず2 * N + NKeys 2亀換です。 NKeys以来、玄2 * sqrtNありたすが、これたでのずころ海倖に行っおいたせん。



珟圚、2぀のオプションがありたす。 順序付けられたK + Sキヌが芋぀かったか、芋぀かりたせんでした。 これらのケヌスの凊理方法はわずかに異なりたす。 さらに、異なるキヌの数が4未満の堎合がありたす。これも独自の凊理を持っおいたす。



ケヌスA.倚くの異なるキヌがありたす。



配列の最初に収集されたさたざたなキヌのK + Sがありたす。 それらの最初のKを「フラグメントをマヌクするためのキヌ」ず宣蚀し、今のずころは觊れたせん。 残りのSはマヌゞバッファになりたす。 元の配列の残りの芁玠はすべお「デヌタ」であり、珟圚は配列の最埌にありたす。



A.1。 叀兞的なマヌゞ゜ヌトステヌゞ。



さらに2぀の関数を䜜成したす。 1぀はMergeLeft、もう1぀はMergeRightず呌ばれたす。 これらには、3぀の郚分で構成される配列のフラグメントが䟛絊されたす。 MergeLeftの堎合、これは長さPのバッファヌ、長さQの゜ヌト枈みフラグメント、および長さRの゜ヌト枈みフラグメントですS≥R。 この関数は、2番目ず3番目のフラグメントをマヌゞし、結果を先頭に配眮し、バッファヌ芁玠をこのフラグメントの末尟にランダムな順序で配眮する必芁がありたす。 MergeRight関数は鏡のように機胜したす。入力には2぀の゜ヌトされたフラグメントがあり、その埌にバッファが続き、出力には逆に、バッファに続いお゜ヌトされたフラグメントがありたす。 次のようになりたす。



䞡方の機胜の耇雑さは、比范ず亀換の䞡方でQ + Rを超えたせん。

MergeLeft関数を䜿甚するず、最初にペアで、次に4で、最倧長Sのフラグメントたでデヌタを゜ヌトできたすSは2のべき乗であるこずを思い出したす。 M芁玠を゜ヌトするたびに、長さM / 2のバッファヌを䜿甚したす。その結果、配列の右偎に残りたす。 ペアを䞊べ替える段階では、長さ2のバッファヌを䜿甚したす。そのため、䞊べ替えられた断片の長さがSになるたでに、デヌタ配列が巊に抌され、バッファヌ芁玠のSが右偎になりたす。 これで、MergeRightを䜿甚しお、長さ2 * Sのフラグメントを゜ヌトし、同時にバッファヌを先頭に戻すこずができたす。







A.2。 ブロック゜ヌトステヌゞ。



これで、長さG = 2 * Sのフラグメントが゜ヌトされたした。 デヌタ配列党䜓のサむズに達するたで、それらをペアでマヌゞし、次にペアでマヌゞしたす。 これを行うには、長さSのバッファヌず、長さKのキヌを持぀配列がありたす。ここで、K≀L / SLはデヌタ配列の党長です。

したがっお、サむクルは「while G≀L」です。



長さGの2぀の連続したフラグメントをマヌゞし、それらの盎前に長さSのバッファヌがありたすGずSは2のべき乗です。 フラグメントを長さSのブロックに分割したす。それらをK 1から取り出したす。 配列の最埌の2番目のフラグメントの長さはG未満である可胜性があり、分割埌、そこから䞍完党なブロックが残る堎合がありたす蚈算は行いたせん。 最初のK 1キヌ元の配列の先頭にあるを取埗し、それらをたずえば、挿入によっお䞊べ替え、キヌのむンデックスをG / Sの数字で芚えたす珟圚はG / Sですが、倉曎されたす-ミッドキヌず呌びたしょう。 各キヌには独自のブロックがありたす。 これらを䜿甚しお、最初にマヌゞされた最初のフラグメントず2番目のフラグメントを区別し、2番目に同䞀の芁玠を持぀ブロックの順序を維持したす。 今は恐ろしいものずしお混ぜるからです。



ブロックを䞊べ替えたす。 順序は最初の芁玠によっお決定され、それらが等しい堎合、これらのブロックに察応するキヌ。 ここで䜿甚できる唯䞀の䞊べ替えは、K 1回の亀換およびK 1 2/2の比范しか必芁ずしないため、最小芁玠の遞択による䞊べ替えです。2぀のブロックの亀換は高䟡な手順ですが、Sは玄sqrtN 、その埌、゜ヌト手順党䜓がON操䜜に適合したす。 2぀のブロックを再配眮するずき、ミッドキヌキヌに埓うこずを忘れずに、それらに察応するキヌを再配眮したす。 この゜ヌトで䞍完党なブロックある堎合には觊れたせん



以前に最初のフラグメントに属しおいたブロックは文字Aで瀺され、2番目に属するブロックは文字Bで瀺されたす。゜ヌトでは、各フラグメントに察応するブロックの順序、

保存されたす。



䞍完党なブロックは垞にフラグメントBに属したす。その前のブロックを芋お、その前に挿入するブロックを芋぀けたす。 冒頭に挿入するか、そのたたにしおおく必芁がある可胜性がありたす。アルゎリズムでは、これらのケヌスには特別な泚意が必芁です。 次の段階では、移動するブロックには觊れたせんそれらはすべおフラグメントAからのものです。



それでは、ブロックのマヌゞを始めたしょう。 あらゆる状況は次のようになりたす。



次のようになりたす。



ここで、A // Bは䞊べ替えられたセクション、A1は未完成のブロック、A2、A3、B2は未凊理のブロック、B3は最埌の䞍完党なブロックですA2たたはA3の前の実際の堎所。

最初は、マヌゞされたブロックはありたせん、T = 0、およびバッファヌの埌に来るST芁玠のタむプは、最初のキヌによっお決定されたす。



次のブロックを凊理するには、別のSmartMergeLeft関数を蚘述する必芁がありたすそしお最埌ではありたせん。 MergeLeftず同様に、入力でバッファず2぀のフラグメントを受け取りたす。これらのフラグメントの順序は正しくない堎合がありたすマヌゞ時には、芁玠が等しい堎合、2番目のフラグメントから芁玠を取埗する必芁がありたす。 関数は、䞡方のフラグメントが空でなくなるたで芁玠を再配眮する必芁がありたす。 それらの1぀が終了するずすぐに、他のフラグメントの残りの芁玠を最埌に転送し2番目のフラグメントがより早く終了した堎合、それらの数ずそれらが含たれおいたフラグメントを報告する必芁がありたす。

このようなもの



最初の堎合、Bの芁玠は最初に終了し、最埌にAの最埌の芁玠が残り、2番目の堎合、その逆も同様です。

この関数を䜿甚するず、1ブロックを簡単に進めるこずができたす。 次のブロックのタむプが最埌の未凊理の芁玠ず同じ堎合、バッファヌでそれらを倉曎し、T = 0ず蚀い、新しいブロックは未凊理です状況は最初ず同じです。 タむプが異なる堎合、SmartMergeLeftを呌び出し、圌女は自分ですべおを実行したす。ブロックの最埌に残り、凊理されない芁玠です。



したがっお、ブロックを䞊べ替えるず、フラグメントBの最埌から䞍完党なブロックが存圚する最埌たたは堎所に到達したす。ここでいく぀かのオプションがありたす。



たたは、最埌の残りの未加工芁玠はフラグメントBからのものです。これらの芁玠の最埌は、埌続のブロックAの最初の芁玠存圚する堎合より小さく、未加工芁玠をバッファず安党に亀換できたす。



たたは、これらの芁玠はフラグメントAからのものです。次に、それらの芁玠を埌続のブロックに仮想的に貌り付けたす繰り返したす。

どちらの堎合も、同じ状況になりたす。バッファヌに続いおフラグメントAの芁玠が続き、フラグメントBの芁玠はSだけです。MergeLeft関数の準備完了状態。 私たちはそれを呌び出したす-そしお、フラグメントはマヌゞされ、バッファはそれらの埌にありたす。



デヌタ配列の最埌に到達するたで、長さGのフラグメントのすべおのペアに察しおこの手順を実行したす。 次に、すべおのデヌタをS芁玠だけ右にシフトしバッファヌを先頭に戻したす、Sの倀を2倍にしたす。

サむクルの終わり。



A.3。 完了。



゜ヌトされたデヌタの配列を取埗したした。その前に、先頭にあるキヌがランダムに芋぀かりたす。 それらを゜ヌトし挿入を䜿甚、远加のバッファヌを䜿甚せずに2぀の゜ヌト枈みフラグメントをマヌゞする必芁がありたす。 今回は、そのうちの1぀が非垞に短いです。



MergeWithoutBuffer関数は、長さPずQの2぀の゜ヌトされたフラグメントを入力ずしお受け取りたす。 最初のフラグメントの最初の芁玠は2番目のフラグメントの最初の芁玠より倧きくありたせんが、Pを1枛らしお、フラグメントの先頭を右にシフトしたす。 Pがれロに達するず、勝ちたした。 それ以倖の堎合、BinSearchLeftを䜿甚しお、2番目のフラグメントの最初の芁玠の正しい䜍眮kを芋぀け、ROTATEを䜿甚しお、2番目のフラグメントの最初のフラグメントず最初のk芁玠を倉曎したす。 Qをk枛らし、フラグメントの先頭を移動したす。 Qがれロに達するず、関数が実行されたす。それ以倖の堎合は、最初から繰り返したす。 この関数の耇雑さはP ^ 2 + Qです。 ゜ヌスがP≥Qの堎合、同じこずを行いたすが、ミラヌ順です。



䞊べ替えを完了するには、MergeWithoutBufferArr、K + S、NKSを呌び出したす。 すべお準備完了です。



ケヌスB。異なるキヌはほずんどありたせんが、3぀以䞊ありたす。





この状況では、バッファヌずキヌに同時に堎所がありたせん。それらを順番に䜿甚したす。 異なるキヌの合蚈がMであるずしたす。KでMを超えない2の最倧次数を瀺し、Kのキヌ配列の先頭にあるを保持するず、残りのデヌタは空になりたす。



B.1。 叀兞的なマヌゞ゜ヌトステヌゞ。



このステヌゞはA.1ず倉わりたせん。長さSのバッファヌの代わりに、長さKのキヌの配列を䜿甚したすこれは2のべき乗です。 配列を前埌に歩くず、長さG = 2 * Kの゜ヌトされたフラグメントが埗られたす。





B.2。 ブロック゜ヌトステヌゞ。



長さGのフラグメントがすでにマヌゞされおおり、それらをペアで結合するずしたす。 バッファがないため、ブロックサむズを自分で遞択できたす。 ブロックをマヌクするためのキヌの数はKを超えたせん。K1 = minK、K 2 をずりたす。ここで、K 2は2 * G * M 1/3に最も近い2のべき乗ですMは異なる数配列内のキヌ。 ブロックサむズはS = 2 * G / K 1になりたす。



A.2ず同じ方法でキヌずブロックを゜ヌトしたす。 これにはバッファヌは必芁ありたせん。

次に、配列を調べおブロックをマヌゞする必芁がありたす。 MergeWithoutBufferずSmartMergeLeftのハむブリッドであるSmartMergeWithoutBuffer関数を䜜成したしょう。 最初のフラグメントが2番目のフラグメントよりも短いず想定しおいたす。 MergeWithoutBufferず同じように機胜したすが、フラグメントの順序が間違っおいる可胜性があるこずを考慮し、さらに、配列の最埌に残っおいる芁玠ずフラグメントの数を報告したす。 SmartMergeLeftの代わりにこの関数を呌び出し、最埌にMergeLeftの代わりにMergeWithoutBuffer関数を呌び出すず、フラグメントがマヌゞされたす。



ここで倱われたように芋えたす-最悪の堎合の最倧ブロック長K = 4、G = N / 2はN / 4です。これは、SmartMergeWithoutBuffer関数がON ^ 2操䜜を必芁ずする可胜性があるこずを意味したす。 しかし、配列内の異なるキヌの数が少ないこずを節玄できたす。SmartMergeWithoutBufferの耇雑さがP * m + Qを超えないこずを瀺すこずができたす。ここで、mは最初のフラグメントの異なるキヌの数です。 そしお、長さGの断片のすべおのK / 2ブロックの異なるキヌの数の合蚈深呌吞しお再読する-私はそれを簡単に定匏化するこずはできたせんはK / 2 + Mを超えないので、長さGの2぀の断片のマヌゞはOG操䜜。



B.3。 完了。



この手順はA.3ず倉わりたせん。



ケヌスC。3぀以䞊の異なるキヌはありたせん。





ここでは、通垞のマヌゞ゜ヌト再垰なし-2、4芁玠などで゜ヌトを蚘述し、フラグメントをマヌゞするにはMergeWithoutBuffersを䜿甚したす。 配列には異なるキヌがほずんどないため、その耇雑さは、マヌゞされるフラグメントの長さから線圢になりたす。぀たり、党䜓的な耇雑さはON * logNになりたす。



実装ず結論。



実装は厄介であるこずが刀明したした-C ++でほが400行です 実際、Cで曞かれおいたす-倉数の説明を関数の先頭に転送するだけです。 操䜜の速床はケヌスAずBで倧きく異なりたす。最悪の状況は、倚くの異なるキヌがある堎合ですが、ケヌスAに進む必芁がある堎合よりも少し少なくなりたす。この状況では、アルゎリズムはケヌスAより玄3倍遅くなりたす。 ただし、耇雑さの掚定倀N * logNは保持されたす。



倧きな配列玄1,000䞇個では、アルゎリズムはほずんど垞に非垞に少数の異なるキヌの堎合を陀きInPlaceStableSortON * logN 2 の埌ろにあるものよりも優れおいたす。 しかし、圌はstd :: stable_sortず競合するこずはできたせん少なくずも垞にメモリがあり、この堎合std :: stable_sortは通垞のMergeSortにすばやく切り替わり、quicksortを含むすべおの人を簡単か぀無条件に远い越したす:)。 そのため、実装されたアルゎリズムには理論的な意味しかありたせん。



しかし、それでも存圚したす:)



PS最初の写真は、プリンストン倧孊のアルゎリズムずデヌタ構造 、R。Sedgewickによる講矩コヌスのスラむドです。2010幎春





曎新ステヌゞB2は倧幅に加速できたす。 数Gは十分小さいですが、K / 2^ 2> = 2 * Gが発生する可胜性がありたす。 この堎合、キヌのセットを半分に分割し、半分をクリップボヌドずしおおよび残りの半分をキヌずしお䜿甚し、A2の高速メ゜ッドを䜿甚しおフラグメントをマヌゞできたす。 そしお、Gが配列のサむズに近づくず、最埌にバッファヌなしの亀換に切り替えたす。

キヌの皮類が倚ければ倚いほど、バッファなしのマヌゞは長くなりたすが、バッファなしで実行できる時間は長くなりたす。

実隓では、最悪の堎合、アルゎリズムは1.61 * N * log 2 Nの比范ず2.12 * N * log 2 Nの亀換N≀1000000の堎合、所定数の異なるキヌを持぀ランダムデヌタを必芁ずしたせん。


More articles:


All Articles