这是一种相当简单的方法,但是当重复项存在时它如何命令项目有点令人困惑.
例如：
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,5] # 7 is now first
[9,5]
[9,6]
[9,2] # order has changed again (now seems more "natural")
如何选择7作为第二项？为什么在采用三个值时根本没有选择它？
如果您采用更多数字,则排序不一致(尽管集合中的项目是).
我已经看了一眼the source code,但似乎正在进行正常比较;从这个代码看,这里看到的顺序并不明显.
任何人都可以解释如何实现这种排序？我知道上面的排序都是“有效的”,但它们是如何产生的？
解决方法
10.times {| Y | p x.max_by(y){| 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.
…
The result is not guaranteed to be stable. When two keys are equal,
the order of the corresponding elements is unpredictable.
第一,第二编辑 – “我们需要更深入”=>我希望你会喜欢“骑”.
简短的回答：
看起来像它的排序的原因是max_by块的组合(导致从％2的最大值开始排序,然后它继续为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 <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,int (*)(const void *,const void *,void *),void *); #endif
>如果检测到BSD样式：
然后使用以下代码(可以在util.c找到).注意如何在ruby_qsort之前调用cmp_bsd_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,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 (revision:1.23).
现在,对于现实生活中的例子 – “我们需要更深入”
测试将在两个(窗户)ruby上进行：
> First ruby：将基于DevKit版本2.2.2p95(于2015年4月13日发布)并且不包含BSD qsort实现.
>第二个ruby：将基于MSYS2工具链版本ruby 2.4.2-p198(于2017年9月15日发布)并且确实包含用于BSD qsort实现的补丁(见上文).
代码：
x=[1,9]
10.times{|y| p x.max_by(y) {|t| t%2}}
Ruby 2.2.2p95：
The result: [] [5] [7,1] [3,5] [7,5] [5,9,6] [5,4] [5,2] [9,2]
Ruby 2.4.2-p198：
The result: [] [1] [7,1] [5,4] [9,2]
现在换不同的x：
X = [7,5]
Ruby 2.2.2p95：
The result: [] [1] [9,7] [1,3] [5,7] [7,2] [7,4] [7,8] [5,2]
Ruby 2.4.2-p198：
The result: [] [9] [9,7] [3,9] [7,8]
现在对于源数组中的相同项(qsort是不稳定的,见下文)：
x = [1,9]
使用以下代码处理它：
12.times {| Y | p x.max_by(y){| t |吨％2}}
Ruby 2.2.2p95：
The result: [] [3] [1,1] [9,7] [5,1] [1,4] [1,2] [1,8] [9,4]
Ruby 2.4.2-p198：
The Result: [] [1] [1,1] [7,4]
现在提出一个大问题 – >现在为什么结果不同？
第一个明显的答案是,当使用GNU或BSD实现时,结果会有所不同吗？对？那么实现是不同的,但是产生(检查链接的实现的细节)相同的结果.该问题的核心是其他地方.
算法本身就是真正的问题.当使用快速排序时,你得到的是不稳定的排序(当你比较两个相等的值时,它们的顺序不会保持不变).如果你有[1,9]然后你在块中转换为[1,1]使用max(_by),您将数组排序为[1,0].你从1开始,但是哪一个？那么你会得到不可预知的结果. (max(_by)是首先获得奇数而后是偶数的原因).
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,9] – >考虑的第一个是奇数[1,9],并认为这些与max_by {| t |相同. t％2}产生[1,1].
结论：
现在哪一个？嗯,在你的情况下它是不可预测的,它是你得到的.即使是相同的ruby版本,我也会得到不同的版本,因为基础quick-sort算法的性质不稳定.