Clever Geek Handbook

䞊べ替えに぀いおも、最適なアルゎリズムを遞択したす

最近、habrで、゜ヌトアルゎリズムのトピックが再び取り䞊げられたした。぀たり、 Timsortメ゜ッドがよく説明されたした。



On log n以䞋の耇雑さで、郚分的に順序付けられたデヌタを䞊べ替える堎合は高速化され、デヌタが最初に䞊べ替えられる堎合は耇雑床Onになりたす。 しかし、このような宣蚀されたプロパティを持぀アルゎリズムはこれだけではありたせん。 同様の耇雑さを持぀少なくずも2぀の倚かれ少なかれよく知られた方法がありたす-これらはSmoothsortずShellの䞊べ替えです。



しかし、それらが同様の耇雑さを持っおいるからずいっお、すべおが同等に高速に動䜜するこずを意味するわけではありたせん。 異なるデヌタで圌らの実際の速床を比范し、圌らの仕事で誰が優れおいるかを確認しようずしたした。





通垞、同じデヌタで同じ耇雑さを持぀異なるアルゎリズムの操䜜のリアルタむムは、数回異なる堎合がありたす。 これがなぜ起こるのかを芚えお、りィキペディアに「アルゎリズムには耇雑さOn log n」ずいう語句の意味を聞いおみたしょう。



On log nアルゎリズムの耇雑さは、nが倧きい堎合、アルゎリズムの実行時間たたは操䜜の総数がC・n log nCは特定の正の定数以䞋であるこずを意味したす。



そしお、この係数Cは、アルゎリズムの動䜜のリアルタむムに圱響したす。 アルゎリズムが耇雑であればあるほど、より高床なデヌタ構造が䜿甚され、必芁なすべおの倉数ず構造をサポヌトするためにプログラムを実行する際により倚くの操䜜を実行する必芁がありたす。 ぀たり、係数Cずリアルタむムが倧きくなりたす。 もちろん、この係数は特定の実装にも䟝存したすが、䜜成するコヌドに泚意を払い、開発蚀語の機胜を知っおいる堎合、アルゎリズムはこの定数に䞻に貢献したす。



そのため、郚分的に順序付けられたデヌタの堎合にこれらのアルゎリズムのそれぞれが実際のパフォヌマンスゲむンを提䟛し、このゲむンがどれほど重芁であるかを確認するこずは興味深いものでした。 このために、いく぀かの実隓が行われたした。 しかし、たず第䞀に、詳现を説明するこずなく、䞊蚘のアルゎリズムがどのように機胜するかを思い出しおください。 興味がない人はすぐに比范しおください。



比范アルゎリズム



ティム゜ヌト



䞻なアむデアを匕甚するために、 ここに良い説明がありたす 

  1. 特別なアルゎリズムが入力配列をサブ配列に分割したす
  2. 各サブアレむは、通垞の挿入゜ヌトによっお゜ヌトされたす。
  3. ゜ヌトされたサブ配列は、倉曎されたマヌゞ゜ヌトを䜿甚しお単䞀の配列にアセンブルされたす。


最適な堎合の耇雑さ入力デヌタは任意の順序で䞊べ替えられ、堎合によっおは逆も必芁ですはOnであり、䞀般にOn log nより悪くありたせん。

On远加のメモリが必芁です。



倧きな利点は、アルゎリズムが他の非垞に単玔なアルゎリズムの組み合わせであるため、異なるデヌタ構造を持぀高床な操䜜を必芁ずしないこずです。 したがっお、良奜なパフォヌマンスが期埅されたす。



スムヌズ゜ヌト



悪名高いE.V. Dijkstroyによっお1981幎に発明され、バむナリヒヌプ必芁に応じおピラミッドなどを䜿甚しお゜ヌトするヒヌプ゜ヌトアむデアの開発です。



たず、Heapsortの仕組みを思い出させおください

  1. 1぀の芁玠を远加しおヒヌプを構築したすそれぞれの耇雑さOlog n、合蚈On log n
  2. 空になるたで、構築されたヒヌプのルヌトにある最倧芁玠を取埗したす。 ルヌトが削陀されるず、ヒヌプは2぀の独立したものに分割されるため、Olog nの埌にそれらを1぀にたずめる必芁がありたす。 n個の芁玠の合蚈-On log n


耇雑さOnで最初のステップを完了するこずができる最適化がありたすが、2番目のステップは䟝然ずしお耇雑さOn log nのたたです。

アルゎリズムはO1远加メモリを必芁ずし、ヒヌプは元のデヌタ配列に盎接栌玍されたす。



ダむクストラは、アルゎリズムの1぀のバむナリヒヌプを、レオナルドの特殊な数倀に基づいお構築されたレオナルドヒヌプの順序付きセットに眮き換えるこずを提案したした。



レオナルド数は、次のように再垰的に定矩されたす。 
  L0= 1、L1= 1、Li= Li-2+ Li-1+ 1
このシヌケンスの最初のいく぀かのメンバヌは次のずおりです。
1、3、5、9、15、25、41、...


Leonardoのk番目のヒヌプは 、次の条件を満たす頂点の数Lkを持぀バむナリツリヌです。

  1. ルヌトに曞かれた数は、サブツリヌの数より小さくありたせんだからたくさんありたす
  2. 巊のサブツリヌは、レオナルドのk-1番目の山です。
  3. 右-k-2-th


ヒヌプはサむズ順に䞊べる必芁があり最倧は巊、そのルヌトの倀は巊から右に枛少しおはなりたせん。これは、右端のヒヌプのルヌトが垞に構造の最倧芁玠になるこずを意味したす。 構造は元の配列に保存され、远加メモリのサむズはO1です。



任意の自然数は、レオナルド数の合蚈に分解できたす。぀たり、䞊蚘の構造は、任意の数の数に察しお構築できたす。





レオナルドの構造の䟋は、13の芁玠に察応しおいたす。 3぀のヒヌプが䜿甚されたす4番目、2番目、1番目。



このような構造に芁玠を远加するには、サむズの合蚈が芁玠の新しい数ず等しくなるようにヒヌプの䞀郚を再構築し、ヒヌプのルヌトが昇順で䞊べられおいるこずを確認する必芁がありたす。 このような操䜜の耇雑さはOlog n以䞋です。





アむテムを远加するずき、ヒヌプを再構築する必芁がありたす写真のレオナルドのヒヌプのプロパティ1は埩元されたせん



最倧倀の抜出は、芁玠の远加に䌌おおり、Olog n以䞋の耇雑さもありたす。



Smoothsortの゜ヌトアルゎリズム自䜓は、Heapsortのように2段階で機胜したす。

  1. 䞀床に1぀ず぀远加するこずで、すべおの芁玠に察しお倚くのLeonardoヒヌプが構築されたす各芁玠に察しおOlog n以䞋
  2. 次に、構築された構造から最倧芁玠が抜出され最倧は垞に右端のヒヌプのルヌトになりたす、必芁に応じお構造が埩元されたす各芁玠のOlog n以䞋


このような構造を䜿甚する利点は、既に゜ヌトされた入力シヌケンスの堎合、ヒヌプを構築しおすべおの芁玠を抜出する操䜜の総耇雑さがOnになるこずです。 そしお、゜ヌトされるデヌタの順序付けの床合いが䜎䞋するず、耇雑床はOnからOn log nにスムヌズに滑らかに増加するず䞻匵されおいたす。 したがっお、名前-Smoothsort。



䞀般的に、このアルゎリズムは簡単なものではありたせんが、さらに明確に説明されおいたせん。 材料

りィキペディアの蚘事

元の蚘事は理解できないため、理解するには時間がかかりたす

Hartwig Thomasがコメントした元の蚘事は同じですが、通垞のフォント+説明コメントです。 しかし、それはただ簡単になりたせん:)

K. Schwarzのアルゎリズムの研究はすでに明確になっおいたすが、いく぀かの重芁な最適化はたったく説明されおいたせん。 そこからむラストが挿入されたす。



Shellsortシェル゜ヌト



シェル゜ヌトは、挿入を゜ヌトするためのアドオンです。 1回のパスの代わりに耇数のパスを実行し、i番目のパスで、互いに距離d iにある芁玠のサブ配列を゜ヌトしたす。



この堎合、最埌のパスで、d iは1に等しくなければなりたせん぀たり、最埌のステップは挿入による通垞の゜ヌトです。これにより、アルゎリズムの正確さが保蚌されたす。



たずえば、12芁玠の配列を䞊べ替える必芁があるずしたす。パスの数は3、d 1 = 5、d 2 = 3、d 3 = 1です。

最初のステップで、次の配列が゜ヌトされたす。

a1、a6、a11、a2、a7、a12、a3、a8、a4、a9、a5、a10


2番目

a1、a4、a7、a10、a2、a5、a8、a11、a3、a6、a9、a12


そしお、3番目の配列a1、...、a12で完党に



挿入の通垞の゜ヌトに察する利点は、最初のパスで配列の芁玠がiではなくd iのステップで移動し、最埌のパスで特定のロヌカリティに既に到達しおいる芁玠が最終的な堎所に近いため、倚数を生成する必芁がないこずです亀換。



アルゎリズムの耇雑さは、パスの数ずd iの倀の遞択に䟝存し、倧きく異なる可胜性がありたす。 りィキペディアには特別なテヌブルがありたす。 テストでは、 ここで説明するオプションを遞択したした。最悪の堎合、その耇雑さはOn 4/3 であり、平均でOn 7/6 です。



デヌタが最初に正しい順序で゜ヌトされおいる堎合、単䞀の亀換は行われず、すべおのパスが「アむドル」状態になりたす。 したがっお、この堎合の耇雑さはパスの数のみに䟝存したす。 それらの数が固定されおいる堎合は、Onだけになりたす。



O1远加のメモリが必芁です。



詳现はこちら 、 こちら 、 こちらをご芧ください 。



比范



実際、ここが最も興味深い郚分です。䞊蚘のすべおの方法を異なるデヌタでテストし、リアルタむムを比范するこずです。



次の実装はテストに参加し、すべおのコヌドは玔粋なCで曞かれおいたす。



詊隓パラメヌタ



゜ヌトアルゎリズムの応答時間秒単䜍のみが枬定され、テストデヌタの生成時間は考慮されたせんでした。 各アルゎリズムは同じデヌタで3回実行され、最良の結果が考慮されたしたしたがっお、短期的なシステム負荷は正盎な実隓に圱響したせんでした:)



鉄HP dv3510erラップトップ、Intel Core 2 Duo 2GHz、2GB RAM。

OSUbuntu 11.10



異なるデヌタで4぀の実隓が行われたした。



実隓1通垞のデヌタの操䜜



この実隓の目的は、順序付けられおいない任意のデヌタでアルゎリズムのパフォヌマンスを比范するこずです。 10 8個の10 8個のランダムな自然数のセットが生成され、各アルゎリズムに぀いお平均動䜜時間が枬定されたした。



任意のデヌタの堎合にテストされたすべおのアルゎリズムの耇雑さはShellSortを陀くOn log nです。 実際、ここでは非垞に䞀定のCの圱響を远跡できたす。







ご芧のずおり、デヌタ構造を䜿甚しないアルゎリズムは非垞に深刻に進歩しおいたす。 次に、郚分的に順序付けられたデヌタを怜蚎したす。



実隓2等サむズの独立した゜ヌトされたグルヌプ



昇順で゜ヌトされた10 8個の異なる自然数を指定したす。 それらをk個の連続した芁玠でグルヌプ化し、すべおのグルヌプを逆の順序に䞊べ替えたす。

10個の数字の䟋1 2 3 4 5 6 7 8 9 10

k = 110 9 8 7 6 5 4 3 2 1

k = 38 9 10 5 6 7 2 3 4 1

k = 56 7 8 9 10 1 2 3 4 5

k = 101 2 3 4 5 6 7 8 9 10



グルヌプは、保存されおいる倀の範囲内で重耇しないずいう意味で、互いに「独立」しおいたす。 ぀たり、任意のグルヌプの芁玠は、右偎のすべおのグルヌプの芁玠よりも倧きく、巊偎の芁玠よりも小さくなりたす。



10の环乗に等しいすべおのkに぀いお枬定が行われたした。







次のパタヌンに気付くこずができたす。



実隓3さたざたなサむズの゜ヌトされたグルヌプ、倀の範囲の制限



限られた範囲の10 8個の敎数が䞎えられこの堎合[0 ... 100000]、それらは1からkたでの任意のサむズのグルヌプによっお順序付けられたす。



そのようなデヌタセットはすでに実際のタスクからのデヌタず䜕らかの圢で䞀臎しおいるため、Dyce近接係数を蚈算するためにそれらを凊理する必芁がありたした







この䟋では、Smoothsortは最適な偎からではなく、Heapsortよりも長く動䜜し、同じように動䜜したす。 ティム゜ヌトは再び先を行っおいたす。



実隓4任意の再配眮



別の方法で郚分的に順序付けられたデヌタを生成したす10 8個の任意の自然数を取埗し、それらを゜ヌトし、堎所にある2぀の芁玠のk個の任意の順列を䜜成したす。







そしお、この実隓により、Smoothsortは最終的に「オヌプン」になりたす。入力デヌタの゜ヌトの床合いが増すに぀れお、加速が顕著になりたす。 これは、以前の実隓ずは異なり、ここでアルゎリズムがレオナルドのヒヌプを「移動」するのは、固定数の芁玠をそれほど倧きくしないためです。これは、ヒヌプ内の芁玠を移動するための倚数の操䜜を䌎いたせん。 しかし、しばらくするず、圌は再び「長くなりすぎ」たす。



たずめ



ご芧のずおり、説明したアルゎリズムは実甚的であり、さたざたな成功を収めながらタスクに察凊しおいたす。 絶察的なリヌダヌはTimsortでした。これは、デヌタの順序付けの床合いを高めながら顕著な加速を提䟛し、通垞の堎合はQuicksortレベルで機胜したす。 Python、OpenJDK、Android JDKに認識され、組み蟌たれおいるのも䞍思議ではありたせん。



ネットワヌク䞊のSmoothsortに぀いおは他のアルゎリズムず比范しおかなり倚くの情報があり、偶然ではありたせん。アむデアの耇雑さず物議を醞すパフォヌマンスのため、適甚可胜な方法よりもアルゎリズムの改良である可胜性が高くなりたす。 このアルゎリズムの実際のアプリケヌションは、IMおよびVoIPアプリケヌションの構築を目的ずしたsofia-sipラむブラリのみでした。



このテストでのShellsortの出珟は、その挞近的な耇雑さが他の2぀のアルゎリズムよりもやや倧きいため、かなり議論の䜙地のあるポむントです。 しかし、2぀の倧きな利点がありたすアむデアの単玔さず、スピヌドず実装の容易さでほが垞にSmoothsortをバむパスするアルゎリズムです-䜜業コヌドは数十行しかかかりたせんが、TimsortずSmoothsortの適切な実装には100行以䞊が必芁です。



パフォヌマンスを具䜓的に比范し、他のパラメヌタヌ远加メモリの䜿甚などには特に焊点を合わせおいないこずに泚意しおください。



私の䞻芳的な結論は、ラむブラリたたは倧芏暡なプロゞェクトに埋め蟌むために非垞に優れた゜ヌトアルゎリズムが必芁な堎合、Timsortが最適であるずいうこずです。 時間がなく、耇雑なアルゎリズムを蚘述する必芁がなく、結果をすぐに必芁ずする小さなタスクの堎合、アルゎリズムを蚘述しやすい最高のパフォヌマンスが埗られるため、Quicksortを省くこずができたす。



読んでくれおありがずう。 あなたが興味を持っおいたこずを願っおいたす。


More articles:


All Articles