当前位置: 首页 > 面试题库 >

用JavaScript排序:返回布尔值是否足以用作比较函数?

柴嘉石
2023-03-14
问题内容

我总是成功地对数组进行如下排序(当我不希望使用标准字典顺序时):

var arr = […] // some numbers or so
arr.sort(function(a, b) {
    return a > b;
});

现在,有人告诉我这是错误的,我需要return a-b代替。是真的,如果是,为什么呢?我已经测试了比较功能,并且可以正常工作!此外,为什么我的解决方案错了会如此普遍?


问题答案:

我总是这样成功地排序我的数组

不,你没有。并没有注意到它。一个简单的反例:

> [1,1,0,2].sort(function(a, b){ return a>b })
Array [0, 1, 2, 1]
// in Opera 12. Results may vary between sorting algorithm implementations

为什么?

因为即使大于,比较函数也确实会返回false(或0等效地)。但是暗示着这两个元素被认为是相等的-排序算法相信这一点。b``a``0

深入解释

JavaScript中的比较功能

比较功能如何工作?

Array::sort方法可以将可选的自定义比较函数作为其参数。该函数接受两个参数(通常称为aand
b)进行比较,并应返回一个 数字

  • > 0a被认为大于b并且应该在其后进行排序
  • == 0什么时候a被认为等于,b而先到是无关紧要的
  • < 0a被认为是小于b,并应该在其之前进行排序

如果不返回数字,则结果将强制转换为数字(对于布尔值来说很方便)。返回的数字不一定要是-101(尽管通常是)。

一致的订购

为了保持一致,比较函数需要满足以下等式

comp(a, b) == -1 * comp(b, a)
// or, if values other than -1, 0 and 1 are considered:
comp(a, b) * comp(b, a) <= 0

如果违反了该要求,则排序行为将不确定。

引用ES5.1规范sort与[ES6规范相同):

如果comparefnis […]不是此数组元素的一致比较函数,则sort的行为由实现定义。

_函数comparefn是一组值的一致的比较函数S,如果所有的下面都满足所有值的要求ab以及c在所述一组(可能是相同的值)S:记号a <CF b装置comparefn(a,b) < 0; a =CF b手段comparefn(a,b) = 0(任何一个标志);和`a

CF b手段comparefn(a,b) > 0`。_

给定特定的一对值
并将其作为两个参数时,调用comparefn(a,b)总是返回相同的值。此外,是Number,不是。请注意,这意味着恰好一个,和将是真正的一对给定的和。v``a``b``Type(v)``v``NaN``a <CF b``a =CF b``a >CF b``a``b

  • 调用comparefn(a,b)不会修改此对象。
  • a =CF a反射性)
  • 如果a =CF b,则b =CF a([对称])
  • 如果a =CF bb =CF c,则a =CF c(的传递性为=CF
  • 如果a <CF bb <CF c,则a <CF c(的传递性为<CF
  • 如果a >CF bb >CF c,则a >CF c(的传递性为>CF

注意:以上条件对于确保comparefn集合划分S为等价类并且确保这些等价类完全有序是必要和充分的。

嗯,这是什么意思?我为什么要在乎?

排序算法需要将数组的各项相互比较。为了做好一项高效的工作,它不必将每个项目都进行比较,而需要能够推断出它们的顺序。为使此功能正常运行,需要遵循一些规则,自定义比较功能必须遵守。一个不重要的问题是,某项a等于其自身(compare(a, a) == 0)-这是上面列表中的第一项(反射性)。是的,这有点数学,但值得。

最重要的是传递性。它说,当算法已经比较两个值ab,并bc,并通过应用比较函数如发现a = bb < c,然后
就可以预期 的是a < c也同样适用。这似乎只是逻辑上的,并且是定义明确,一致的顺序所必需的。

但是您的比较功能 确实失败了 。让我们看这个例子:

 function compare(a, b) { return Number(a > b); }
 compare(0, 2) == 0 // ah, 2 and 0 are equal
 compare(1, 0) == 1 // ah, 1 is larger than 0
 // let's conclude: 1 is also larger than 2

哎呀 这就是为什么在使用不一致的比较函数调用排序算法时会失败的原因(在规范中,这是“与 实现相关的行为 ”,即不可预测的结果)。

为什么错误的解决方案如此普遍?

因为在许多其他语言中,有些排序算法不希望进行三向比较,而只是布尔值小于运算符。C++std::sort就是一个很好的例子。如果需要确定相等性,它将与交换的参数一起简单地应用两次。诚然,这可以更高效且不易出错,但是如果无法内联运算符,则需要更多
调用 比较函数。

反例

我已经测试了比较功能,并且可以正常工作!

仅凭运气,如果您尝试了一些随机示例。或者因为您的测试套件存在缺陷-错误和/或不完整。

这是我用来查找上述最小反例的小脚本:

function perms(n, i, arr, cb) {
// calls callback with all possible arrays of length n
    if (i >= n) return cb(arr);
    for (var j=0; j<n; j++) {
        arr[i] = j;
        perms(n, i+1, arr, cb);
    }
}
for (var i=2; ; i++) // infinite loop
    perms(i, 0, [], function(a) {
        if (    a.slice().sort(function(a,b){ return a>b }).toString()
             != a.slice().sort(function(a,b){ return a-b }).toString() )
            // you can also console.log() all of them, but remove the loop!
            throw a.toString();
    });

哪种比较功能正确?

当您要按字典顺序排序时,根本不使用任何比较功能。必要时将对数组中的项目进行字符串化。

可以像关系运算符一样工作的通用比较函数可以实现为

function(a, b) {
    if (a > b) return 1;
    if (a < b) return -1;
    /* else */ return 0;
}

通过一些技巧,可以将其最小化function(a,b){return +(a>b)||-(a<b)}

对于数字,您只需返回它们的差,即遵守上述所有定律:

function(a, b) {
    return a - b; // but make sure only numbers are passed (to avoid NaN)
}

如果你想反向排序,只取一个合适的交换和a使用b

如果你想复合类型(对象等)进行排序,替换每个a每个b与性能问题的访问,还是一个方法调用或任何你想进行排序。



 类似资料:
  • 我有一个布尔方法正在对字符串进行一些错误检查。我有一个int类常量叫“numwords”=8。我将一个字符串传递给布尔方法,在该方法中,我使用.split和.length对字符串进行单词计数。一个名为“words”的int计算字符串中的单词数。完成之后,我要执行一个if语句,比较单词和数字单词。如果它们的数目相等,则返回true,否则为false。我试过==和.等于,但都没用。有什么想法吗? 我试

  • 问题内容: 我做了几个布尔比较: 听起来像布尔值,并且可以互换。 有时候使用起来更清晰 我想知道: 是和python中预分配? 是始终返回相同的(或者与预先分配)(或)? 它是安全的替代与比较布尔值? 这与最佳实践无关。 我只想知道真相。 问题答案: 您可能永远不需要比较布尔值。如果您正在执行以下操作: …只需将其更改为: 没有或需要。 正如评论者所指出的,有比较布尔值的正当理由。如果两个布尔值都

  • 我正在尝试将哈希检查从服务器应用程序移动到PostgreSQL。换句话说,我需要调用一个对PGSQL的查询,它将来自查询的字符串与来自字段的字符串进行比较,并将相等比较的结果返回为bool,但如果没有关于clear SQL的过程,我不知道如何实现这一点。 upd:我有字段密码的表用户(当前为文本,将来为bytea)。我想写点什么 它必须返回true或false作为相等比较的结果。

  • 问题内容: 以这个为例(摘自Java regexchecker不起作用): 是否用于检查的值是否重要? 我知道有这是颇为相似。但是,很明显,这个问题只针对原始对象,而不是对象包装器;因此,将不适用。 另外,应该以不同于其他的方式对待? 问题答案: 从您的评论看来,您正在寻找使用包装器类的“最佳实践” 。但是实际上 并没有 最佳实践,因为使用此类开始是一个坏主意。使用对象包装的唯一原因是在您绝对 必

  • 我正在使用MyBatis调用PL SQL数据库中的一个函数。该函数中有一个OUT参数为布尔值,如下所示: 我的问题是,当我试图从xml映射器调用函数时,每次尝试mybatis都不能识别布尔输出,并抛出me和错误,就像不兼容的类型一样。另外,当我试图从PLSQL Developer测试该函数时,它会进行如下转换并以位形式返回布尔值。 忽略这个整数并指定MyBatis将输出视为布尔值是正确的?我怎么能

  • 我正在尝试这个代码编写练习,我太迷路了! 它甚至不编译,但即使它编译了,我肯定它也不会工作。