3

配列の並べ替えについて学習しようとしています。それはかなり簡単なようです。しかし、mozillaサイトで、マップの並べ替えについて説明しているセクションに出くわしました（ページの約4分の3）。

compareFunctionは、配列内の要素ごとに複数回呼び出すことができます。compareFunctionの性質によっては、これにより高いオーバーヘッドが発生する可能性があります。compareFunctionが実行する作業が多く、並べ替える要素が多いほど、並べ替えにマップを使用することを検討する方が賢明です。

与えられた例はこれです：

// the array to be sorted
var list = ["Delta", "alpha", "CHARLIE", "bravo"];
// temporary holder of position and sort-value
var map = [];
// container for the resulting order
var result = [];

// walk original array to map values and positions
for (var i=0, length = list.length; i < length; i++) {
  map.push({    
    // remember the index within the original array
    index: i, 
    // evaluate the value to sort
    value: list[i].toLowerCase()
  });
}

// sorting the map containing the reduced values
map.sort(function(a, b) {
  return a.value > b.value ? 1 : -1;
});

// copy values in right order
for (var i=0, length = map.length; i < length; i++) {
  result.push(list[map[i].index]);
}

// print sorted list
print(result);

私はいくつかのことを理解していません。compareFunctionつまり、「配列内の要素ごとに複数回呼び出すことができる」とはどういう意味ですか？誰かがその例を教えてもらえますか？次に、例で何が行われているのかは理解できますが、の潜在的な「より高いオーバーヘッド」については理解できませんcompareFunction。ここに示す例は非常に単純なようで、配列をオブジェクトにマッピングし、その値を並べ替えてから、配列に戻すと、一見するとはるかに多くのオーバーヘッドがかかります。これは単純な例であり、おそらく手順を示す以外の目的ではないことを理解しています。しかし、誰かがこのようにマップする方がオーバーヘッドが低くなる場合の例を挙げられますか？それはもっと多くの仕事のようです。

ありがとう！

4

5 に答える 5

3

toLowerCase()この例での主な時間の節約は、比較関数での呼び出しを避けることによって得られます。比較関数は、要素のペアを比較する必要があるたびに並べ替えコードによって呼び出されるため、多くの関数呼び出しを節約できます。マップの構築と構築解除のコストは、大規模な配列にとって価値があります。

要素ごとに比較関数が複数回呼び出される可能性があるということは、並べ替えの仕組みの自然な意味です。要素ごとに 1 つの比較のみが必要な場合は、線形時間のプロセスになります。

編集— 行われる比較の数は、配列の長さに底 2 の対数を掛けた長さにほぼ比例します。1000 要素の配列の場合、これは 10,000 回の比較に比例します (実際の並べ替えアルゴリズムによっては、おそらく 15,000 回近くになります)。20,000 回の不要な関数呼び出しを節約することは、ソート マップの構築と構築解除に必要な 2000 回の操作に値します。

于 2013-01-24T19:55:26.470 に答える
3

リストを並べ替える場合、アイテムは他の 1 つのアイテムと比較されるだけでなく、他のいくつかのアイテムと比較される必要がある場合があります。一部の項目は、他のすべての項目と比較する必要さえある場合があります。

配列をソートするときに実際にいくつの比較があるか見てみましょう:

var list = ["Delta", "alpha", "CHARLIE", "bravo", "orch", "worm", "tower"];

var o = [];
for (var i = 0; i < list.length; i++) {
    o.push({
        value: list[i],
        cnt: 0
    });
}

o.sort(function(x, y){
    x.cnt++;
    y.cnt++;
    return x.value == y.value ? 0 : x.value < y.value ? -1 : 1;
});

console.log(o);

結果：

[
 { value="CHARLIE",  cnt=3},
 { value="Delta",  cnt=3},
 { value="alpha",  cnt=4},
 { value="bravo",  cnt=3},
 { value="orch",  cnt=3},
 { value="tower",  cnt=7},
 { value="worm",  cnt=3}
]

(フィドル: http://jsfiddle.net/Guffa/hC6rV/ )

ご覧のとおり、各アイテムは他のいくつかのアイテムと比較されました。この文字列"tower"は、他の文字列よりも多くの比較が行われました。つまり、少なくとも 1 つの他の文字列と少なくとも 2 回比較されたことを意味します。

値を比較する前に何らかの計算が必要な場合 (toLowerCase例のメソッドのように)、その計算は数回行われます。その計算の後に値をキャッシュすることで、アイテムごとに 1 回だけ実行されます。

于 2013-01-24T20:06:52.253 に答える
2

これは「装飾 - 並べ替え - 装飾解除」パターンと呼ばれます (ウィキペディアでわかりやすい説明を見つけることができます)。

これは、配列が既にソートされていることを確認するために必要な比較の数であるため、比較ベースのソートでは、比較関数を少なくとも 1n回呼び出す必要があるという考えです (nはリスト内のアイテムの数)。通常、比較の回数はそれよりも多くなります (O(n ln n)適切なアルゴリズムを使用している場合)。ピンジョンホールの原則によれば、少なくとも 1 つの値が比較関数に 2 回渡されます。

比較関数が 2 つの値を比較する前に高価な処理を行う場合、最初に高価な部分を実行し、各値の結果を保存することでコストを削減できます (最良のシナリオでもそれを行う必要があることがわかっているため)。処理）。次に、ソート時に、キャッシュされた出力のみを比較する安価な比較関数を使用します。

この例では、「高価な」部分は文字列を小文字に変換しています。

于 2013-01-24T20:07:12.100 に答える
1

これはキャッシングのようなものだと考えてください。同じ値を何度も計算することになるため、比較関数で多くの計算を行うべきではないと言っているだけです。

「配列内の要素ごとにcompareFunctionを複数回呼び出すことができる」とはどういう意味ですか?

それはまさにそれが言うことを意味します。A、B、C の 3 つのアイテムを取得できます。比較関数の結果でソートする必要があります。比較は次のように行うことができます。

compare(A) to compare(B)
compare(A) to compare(C)
compare(B) to compare(C)

ここでは、3 つの値がありますが、compare()関数は 6 回実行されています。一時配列を使用して物事をキャッシュすることで、アイテムごとに 1 回だけ計算を実行し、それらの結果を比較できます。

第二に、この例で何が行われているかは理解できますが、compareFunction の潜在的な「高い [er] オーバーヘッド」は理解できません。

compare()データベースが (一致する行の数を比較して) フェッチするとどうなりますか? または、複雑な数学計算 (階乗、再帰的フィビノッチ、または多数の項目の反復) は、複数回実行したくないものです。

ほとんどの場合、非常に単純で高速な計算をインラインのままにしても問題ありません。最適化しすぎないでください。しかし、比較で複雑なものや遅いものが必要な場合は、それについてもっと賢くする必要があります。

于 2013-01-24T19:59:06.837 に答える
0

最初の質問に答えるためcompareFunctionに、配列内の要素ごとに複数回呼び出されるのはなぜですか?

配列の並べ替えには、ほとんどの場合、N を超えるパスが必要です。ここで、N は配列のサイズです (配列が既に並べ替えられていない場合)。したがって、配列内のすべての要素について、配列内の別の要素と最大 N 回比較できます (バブル ソートでは最大 N^2 の比較が必要です)。あなたcompareFunctionが提供する は、2 つの要素が小さい/等しい/大きいかどうかを判断するために毎回使用されるため、配列内の要素ごとに複数回呼び出されます。

2 番目の質問に対する簡単な回答compareFunctionです。

配列compareFunctionの 2 つの要素を比較しているときに、多くの不要な作業を行ったとします。これによりソートが遅くなる可能性があるため、compareFunction を使用するとオーバーヘッドが高くなる可能性があります。

于 2013-01-24T19:58:58.053 に答える