Ruby的max函数命令如何重复？
我一直在看Ruby的Enumerable mixin（v2.4.1）中的max方法 。
这是一种相当简单的方法，但是当重复项存在时它如何命令项目有点令人困惑。
例如：
x = [1,2,3,4,5,6,7,8,9] x.max {|a, b| a%2 b%2} => 1 10.times{|y| p x.max(y) {|a, b| a%2 b%2}} [] [1] [1, 7] # why is 7 the next element after 1? [3, 1, 5] # why no more 7? [7, 3, 1, 5] # 7 is now first [9, 7, 3, 1, 5] [9, 7, 3, 1, 5, 6] [9, 7, 3, 1, 5, 4, 6] [9, 7, 3, 1, 5, 2, 4, 6] [9, 7, 5, 3, 1, 8, 6, 4, 2] # order has changed again (now seems more "natural")
如何选择7作为第二项？ 为什么在采用三个值时根本没有选择它？
如果您采用更多数字，则排序不一致（尽管集合中的项目是 ）。
我已经看了一下源代码 ，但似乎正在进行正常的比较; 从这个代码看，这里看到的顺序并不明显。
任何人都可以解释如何实现这种排序？ 我知道上面的排序都是“有效的”，但它们是如何生成的？
通过使用max_by产生类似的结果，可以简化您的示例：
10.times{|y| p x.max_by(y) {|t| t%2}}
我花了一些时间与源，但找不到任何漏洞。
在我记得看到一本名为Switch: A Deep Embedding of Queries into Ruby的出版物Switch: A Deep Embedding of Queries into Ruby （Manuel Mayr的论文）后，我找到了答案。
在页104上，您可以找到max_by的答案：
…这里，返回输入列表中假定函数计算最大值时的值。 如果多个值产生最大值，则在这些值中选择结果是任意的。 …
同样适用于：
来自评论@ emu.c的 sort ＆ sort_by
结果不能保证稳定。 当两个键相等时，相应元素的顺序是不可预测的。
第一，第二编辑 – “我们需要更深入”=>我希望你会喜欢“骑”。
简短的回答：
看起来像它的排序的原因是max_by块的组合（导致从%2 max开始排序，然后它继续为0 ）和qsort_r（BSD快速排序）实现@ruby。
答案很长：全部基于ruby 2.4.2或当前2.5.0（现在正在开发）的源代码。
快速排序算法可能因您使用的编译器而异。 您可以使用qsort_r：GNU版本，BSD版本（您可以查看configure.ac ）了解更多信息。 视觉工作室使用2012年或更晚的BSD版本。
+Tue Sep 15 12:44:32 2015 Nobuyoshi Nakada + + * util.c (ruby_qsort): use BSD-style qsort_r if available.
Thu May 12 00:18:19 2016 NAKAMURA Usaku * win32/Makefile.sub (HAVE_QSORT_S): use qsort_s only for Visual Studio 2012 or later, because VS2010 seems to causes a SEGV in test/ruby/test_enum.rb.
-
如果你有GNU qsort_r而不是BSD：只使用内部ruby_qsort实现。 检查util.c以获取Tomoyuki Kawamura的快速排序（
ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)）函数的内部实现。@util.h如果HAVE_GNU_QSORT_R = 1则
#define ruby_qsort qsort_r：#ifdef HAVE_GNU_QSORT_R #define ruby_qsort qsort_r #else void ruby_qsort(void *, const size_t, const size_t, int (*)(const void *, const void *, void *), void *); #endif -
如果检测到BSD样式：则使用以下代码（可以在util.c中找到）。 注意如何在
cmp_bsd_qsort之前调用ruby_qsort。 原因？ 可能标准化，堆栈空间和速度（没有自己测试 – 必须创建基准，这是非常耗时的）。
保存堆栈空间在BSD qsort.c源代码中指示：
/* * To save stack space we sort the smaller side of the partition first * using recursion and eliminate tail recursion for the larger side. */
ruby源代码中的BSD分支：
#if defined HAVE_BSD_QSORT_R typedef int (cmpfunc_t)(const void*, const void*, void*); struct bsd_qsort_r_args { cmpfunc_t *cmp; void *arg; }; static int cmp_bsd_qsort(void *d, const void *a, const void *b) { const struct bsd_qsort_r_args *args = d; return (*args->cmp)(a, b, args->arg); } void ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d) { struct bsd_qsort_r_args args; args.cmp = cmp; args.arg = d; qsort_r(base, nel, size, &args, cmp_bsd_qsort); }
如果您正在使用MSYS2在Windows上编译ruby（不再使用DevKit，而是用于Windows安装程序的MSYS2，我大部分时间都在使用）NetBSD版本的qsort_r（从2012年7月2日开始）。 最新的NetBSD qsort.c（修订版：1.23） 。
现在，对于现实生活中的例子 – “我们需要更深入”
测试将在两个（窗户）ruby上进行：
-
第一个ruby：将基于
DevKit版本2.2.2p95（于2015年4月13日发布）并且不包含BSD qsort实现。 -
第二个ruby：将基于
MSYS2 tool-chain版本ruby2.4.2-p198（于2017年9月15日发布）并且确实包含用于BSD qsort实现的补丁（见上文）。
代码：
x=[1,2,3,4,5,6,7,8,9] 10.times{|y| p x.max_by(y) {|t| t%2}}
Ruby 2.2.2p95 ：
The result: [] [5] [7, 1] [3, 1, 5] [7, 3, 1, 5] [9, 7, 3, 1, 5] [5, 9, 1, 3, 7, 6] [5, 1, 9, 3, 7, 6, 4] [5, 1, 3, 7, 9, 6, 4, 2] [9, 1, 7, 3, 5, 4, 6, 8, 2]
Ruby 2.4.2-p198 ：
The result: [] [1] [7, 1] [5, 3, 1] [5, 7, 3, 1] [5, 9, 7, 3, 1] [5, 1, 9, 7, 3, 6] [5, 1, 3, 9, 7, 4, 6] [5, 1, 3, 7, 9, 2, 6, 4] [9, 1, 3, 7, 5, 8, 4, 6, 2]
现在针对不同的x ： x=[7,9,3,4,2,6,1,8,5]
Ruby 2.2.2p95 ：
The result: [] [1] [9, 7] [1, 7, 3] [5, 1, 7, 3] [5, 1, 3, 9, 7] [7, 5, 9, 3, 1, 2] [7, 9, 5, 3, 1, 2, 4] [7, 9, 3, 1, 5, 2, 4, 8] [5, 9, 1, 3, 7, 4, 6, 8, 2]
Ruby 2.4.2-p198 ：
The result: [] [9] [9, 7] [3, 1, 7] [3, 5, 1, 7] [7, 5, 1, 3, 9] [7, 9, 5, 1, 3, 2] [7, 9, 3, 5, 1, 4, 2] [7, 9, 3, 1, 5, 8, 2, 4] [5, 9, 3, 1, 7, 2, 4, 6, 8]
现在对于源数组中的相同项（qsort不稳定，见下文）： x=[1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9] 1,1,1,2,3,4,5,6,7,8,9 x=[1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
使用以下代码处理它： 12.times{|y| p x.max_by(y) {|t| t%2}} 12.times{|y| p x.max_by(y) {|t| t%2}}
Ruby 2.2.2p95 ：
The result: [] [3] [1, 1] [9, 1, 7] [3, 9, 1, 7] [5, 3, 9, 1, 7] [1, 5, 3, 9, 1, 7] [5, 9, 3, 7, 1, 1, 1] [1, 5, 9, 1, 7, 1, 3, 4] [1, 1, 5, 9, 1, 7, 3, 4, 2] [1, 1, 1, 5, 7, 3, 9, 4, 2, 8] [9, 1, 7, 1, 5, 3, 1, 2, 6, 8, 4]
Ruby 2.4.2-p198 ：
The Result: [] [1] [1, 1] [7, 9, 1] [7, 3, 9, 1] [7, 5, 3, 9, 1] [7, 1, 5, 3, 9, 1] [1, 5, 9, 3, 7, 1, 1] [1, 1, 5, 9, 3, 7, 1, 4] [1, 1, 1, 5, 9, 3, 7, 2, 4] [1, 7, 3, 1, 5, 9, 1, 2, 4, 8] [9, 3, 1, 7, 1, 5, 1, 2, 8, 6, 4]
现在提出一个大问题 – >现在为什么结果会有所不同？
第一个明显的答案是，当使用GNU或BSD实现时，结果会有所不同吗？ 对？ 那么实现是不同的，但是产生（检查链接的实现的细节）相同的结果。 该问题的核心是其他地方。
算法本身就是真正的问题。 当使用快速排序时，你得到的是不稳定的排序（当你比较两个相等的值时，它们的顺序不会保持不变）。 如果你有[1,2,3,4,5,6,7,8,9]然后你在块中转换为[1,0,1,0,1,0,1,0,1]使用max（_by），您将数组排序为[1,1,1,1,1,0,0,0,0]。 你从1开始，但是哪一个？ 那么你得到了不可预知的结果。 （max（_by）是首先获得奇数而后是偶数的原因）。
请参阅GNU qsort评论：
警告：如果两个对象比较相等，则排序后的顺序是不可预测的。 也就是说，排序不稳定。 当比较仅考虑部分元素时，这可能会有所不同。 具有相同排序键的两个元素在其他方面可能不同。
现在像引擎一样对它进行排序：
[1,2,3,4,5,6,7,8,9] – >考虑的第一个是奇数[1,3,5,7,9] ，这些被认为与max_by{|t| t%2} max_by{|t| t%2}产生[1,1,1,1,1] 。
结论：
现在哪一个？ 嗯，在你的情况下它是不可预测的，它是你得到的。 即使是相同的ruby版本，我也会得到不同的版本，因为底层的快速排序算法本质上是不稳定的。