Ruby的最大值函数如何排序重复元素？

Question

Ruby的最大值函数如何排序重复元素？

8

我一直在研究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不被选为第二个项目？

如果你取更多的数字，顺序是不一致的（尽管集合中的项是一致的）。

我已大致查看了源代码，但它似乎只做正常的比较；这里看到的排序并不明显从那段代码中。

有人能解释如何实现这种排序吗？我知道以上排序都是“有效”的，但它们是如何生成的呢？

- River

3

max函数使用一个块，该块使用两个变量来比较对象；您应该检查 |a, b| (a%2) <=> (b%2) 或类似的内容。另外，请不要使用输出的截图 - 请将实际输出复制/粘贴到代码块中。 - Derek

我的猜测是，它比较项目的顺序不能保证？ - Derek

2

你的排序关系真的很奇怪。基本上，所有奇数都大于所有偶数，但所有偶数和所有奇数都相等。由于1、3、5、7和9都相等，它们都是最大值，因此任何任意排列都是“最大值”。 - Jörg W Mittag

1

@JörgWMittag ... 你没有理解重点。任何排列都是有效的，但为什么选择特定的排列？是哪种实现导致了它？这个排列很“奇怪”，因为很难看出它是如何形成的。 - River

1

也许应该打上 C 的标签，因为这本质上是关于用那种语言编写的算法的问题。 - David Aldridge

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tukan · Accepted Answer

您的示例可以通过使用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的答案：

... 在这里，当函数求值时，输入列表中假定最大值的值被返回。如果有多个值产生最大值，则在这些值中选择结果是任意的。 ...

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

结果不能保证稳定。当两个键相等时，相应元素的顺序是不可预测的。

第一、第二次编辑 - “我们需要更深入” => 我希望你会喜欢这个“旅程”。

简短回答：
排序看起来像这样的原因是由max_by块引起的（导致从%2中的 max 值开始排序，即1，然后继续使用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.

If you have GNU qsort_r but not BSD: Only internal ruby_qsort implementation is used. Check util.c for internal implementation of the quick-sort (ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)) function by Tomoyuki Kawamura. @util.h

If HAVE_GNU_QSORT_R=1 then #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
```
If the BSD-style is detected: Then the below code is used (can be found at util.c). Notice how the cmp_bsd_qsort is called before ruby_qsort. The reason? Probably standardization, stack space and maybe speed (did not test it myself - would have to create benchmark, and that is quite time consuming).

在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（自02-07-2012以来提供）。最新的NetBSD链接1：qsort.c（修订版：1.23）。

现在是真实示例 - “我们需要更深入”

测试将在两个（Windows）Ruby上执行：

第一个Ruby将基于DevKit版本2.2.2p95（发布于2015年4月13日），不包含BSD qsort实现。

第二个Ruby将基于MSYS2工具链版本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}}

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]

Now for different 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] 使用以下代码进行处理： 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} 相等产生 [1,1,1,1,1]。

结论：

现在该选哪个呢？嗯，在你的情况下是不可预测的。即使对于相同的 ruby 版本，底层的 quick-sort 算法也是不稳定的。