ScalaのSeq集合におけるソート実装
26088 ワード
テキストhttps://dreamylost.cn/%E7%AE%97%E6%B3%95/%E7%AE%97%E6%B3%95-Scala%E4%B8%ADSeq%E7%9A%84%E6%8E%92%E5%BA%8F%E5%AE%9E%E7%8E%B0.html
Scala Seqをソートするには、sortBy、sorted、sortWithの3つの関数を使用するのが一般的です.
その中でsortByの実現は簡潔で、以下の通りである.
その本質はsorted関数を呼び出し,暗黙オブジェクトordを用いてfパラメータを比較関数に変換することであり,既存のJavaソートを用いて実現するためであると推測する.
on関数は以下のように実現される
on関数の役割:与えられた受信パラメータがUでTに戻るf関数に対してouter(Ordering特質のインスタンスに混入し、OrderingはJavaのComparatorインタフェースを継承する)を使用して比較関数を作成し、その比較関数は
sortByとsortWithではなくsortedを使用する場合、デフォルトではOrdering伴生オブジェクトの事前定義の比較関数が使用されます.これらの関数は最終的にJavaタイプのcompareメソッドを使用して、一般的な基本タイプのサイズを比較します.
sortByとsortWith自体はsortedメソッドを呼び出しているが,それらが伝達するordソート関数は異なる.
この2つのメソッドがsortedを呼び出すには、暗黙的ではなく表示伝達パラメータを使用し、sortedを直接呼び出すと、Orderingとその伴生オブジェクトドメイン内で使用可能な暗黙的ソート関数が検索されます).比較関数はJavaの比較器です.
JavaのArrays.sortメソッドは主に配列をソートする
指定した比較器に基づいて指定したオブジェクト配列をソートします.配列内のすべての要素は、指定された比較器によって相互比較される必要があります(すなわち、c.compare(e 1,e 2)配列内の任意の要素に対してCastException異常を放出することはできません).Scalaの場合、Seqは異なるタイプのデータを格納することができるが、下位ソートはJava配列に基づいているため、異なるタイプのデータを格納したSeqはsortedソートできない.
TimSortは、安定で適応的で反復的な集計ソートであり、部分的にソートされた配列上で実行する際に必要な比較はnlg(n)よりはるかに少ないが、ランダムにソートされていない配列上で実行する際に提供される性能は、従来の集計ソートに相当する.すべての正しい集計ソートと同様に,このソートは安定であり,実行にはO(nlogn)時間(最悪)が必要である.最悪の場合、このソートにはn/2個のオブジェクト参照の一時記憶領域が必要である.最良の場合、それはわずかな一定の空間しか必要としない.
本質は、要素の既存のシーケンス状態を最適化してよく利用できる集計ソートである.
コンパレータのないArrays.sort実装
比較器のあるTimSort.sortの実現
countRunAndMakeAscending実装
minRunLength実装配列サイズがMINより小さい場合MERGE、n を返します配列サイズが2のN乗の場合、16(MIN_MERGE/2) が戻る.その他の場合、16と32の間の数 が見つかるまで、ビット毎に右にシフト(すなわち2で割る)する.は隣接するブロックのみを集計し、集計する2つのrunはすでにソートされた であることに注意する.現在のブロック数が2のみの場合、IfX<=Yは、XとYを にまとめる.現在のブロック数>=3、IfX<=Y+Zの場合、X>Y+ZとY>Z が同時に満たされるまでXとYを集計する.
Scala Seqをソートするには、sortBy、sorted、sortWithの3つの関数を使用するのが一般的です.
その中でsortByの実現は簡潔で、以下の通りである.
def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sorted(ord on f)
その本質はsorted関数を呼び出し,暗黙オブジェクトordを用いてfパラメータを比較関数に変換することであり,既存のJavaソートを用いて実現するためであると推測する.
on関数は以下のように実現される
def on[U](f: U => T): Ordering[U] = new Ordering[U] {
def compare(x: U, y: U) = outer.compare(f(x), f(y))
}
on関数の役割:与えられた受信パラメータがUでTに戻るf関数に対してouter(Ordering特質のインスタンスに混入し、OrderingはJavaのComparatorインタフェースを継承する)を使用して比較関数を作成し、その比較関数は
def compare(x:U, y:U) = Ordering[T].compare(f(x), f(y))
sortByとsortWithではなくsortedを使用する場合、デフォルトではOrdering伴生オブジェクトの事前定義の比較関数が使用されます.これらの関数は最終的にJavaタイプのcompareメソッドを使用して、一般的な基本タイプのサイズを比較します.
sortByとsortWith自体はsortedメソッドを呼び出しているが,それらが伝達するordソート関数は異なる.
この2つのメソッドがsortedを呼び出すには、暗黙的ではなく表示伝達パラメータを使用し、sortedを直接呼び出すと、Orderingとその伴生オブジェクトドメイン内で使用可能な暗黙的ソート関数が検索されます).比較関数はJavaの比較器です.
def sorted[B >: A](implicit ord: Ordering[B]): Repr = {
val len = this.length
// （ Scala ， ）
val b = newBuilder
// ，
if (len == 1) b ++= this
else if (len > 1) {
//
// “result” 。 （builder） 。 Set 0~4
b.sizeHint(len)
val arr = new Array[AnyRef](len) // ArraySeq
var i = 0
for (x JavaのArrays.sortメソッドは主に配列をソートする
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
// ， sort， （ ）
sort(a);
} else {
// ，
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
// TimSort
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
指定した比較器に基づいて指定したオブジェクト配列をソートします.配列内のすべての要素は、指定された比較器によって相互比較される必要があります(すなわち、c.compare(e 1,e 2)配列内の任意の要素に対してCastException異常を放出することはできません).Scalaの場合、Seqは異なるタイプのデータを格納することができるが、下位ソートはJava配列に基づいているため、異なるタイプのデータを格納したSeqはsortedソートできない.
TimSortは、安定で適応的で反復的な集計ソートであり、部分的にソートされた配列上で実行する際に必要な比較はnlg(n)よりはるかに少ないが、ランダムにソートされていない配列上で実行する際に提供される性能は、従来の集計ソートに相当する.すべての正しい集計ソートと同様に,このソートは安定であり,実行にはO(nlogn)時間(最悪)が必要である.最悪の場合、このソートにはn/2個のオブジェクト参照の一時記憶領域が必要である.最良の場合、それはわずかな一定の空間しか必要としない.
本質は、要素の既存のシーケンス状態を最適化してよく利用できる集計ソートである.
コンパレータのないArrays.sort実装
public static void sort(Object[] a) {
// java.util.Arrays.useLegacyMergeSort
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
//ComparableTimSort TimSort ， Comparable ， 。 ， TimSort， 。
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
比較器のあるTimSort.sortの実現
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
//
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // 0 1
// ， “mini-TimSort”， 32， 32 ， binarySort（ ， O(nlogn) ， O(n^2) ）
//MIN_MERGE 2 。Tim Peter C 64， 32 。 2 ， minRunLength
// binarySort， ， ： lo（ ） start（ ） 。
//1. （ ）
//2. ，binarySort a[lo:hi] ， a[lo:start] 。
// a[start:hi] ， binarySearch a[lo:start] ， 。
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
// ， （ initRunLen， ）
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
// ， minRun ， minRun
int minRun = minRunLength(nRemaining);
do {
// ，countRunAndMakeAscending run
// run ， ， ， ，
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// minRun， ， binarySort run ， ，run
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
runLen = force;
}
// run a[lo:runLen]， ts.pushRun(lo, runLen);
// merge ： （pushRun run ）
ts.pushRun(lo, runLen);
// merge
ts.mergeCollapse();
// run，lo
lo += runLen;
nRemaining -= runLen; //
} while (nRemaining != 0); //
// run
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
countRunAndMakeAscending実装
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
if (c.compare(a[runHi++], a[lo]) < 0) { //
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { //
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
//
return runHi - lo;
}
minRunLength実装
private static int minRunLength(int n) {
assert n >= 0;
int r = 0;
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
private void mergeCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
if (runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
} else if (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} else {
break; // Invariant is established
}
}
}