jjzjj

javascript - 输入的初始排序如何影响 Array.sort 性能？

coder 2024-12-24 原文

输入的顺序是否可能影响 Array.sort() 的性能？如果是，怎么办？

最佳答案

这取决于几件事:

  • 运行时(不同的浏览器/运行时使用不同的排序算法)
  • 您输入的内容相对于所需顺序的排列方式
  • 是否使用自定义比较器(也与上一点有关)

我正在处理的一个应用程序在一个模块中遇到了严重的性能下降，该模块正在对 35K+ 字符串的列表进行排序，在它访问的 API 端点开始按排序顺序向其提供数据后。前端排序花费的时间从大约 30 毫秒减少到 6 秒 (200x)。

排序是使用自定义比较器完成的，该比较器优先考虑以特定后缀结尾的字符串。如果没有或两个字符串都以后缀结尾，则使用自然顺序。我使用浏览器开发人员工具分析了模块，发现大部分时间都花在了比较上。该配置文件还显示 QuickSort 是 Array.sort() 使用的底层算法(至少在 Chrome 中是这样)。

这很奇怪，因为 QuickSort 应该不受输入顺序的影响。根据维基百科:

[the worst case] may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations (e.g., the Lomuto partition scheme as described above) when all the elements are equal.

我变得很好奇，并对进行排序的多种变体进行了基准测试。我在命令行中使用了在节点上运行的 benchmark.js。基准测试和浏览器都在 v8 之上运行，因此它们应该使用相同的排序算法。结果令人惊讶:

6 tests completed.

  Ordered array, sorted with a default comparator           x 34.27 ops/sec ±1.07% (59 runs sampled)
  Ordered array, sorted with a custom comparator            x  0.18 ops/sec ±2.81% (5 runs sampled)
  Ordered array, shuffled, sorted with a custom comparator  x 38.37 ops/sec ±3.67% (51 runs sampled)
  Ordered array, shuffled, sorted with a default comparator x 29.20 ops/sec ±1.28% (51 runs sampled)
  Unordered array, sorted with a default comparator         x 28.38 ops/sec ±1.28% (50 runs sampled)
  Unordered array, sorted with a custom comparator          x 42.10 ops/sec ±1.32% (55 runs sampled)

这些结果表明，性能下降是由于与比较器相关的数据分布。以下是输入的一些特征:

  • 比较器优先考虑的后缀 (/Prod) 匹配大约 20% 的字符串
  • 当字符串按字母顺序排序时，以/Prod结尾的字符串很可能在整个过程中相对均匀地分布
  • ABC/Alpha、ABC/Beta、ABC/Prod 等序列很常见。

这可能使算法更有可能选择在其子序列中处于极端的枢轴，从而导致要执行的元素之间的大量比较。

这只发生在 Chrome 61 中。我已经测试了 Firefox 52.3 和 Safari 10.1，但问题没有重现。我认为这是因为使用了不同的排序算法。

关于javascript - 输入的初始排序如何影响 Array.sort 性能？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46228556/

javascriptArraycodesectioncomparatorsortingquicksort

有关javascript - 输入的初始排序如何影响 Array.sort 性能？的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  4. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  5. ruby - 在 Ruby 中实现 `call_user_func_array` - 2

    我怎样才能完成http://php.net/manual/en/function.call-user-func-array.php在ruby中？所以我可以这样做:classAppdeffoo(a,b)putsa+benddefbarargs=[1,2]App.send(:foo,args)#doesn'tworkApp.send(:foo,args[0],args[1])#doeswork,butdoesnotscaleendend 最佳答案 尝试分解数组App.send(:foo,*args)

  6. 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

  7. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

  8. ruby-on-rails - 未初始化的常量 Psych::Syck (NameError) - 2

    在我的gem中，我需要yaml并且在我的本地计算机上运行良好。但是在将我的gem推送到ruby​​gems.org之后，当我尝试使用我的gem时，我收到一条错误消息=>"uninitializedconstantPsych::Syck(NameError)"谁能帮我解决这个问题？附言RubyVersion=>ruby1.9.2,GemVersion=>1.6.2,Bundlerversion=>1.0.15 最佳答案 经过几个小时的研究，我发现=>“YAML使用未维护的Syck库，而Psych使用现代的LibYAML”因此，为了解决

  9. ruby - 如何指定 Rack 处理程序 - 2

    Rackup通过Rack的默认处理程序成功运行任何Rack应用程序。例如:classRackAppdefcall(environment)['200',{'Content-Type'=>'text/html'},["Helloworld"]]endendrunRackApp.new但是当最后一行更改为使用Rack的内置CGI处理程序时，rackup给出“NoMethodErrorat/undefinedmethod`call'fornil:NilClass”:Rack::Handler::CGI.runRackApp.newRack的其他内置处理程序也提出了同样的反对意见。例如Rack

  10. ruby - 如何每月在 Heroku 运行一次 Scheduler 插件？ - 2

    在选择我想要运行操作的频率时，唯一的选项是“每天”、“每小时”和“每10分钟”。谢谢!我想为我的Rails3.1应用程序运行调度程序。 最佳答案 这不是一个优雅的解决方案，但您可以安排它每天运行，并在实际开始工作之前检查日期是否为当月的第一天。 关于ruby-如何每月在Heroku运行一次Scheduler插件？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/8692687/

随机推荐