3

Javascript で (非常に単純な) 絶対偏差ソート アルゴリズムを実装しようとしています。絶対偏差は、1 つの要素とすべての要素の平均との差の絶対値として定義されます。たとえば、要素 1、4、5、9 の場合、平均は (1 + 4 + 5 + 9) / 4 = 4.75 となるため、各要素の絶対偏差は次のように計算されます。

  • absDev(1) = |1 - 4.75| = 3.75
  • absDev(4) = |4 - 4.75| = 0.75
  • absDev(5) = |5 - 4.75| = 0.25
  • absDev(9) = |9 - 4.75| = 4.25

したがって、要素を絶対逸脱度の昇順で並べ替えると、5、4、1、9 のシーケンスが得られます。これまでのところ、私の現在の Javascript 実装では、さまざまなブラウザーでさまざまな結果が得られます。

ここにあります：http://jsfiddle.net/WVvuu/

  • Firefox と Safari では、期待される結果 5、4、1、9 が得られます
  • Chrome と Opera では、4、5、1、9 になります。
  • IE 10 では、1、4、5、9 を取得しています

私のコードにはおそらく非常に単純な間違いがあるに違いないと思いますが、それを見つけることができないようです。何が問題なのか、ブラウザを変更すると異なる結果が得られる理由を理解したいと思います。誰かが私に欠けているものを親切に説明していただければ幸いです。繰り返しますが、これはコードです：

var array = [1, 4, 5, 9];

function absDev(x) {
    return Math.abs(x - average(array));
}

function average(array) {
    var sum = array.reduce(function(previousValue, currentValue) {
        return previousValue + currentValue;
    }, 0);
    return sum / array.length;
}

array.sort(function(x, y) {
    return absDev(x) - absDev(y);
});

alert("Sorted array: " + array);
4

3 に答える 3

2

ソート中の配列の状態が必ずしも一貫しているとは限らないためだと思います。とにかく、各比較で平均を再計算するべきではありません。

array.sort(function(array) {
  var avg = array.reduce(function(previousValue, currentValue) {
    return previousValue + currentValue;
  }, 0);
  avg /= array.length;
  return function(x, y) {
    return Math.abs(x - avg) - Math.abs(y - avg);
  };
}(array));

それがうまくいくかどうか見てください。(編集— Chrome で正しい答えが得られます。)

より詳細には、奇妙な結果が表示されているソート関数が配列でスワップを実行する可能性があり、ソートメカニズムが実行されている間に1つ以上の元の配列値が欠落または複製される間隔がある可能性があると私は疑っていますそのことをやっています。したがって、平均化関数は、値のリストが異なる配列を (場合によって) 参照します。つまり、平均が (場合によって) 異なります。

于 2013-07-30T23:00:20.790 に答える
0

並べ替えが進行中の配列の状態は、実装で定義されるように指定されているため、並べ替え中にアイテムが特定の方法で配列内にあるとは信じられません。並べ替えプロセスを開始する前に、平均を事前に計算する必要があります。

参照

http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.4.11

見積もり

obj の [[Get]] 、 [[Put]] および [[Delete]] 内部メソッドへの呼び出しの実装依存のシーケンスを実行します

于 2013-07-30T23:13:49.313 に答える
0

ソート機能は、ソートの各ステップで配列の平均を再計算しています。ブラウザーによっては、並べ替えプロセス中に配列が完全にそのまま維持されない場合があります。console.log(previousValue, currentValue);array.reduce 関数に追加すると、この効果を確認できます。

最初に配列の平均を計算し、それを変数に格納する必要があります。次に、その変数を sort 関数に渡します。コードに加えた変更は次のとおりです。

var array = [1, 4, 5, 9];
var mean = average(array);

function absDev(x, mean) {
    return Math.abs(x - mean);
}

function average(array) {
    var sum = array.reduce(function(previousValue, currentValue) {
        console.log(previousValue, currentValue);
        return previousValue + currentValue;
    }, 0);
    return sum / array.length;
}

array.sort(function(x, y) {
    return absDev(x, mean) - absDev(y, mean);
});

console.log("Sorted array: " + array);
于 2013-07-30T23:05:48.373 に答える