草庐IT

javascript - 在 JavaScript : Shouldn't returning a boolean be enough for a comparison function? 中排序

coder 2023-07-05 原文

我总是像这样成功地对我的数组进行排序(当我不想要标准的字典顺序时):

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

现在，有人告诉我这是错误的，我需要 return a-b反而。这是真的吗？如果是，为什么？我已经测试了我的比较功能，它有效!另外，为什么我的解决方案be so common什么时候出错？

最佳答案

TL; 博士

I have always successfully sorted my arrays like this



不，你没有。并且没有注意到。一个快速的反例:
> [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

why?



因为您的比较函数确实返回 false (或 0 ，等效地)即使 b大于 a .但是0意味着这两个元素被认为是相等的——排序算法相信这一点。

深入讲解

JavaScript 中的比较函数

How do comparison functions work?



Array::sort method可以将可选的自定义比较函数作为其参数。该函数需要比较两个参数(通常称为 a 和 b )，并应该返回一个 号码
  • > 0当a被认为大于 b并且应该在它之后排序
  • == 0当a被认为等于 b哪个先出现并不重要
  • < 0当a被认为小于 b并且应该排在它之前

    • 如果它不返回数字，结果将被转换为一个数字(这对 bool 值很方便)。返回的数字不需要正好是 -1或 0或 1 (虽然它通常是)。

    一致的排序

    为了保持一致，比较函数需要满足等式
    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 spec on sort (在 ES6 spec 中相同):

    If comparefn is […] not a consistent comparison function for the elements of this array, the behaviour of sort is implementation-defined.

    A function comparefn is a consistent comparison function for a set of values S if all of the requirements below are met for all values a, b, and c (possibly the same value) in the set S: The notation a <CF b means comparefn(a,b) < 0; a =CF b means comparefn(a,b) = 0 (of either sign); and a >CF b means comparefn(a,b) > 0.

    Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a <CF b, a =CF b, and a >CF b will be true for a given pair of a and b.

    • Calling comparefn(a,b) does not modify the this object.
    • a =CF a (reflexivity)
    • If a =CF b, then b =CF a (symmetry)
    • If a =CF b and b =CF c, then a =CF c (transitivity of =CF)
    • If a <CF b and b <CF c, then a <CF c (transitivity of <CF)
    • If a >CF b and b >CF c, then a >CF c (transitivity of >CF)

    NOTE: The above conditions are necessary and sufficient to ensure that comparefn divides the set S into equivalence classes and that these equivalence classes are totally ordered.



    Uh, what does this mean? Why should I care?



    排序算法需要将数组的项目相互比较。为了做好且高效的工作，它不一定需要将每个项目相互比较，但需要能够推理它们的顺序。为了使其正常工作，自定义比较函数需要遵守一些规则。一个微不足道的是一个项目 a等于自身( compare(a, a) == 0 )——这是上面列表中的第一项(自反性)。是的，这有点数学化，但返回不错。

    最重要的是传递性。它说当算法比较两个值时 a和 b ，还有 b与 c ，并通过应用比较函数发现，例如a = b和 b < 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

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

    Why is the wrong solution so common?



    因为在许多其他语言中，有排序算法不期望 three-way comparison但只是一个小于运算符的 bool 值。 C++ std::sort 就是一个很好的例子。如果需要确定相等性，它将使用交换的参数简单地应用两次。诚然，这可以更有效并且更不容易出错，但如果无法内联运算符，则需要对比较函数进行更多调用。

    反例

    I have tested my comparison function, and it works!



    如果您尝试了一些随机示例，那只能靠运气了。或者因为您的测试套件有缺陷 - 不正确和/或不完整。

    这是我用来查找上述最小反例的小脚本:
    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)} .

    For numbers ，您可以简单地返回它们的差异，这符合上述所有规律:
    function(a, b) {
    return a - b; // but make sure only numbers are passed (to avoid NaN)
}

    如果要逆序排序，只要取合适的并交换a与 b .

    如果要对复合类型(对象等)进行排序，请替换每个 a和每个 b访问相关属性，或方法调用或任何您想要排序的内容。

    关于javascript - 在 JavaScript : Shouldn't returning a boolean be enough for a comparison function? 中排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24080785/

    中排javascriptcodebrblockquotesortingcomparison

    有关javascript - 在 JavaScript : Shouldn't returning a boolean be enough for a comparison function? 中排序的更多相关文章

    1. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

      我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身，new.html.erb，有代码:当我运行rspec时，它失败了:1)messages/new.html.erbshou

    2. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

      我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

    3. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

      我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

    4. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2

      在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

    5. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

      我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

    6. ruby - 无法让 RSpec 工作—— 'require' : cannot load such file - 2

      我花了三天的时间用头撞墙，试图弄清楚为什么简单的“rake”不能通过我的规范文件。如果您遇到这种情况:任何文件夹路径中都不要有空格!。严重地。事实上，从现在开始，您命名的任何内容都没有空格。这是我的控制台输出:(在/Users/*****/Desktop/LearningRuby/learn_ruby)$rake/Users/*******/Desktop/LearningRuby/learn_ruby/00_hello/hello_spec.rb:116:in`require':cannotloadsuchfile--hello(LoadError) 最佳

    7. ruby-on-rails - 新 Rails 项目 : 'bundle install' can't install rails in gemfile - 2

      我已经像这样安装了一个新的Rails项目:$railsnewsite它执行并到达:bundleinstall但是当它似乎尝试安装依赖项时我得到了这个错误Gem::Ext::BuildError:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcheckingforlibkern/OSAtomic.h...yescreatingMakefilemake"DESTDIR="cleanmake"DESTDIR="

    8. ruby-on-rails - rspec should have_select ('cars' , :options => ['volvo' , 'saab' ] 不工作 - 2

      关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion在首页我有:汽车:VolvoSaabMercedesAudistatic_pages_spec.rb中的测试代码:it"shouldhavetherightselect"dovisithome_pathit{shouldhave_select('cars',:options=>['volvo','saab','mercedes','audi'])}end响应是rspec./spec/request

    9. ruby-on-rails - Rails 中的 NoMethodError::MailersController#preview undefined method `activation_token=' for nil:NilClass - 2

      似乎无法为此找到有效的答案。我正在阅读Rails教程的第10章第10.1.2节，但似乎无法使邮件程序预览正常工作。我发现处理错误的所有答案都与教程的不同部分相关，我假设我犯的错误正盯着我的脸。我已经完成并将教程中的代码复制/粘贴到相关文件中，但到目前为止，我还看不出我输入的内容与教程中的内容有什么区别。到目前为止，建议是在函数定义中添加或删除参数user，但这并没有解决问题。触发错误的url是http://localhost:3000/rails/mailers/user_mailer/account_activation.http://localhost:3000/rails/mai

    10. ruby-on-rails - Rails - 使用/自定义 URL : '/dashboard' 指定根路径 - 2

      如何使此根路径转到:“/dashboard”而不仅仅是http://example.com？root:to=>'dashboard#index',:constraints=>lambda{|req|!req.session[:user_id].blank?} 最佳答案 您可以通过以下方式实现:root:to=>redirect('/dashboard')match'/dashboard',:to=>"dashboard#index",:constraints=>lambda{|req|!req.session[:user_id].b

    随机推荐