Clever Geek Handbook

配列＃ソートを隠すもの：利用可能なツールを使用したリバースエンジニアリング

ご存知かもしれませんが、JavaScript言語仕様では、配列に対するsortメソッドの特定の実装は規定されていません。 内部のアルゴリズムは、ブラウザーによって異なる場合があります（異なる場合があります）。 理論的には、Webアプリケーションのパフォーマンスが特定のエンジンでの配列の並べ替えの実装方法に依存する状況を想像できます。
非表示のテキスト
私はこれが実際に起こりうることを強く疑いますが、当時一定数の学期論文と学位論文を書いた人として、「国民経済への適用」のセクションなしではできませんでした。



オープンソースブラウザについて話している場合、このコードを開くだけで、そこで使用されているアルゴリズムを確認できます。 ただし、クローズドソースのブラウザがあります（指をさしません）。 この場合の対処方法



私たちはHabréにいるので、一部の読者はすでにお気に入りの逆アセンブラーに手を伸ばしており、一部の読者は1つの小規模で堅実でない会社から友人に電話をかける準備をしていると推測できます。 ただし、今日はマシンコードを掘り下げたり、インサイダー情報を使用したりしません。 私たちは面白い写真を見ます。











スクリプト内でsortメソッドの実装について何かを学ぶ機会があります。 これは、このメソッドが引数としてコンパレーター（数値を返す2つの変数の関数）を取り、そのアルゴリズムに基づいて、ソートアルゴリズムがどちらの引数が大きいかを結論付けるという事実にあります。 これにより、数字や文字列だけでなく、任意のオブジェクトの配列を並べ替えることができます。 また、これは私たちの場合に重要であり、これにより、配列のどの要素がどのような順序で並べ替えられているかを正確に見つけることができます。 たとえば、次のように： 



function compare(a, b){ console.log(a, b); return a - b; }




ただし、データを取得するだけでは十分ではありません。データを解釈する方法を理解する必要があります。 私が最後に本屋に行ったとき、「ダミーのために、彼らがどの要素を比較するかに基づいた分類アルゴリズムの分類」という本はありませんでした。 それ以来彼女はそこに現れた可能性がありますが、私は彼女なしでやることに決め、視覚パターンを認識する人の能力に頼っていました。



これを行います。特定の配列を取得し、特別にトレーニングされたコンパレーターを使用して並べ替えます。コンパレーターは各比較に関するデータを保存します。 次に、このデータを取得して、それに基づいて次の図を作成します：インデックスaおよびbを持つ要素が参加した各比較（既に並べ替えられた配列内のこれらの要素のインデックスを意味します）で、座標（a、b）でポイントをマークします。 同時に、ポイントを座標（b、a）でマークします。これにより、ポイントが美しくなり、図が実装の細部に依存しないようになります。 さらに、ポイントは単純なものではなく、色付きです。この色は、この比較が行われたときに象徴します。 並べ替えの最初に行われた比較は赤でマークされ、最後に近いものは青で表示され、それらの間には他の色の虹があります。



奇妙なことに、この計画はそれほど愚かではありませんでした。 最も一般的なアルゴリズムのいくつかを実装しましたが、それらは明確に区別可能なパターンを提供しました。 ここで、たとえば、選択ソート：











そして、これがバブルソートのようです。 違いは明確に区別でき、原則として、どこから来たのかを理解することは難しくありません。











どちらも非効率的なソートアルゴリズムです（平均時間の複雑さはO（n 2 ）です）。 より高度なアルゴリズムでは比較の回数が少なくなるため、図の陰影が少なくなります。 記事の冒頭には、ピラミッド型ソート（ヒープソート）の図がありますが、その上にははるかに多くの白いピクセルがあります。



各ソートには、独自の認識可能なパターンがあります。 選択による並べ替えのための滑らかなグラデーション、バブル並べ替えのための小さな横縞のあるグラデーション、挿入並べ替えのための異なる色のストライプ。 クイックソートは、クロスですべてを描画し、バイナリツリーでソートします（ツリーソート）-クロスは似ていますが、単調ではなく、雑多です。 マージソートには、対角線に近い特徴的な短い青色のストライプがあります。 ピラミッド型のソート図はマージソートに似ていますが、顕著な色のグラデーションがあります。



「しかし、ブラウザについてはどうでしょうか？」好奇心itive盛な読者は、記事がどこから始まったかをまだ忘れていない人に尋ねます。 特にそのような読者のために、現在のブラウザで配列番号の並べ替え図を確認できるページを作成し、よく知られているアルゴリズムの図と比較します。



要するに：







「しかし、Internet Explorerについてはどうでしょうか？」好奇心itive盛な読者が私に尋ねます。 まあ、私はいつかこの質問が来ることを知っていました... IEでは、恥ずかしさが出てきました。 IE11およびEdgeで取得した図は、実装されているどのアルゴリズムとも一致しません。 これらは次のようになります。











AVLツリーの並べ替えには共通点がありますが、明確な一致はありません。 しかし、私は希望を失いません。新しいページのアルゴリズムを引き続き掘り下げます。 そして、あなたの手が私を助けてくれるなら、私はあなたのプルリクエストを喜んで受け入れます。



今のところ、私が言わなければならないのはそれだけです。 あなたが興味を持っていたと思います。



UPD： Viacheslav01が示唆したように、IE11とEdgeは小さな配列に対して変更された挿入ソートを使用します。 彼はこの並べ替えの実装をページに追加して、誰もが確認および確認できるようにしました。 512要素よりも大きい配列の場合、クイックソートが使用されます。これは、URLに「？Size = 10」を追加することで確認できます。



Upd2： ブラックマジックを使用して、IE7がピラミッドソートを使用していることがわかりました。 この結果は、IE7がcanvasをサポートしていないという事実のため、一般の人々によるテストにはまだ利用できず、フォールバックをまだ提出していません。


More articles:


All Articles