我一直在阅读 Sedgewick 和 Wayne 的“算法，第 4 版”，并且一直在实现 JavaScript 中讨论的算法。
我最近采用了书中提供的合并排序示例来比较自上而下和自下而上的方法...但我发现自下而上的运行速度更快(我认为)。请参阅我的博客上的分析。 - http://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/
我没能找到任何讨论说一种归并排序方法应该比另一种更快。我的实现(或分析)有缺陷吗？
注意:我的分析衡量的是算法的迭代循环，而不是严格意义上的数组比较/移动。也许这是有缺陷的或无关紧要的？
编辑:我的分析实际上并没有计算速度，所以我关于它运行“更快”的说法有点误导。我正在通过递归方法跟踪“迭代”(top-向下)和 for 循环(自下而上)- 自下而上似乎使用更少的迭代。
最佳答案
I have not been able to find any discussion that says one method of mergesort should be faster than the other.
自下而上和自上而下的合并排序以及其他变体在 90 年代得到了很好的研究。简而言之，如果将成本衡量为单个键的比较次数，则最佳成本相同(~(n lg n)/2)，自上而下的最差成本低于或等于最差自下而上的情况(但都是 ~ n lg n)和自上而下的平均成本低于或等于自下而上的平均情况(但都是 ~ n lg n)，其中“lg n”是二进制对数。差异源于线性项。当然，如果 n=2^p，这两个变体实际上是完全一样的。这意味着，比较而言，自上而下总是比自下而上更好。此外，已经证明自上而下归并排序的“对半”拆分策略是最优的。研究论文来自 Flajolet、Golin、Panny、Prodinger、Chen、Hwang 和 Sedgewick。
这是我在纯函数式程序的设计和分析(英国大学出版社)一书中用 Erlang 编写的内容:
tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T) -> T.
cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S, T, U) -> mrg(tms(S),tms(T)).
mrg( [], T) -> T;
mrg( S, []) -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg( [X|S], T) -> [X|mrg(S,T)].
请注意，这不是稳定的排序。此外，在 Erlang(和 OCaml)中，如果您想节省内存，则需要在模式中使用别名 (ALIAS=...)。这里的技巧是在不知道列表长度的情况下找到列表的中间位置。这是由 cutr/3 完成的，它处理两个指向输入列表的指针:一个递增 1，另一个递增 2，因此当第二个到达末尾时，第一个在中间。 (我从 Olivier Danvy 的一篇论文中了解到这一点。)这样，您不需要跟踪长度，也不会复制列表后半部分的单元格，因此您只需要 (1/2 )n lg n 额外空间，相对于 n lg n。这并不为人所知。
人们经常声称自下而上的变体更适合函数式语言或链表(Knuth、Panny、Prodinger)，但我认为这不是真的。
我和您一样对缺乏对合并排序的讨论感到困惑，所以我进行了自己的研究并写了一个大章节。我目前正在准备一个新版本，其中包含更多关于合并排序的 Material 。
顺便说一句，还有其他变体:队列归并排序和在线归并排序(我在我的书中讨论了后者)。
[编辑:由于成本的衡量标准是比较次数，因此选择数组与链表之间没有区别。当然，如果你用链表实现自上而下的变体，你必须要聪明，因为你不一定知道键的数量，但你每次至少需要遍历一半的键，并且重新分配，总共 (1/2)n lg n 个单元格(如果你够聪明的话)。使用链表的自下而上归并排序实际上需要更多的额外内存，n lg n + n 个单元格。因此，即使使用链表，自上而下的变体也是最佳选择。至于程序的长度，您的里程数可能会有所不同，但在函数式语言中，如果不需要稳定性，自上而下的合并排序可以比自下而上的更短。有一些论文讨论了合并排序的实现问题，例如就地(为此您需要数组)或稳定性等。例如，A Meticulous Analysis of Mergesort Programs，作者 Katajainen 和 Larsson Traff (1997).]
关于javascript - Mergesort - 自下而上比自上而下更快吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10153393/
我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的
原始问题Letd(n)bedefinedasthesumofproperdivisorsofn(numberslessthannwhichdivideevenlyinton).Ifd(a)=bandd(b)=a,whereab,thenaandbareanamicablepairandeachofaandbarecalledamicablenumbers.Forexample,theproperdivisorsof220are1,2,4,5,10,11,20,22,44,55and110;therefored(220)=284.Theproperdivisorsof284are1,2,
我有这个:AccountSummary我想单击该链接，但在使用link_to时出现错误。我试过:bot.click(page.link_with(:href=>/menu_home/))bot.click(page.link_with(:class=>'top_level_active'))bot.click(page.link_with(:href=>/AccountSummary/))我得到的错误是:NoMethodError:nil:NilClass的未定义方法“[]” 最佳答案 那是一个javascript链接。Mechan
在尝试解决“网格上的路径”问题时，我编写了代码defpaths(n,k)p=(1..n+k).to_ap.combination(n).to_a.sizeend代码工作正常，例如ifn==8andk==2代码返回45，这是正确的路径数。但是，当使用较大的数字时，代码非常慢，我正在努力想出如何加快这个过程。 最佳答案 与其构建组合数组只是为了计算它，不如编写function定义组合的数量。我敢肯定还有包含此功能和许多其他组合函数的gem。请注意，我使用的是gemDistribution对于Math.factorial方法，但这是另一种
我看到有关未找到文件min.map的错误消息:GETjQuery'sjquery-1.10.2.min.mapistriggeringa404(NotFound)截图这是从哪里来的？ 最佳答案 如果ChromeDevTools报告.map文件的404(可能是jquery-1.10.2.min.map、jquery.min.map或jquery-2.0.3.min.map，但任何事情都可能发生)首先要知道的是，这仅在使用DevTools时才会请求。您的用户不会遇到此404。现在您可以修复此问题或禁用sourcemap功能。修复:获取文
我有一个用Rails3编写的站点。我的帖子模型有一个名为“内容”的文本列。在帖子面板中，html表单使用tinymce将“content”列设置为textarea字段。在首页，因为使用了tinymce，post.html.erb的代码需要用这样的原始方法来实现。.好的，现在如果我关闭浏览器javascript，这个文本区域可以在没有tinymce的情况下输入，也许用户会输入任何xss，比如alert('xss');.我的前台会显示那个警告框。我尝试sanitize(@post.content)在posts_controller中，但sanitize方法将相互过滤tinymce样式。例如
关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭7年前。ImprovethisquestionC、Java、C#和Python都是从头编译的。感谢Facebook，PHP现在也可以编译并可以在HHVM上运行，从而提高程序的性能。Ruby不可编译并且比上述语言慢。Ruby有没有可能在未来被编译(就像PHP和HHVM一样)？或者可能有一些原因不能做到？
我有这两个gcd函数的实现:defgcd1(a,b)ifa==baelsifa>bif(a%b)==0belsegcd1(a%b,b)endelseif(b%a)==0aelsegcd1(a,b%a)endendenddefgcd2(a,b)if(a==b)returnaelsifb>amin,max=a,belsemin,max=b,aendwhile(max%min)!=0min,max=max%min,minendminend函数gcd1是尾递归的，而gcd2使用while循环。我已经验证rubinius通过对阶乘函数进行基准测试来执行TCO，只有阶乘函数基准测试显示递归版本和迭
出于某种原因，我必须为Firefox禁用javascript(手动，我们按照提到的步骤执行http://support.mozilla.org/en-US/kb/javascript-settings-for-interactive-web-pages#w_enabling-and-disabling-javascript)。使用Ruby的SeleniumWebDriver如何实现这一点？ 最佳答案 是的，这是可能的。而是另一种方式。您首先需要查看链接Selenium::WebDriver::Firefox::Profile#[]=
我正在尝试将用户提供的身份验证token与存储在我的服务器上的身份验证token进行比较。最明显的方法就是使用==，但这可能会造成定时攻击。为了缓解这种情况，我编写了这个安全比较函数:#stringcomparisonthatleaksnoinformationaboutthestrings.#looselybasedonhttps://github.com/rack/rack/blob/master/lib/rack/utils.rb#andhttp://security.stackexchange.com/questions/49849/timing-safe-string-com