Ruby 的最大函数顺序如何重复？

Question

我一直在查看 Ruby 的 Enumerable mixin (v2.4.1) 中的 max method。

这是一个相当简单的方法，但是当存在重复项时它如何排序项目有点令人困惑。

例如：

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是如何被选为第二项的？为什么取三个值时根本不选？

如果你取的数再多，顺序就会不一致（虽然集合中的项目是）。

我看了一眼the source code，不过好像是在做正常的比较；此处看到的顺序在该代码中并不明显。

谁能解释一下这个排序是如何实现的？我知道上面的排序都是"valid"，但是它们是怎么生成的呢？

Answer 1

您的示例可以通过使用 max_by 来简化，以产生类似的结果：

10.times{|y| p x.max_by(y) {|t| t%2}}

我花了一些时间在源代码上，但找不到任何漏洞。

我记得看到一篇名为 Switch: A Deep Embedding of Queries into Ruby 的出版物（Manuel Mayr 的论文）后，我找到了答案。

您可以在第 104 页的哪个位置找到 max_by 的答案：

... Here, the value in the input list that assumes the maximum when evaluated by the function is returned. If more than one value yields the maximum, the choice for a result among these values is arbitrary. ...

同样适用于：
sort & sort_by 来自评论@ emu.c

The result is not guaranteed to be stable. When two keys are equal, the order of the corresponding elements is unpredictable.

第一次，第二次编辑 - "we need to go deeper" => 希望你喜欢 "ride".

简答：
排序看起来像它的原因是 max_by 块的组合（导致开始使用 %2 中的 max 值进行排序，即 1 然后它继续 0) 和 qsort_r（BSD 快速排序）实现 @ruby.

长答案： 全部基于 ruby 2.4.2 或当前 2.5.0（正在开发中）的源代码。

快速排序算法可能因您使用的编译器而异。你可以使用qsort_r：GNU版本，BSD版本（你可以查看configure.ac）了解更多。 visual studio 使用的是 2012 或更高版本的 BSD。

+Tue Sep 15 12:44:32 2015  Nobuyoshi Nakada  <nobu@ruby-lang.org>
+
+   * util.c (ruby_qsort): use BSD-style qsort_r if available.

Thu May 12 00:18:19 2016  NAKAMURA Usaku  <usa@ruby-lang.org>

    * 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 之前是如何被调用的。原因？可能是标准化、堆栈 space 和速度（我自己没有测试 - 必须创建基准，这非常耗时）。

保存栈space在BSDqsort.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（从 02-07-2012 开始）。最新的 NetBSD qsort.c (revision:1.23).

现实生活中的例子 - "we need to go even deeper"

测试将在两个 (windows) 颗红宝石上进行：

第一个 ruby：将基于 DevKit 版本 2.2.2p95（于 2015 年 4 月 13 日发布）并且不包含 BSD qsort 实现。
第二个 ruby：将基于 MSYS2 tool-chain 版本 ruby 2.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}}

Ruby2.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]

Ruby2.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]

Ruby2.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]

Ruby2.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]

用以下代码处理： 12.times{|y| p x.max_by(y) {|t| t%2}}

Ruby2.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]

Ruby2.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评论：

Warning: If two objects compare as equal, their order after sorting is unpredictable. That is to say, the sorting is not stable. This can make a difference when the comparison considers only part of the elements. Two elements with the same sort key may differ in other respects.

现在像引擎一样对其进行排序：

[1,2,3,4,5,6,7,8,9] -> 首先考虑的是奇数 [1,3,5,7,9] 那些被认为与 max_by{|t| t%2} 相等的产生 [1,1,1,1,1].

结论：

现在选哪一个？那么在你的情况下是不可预测的，它是你得到的。即使对于相同的 ruby 版本，我也会得到不同的，因为底层 quick-sort 算法本质上是不稳定的。

Ruby 的最大函数顺序如何重复？

How does Ruby's max function order duplicates?

c

ruby

max

semantics

ruby-2.4