4

ティムソートのアルゴリズムを理解しようとしていますが、スタック不変条件を実装する理由を理解するのに問題があります。

  1. A> B + C
  2. B> C

この文書によると、

後で発生する可能性のあるパターンを悪用するために、マージをできるだけ遅らせたいと思いますが、見つかった実行がまだメモリ階層の上位にあることを悪用するために、できるだけ早くマージを実行したいと思います。

キャッシュ効果を活用するために、できるだけ早くマージを実行したいことは理解していますが、遅延させたい理由がわかりません。それは彼がどのような「パターン」を意味するのでしょうか？

4

1 に答える 1

0

ここでのパターンは、並べ替えられるデータのパターンを指しています。たとえば、Timsort は、データ内の増加 (または減少) する実行を探しています。これは、既に並べ替えられているか、その場で実行を逆にすることで自明に並べ替えることができます。次に、これらの実行をマージソート パーティションに使用しようとします。

ところで、ティムソートに関するウィキペディアの記事が役に立つかもしれません: https://en.wikipedia.org/wiki/Timsort

于 2012-06-11T04:22:04.967 に答える