3

我正在尝试学习数组排序。这似乎很简单。但是在 mozilla 网站上，我遇到了一个讨论排序地图的部分（大约在页面下方的四分之三处）。

数组中的每个元素可以多次调用 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()比较函数来获得的。每次需要比较一对元素时，排序代码都会调用比较函数，这样可以节省大量函数调用。对于大型阵列，构建和取消构建地图的成本是值得的。

每个元素可以多次调用比较函数是排序工作方式的自然含义。如果每个元素只需要进行一次比较，那将是一个线性时间过程。

编辑- 将进行的比较次数将大致与数组长度乘以长度的以 2 为底的对数成正比。那么，对于 1000 个元素的数组，这与 10,000 次比较成正比（可能更接近 15,000，具体取决于实际的排序算法）。节省 20,000 次不必要的函数调用值得构建和取消构建排序映射所需的 2000 次操作。

于 2013-01-24T19:55:26.470 回答
3

对列表进行排序时，不仅要将项目与其他项目进行比较，还可能需要将其与其他几个项目进行比较。有些项目甚至可能必须与所有其他项目进行比较。

让我们看看在对数组进行排序时实际上有多少比较：

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"甚至比其他字符串有更多的比较，这意味着它与至少一个其他字符串至少进行了两次比较。

如果在比较值之前需要进行一些计算（如toLowerCase示例中的方法），则该计算将进行多次。通过在计算后缓存值，每个项目只会执行一次。

于 2013-01-24T20:06:52.253 回答
2

这被称为“装饰 - 排序 - 取消装饰”模式（你可以在Wikipedia上找到一个很好的解释）。

这个想法是，基于比较的排序必须至少调用比较函数n（其中n是列表中的项目数），因为这是检查数组是否已经排序所需的比较次数。通常，比较的次数会大于这个数（O(n ln n)如果您使用的是好的算法），并且根据 pingeonhole 原理，至少有一个值将被传递两次给比较函数。

如果您的比较函数在比较两个值之前进行了一些昂贵的处理，那么您可以通过首先执行昂贵的部分并存储每个值的结果来降低成本（因为您知道即使在最好的情况下您也必须这样做加工）。然后，在排序时，您使用更便宜的比较函数，它只比较那些缓存的输出。

在此示例中，“昂贵”部分是将字符串转换为小写。

于 2013-01-24T20:07:12.100 回答
1

把它想象成缓存。这只是说您不应该在比较函数中进行大量计算，因为您将一遍又一遍地计算相同的值。

“数组中的每个元素可以多次调用 compareFunction”是什么意思？

它的意思正是它所说的。让您拥有三个项目，A、B 和 C。它们需要按比较函数的结果进行排序。比较可以这样进行：

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

所以在这里，我们有 3 个值，但compare()函数执行了 6 次。使用临时数组来缓存事物可以确保我们对每个项目只进行一次计算，并且可以比较这些结果。

其次，我了解示例中正在执行的操作，但我不了解 compareFunction 的潜在“高[er]开销”。

如果compare()数据库获取（比较匹配行的计数）怎么办？或复杂的数学计算（阶乘、递归 fibbinocci 或对大量项目的迭代）这些你不想做的事情不止一次。

我会说大多数时候，将非常简单/快速的计算留在内联是很好的。不要过度优化。但是，如果您需要在比较中进行任何复杂或缓慢的操作，您就必须更加聪明。

于 2013-01-24T19:59:06.837 回答
0

为了回答您的第一个问题，为什么compareFunction数组中的每个元素会被多次调用？

对数组进行排序几乎总是需要 N 次以上，其中 N 是数组的大小（除非数组已经排序）。因此，对于数组中的每个元素，它可以与数组中的另一个元素进行最多 N 次比较（冒泡排序最多需要 N^2 次比较）。您提供的compareFunction每次都将用于确定两个元素是否小于/等于/大于，因此将在数组中的每个元素中多次调用。

对第二个问题的简单回答，为什么 a 可能会有更高的开销compareFunction？

假设您compareFunction在比较数组的两个元素时做了很多不必要的工作。这可能会导致排序变慢，因此使用 compareFunction 可能会导致更高的开销。

于 2013-01-24T19:58:58.053 回答