3

我正在尝试在 Javascript 中实现（确实非常简单）绝对偏差排序算法。绝对偏差定义为一个元素与所有元素平均值之差的绝对值。例如，给定元素 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 中给了我正确的答案。）

更详细地说，我怀疑您看到奇怪结果的排序函数可能会在适当的位置对数组执行交换，并且可能存在一个或多个原始数组值丢失或复制的间隔，而排序机制是做它的事。因此，您的平均函数看到一个数组（有时）具有不同的值列表，这意味着平均值（有时）不同。

于 2013-07-30T23:00:20.790 回答
0

排序函数正在为排序的每一步重新计算数组的平均值。在排序过程中，不同的浏览器可能无法保持数组完整无缺。如果你添加console.log(previousValue, currentValue);到 array.reduce 函数中，你可以看到它的效果。

您需要先计算数组的平均值，并将其存储到变量中。然后将该变量传递给排序函数。以下是我对您的代码所做的更改：

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 回答
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 回答