Ruby的sort_by {rand}是如何工作的？

Question

我认为这是一个很棒的Ruby单行程序:

someArray.sort_by {rand}

它简洁,可读,而且有效 - 但我不太明白.这就是我所知道的:

1. rand 求值为0到1之间的数字(如0.783468632804653)
2. rand正在上面的代码中重复评估,因为将其分配给x第一个会破坏随机排序
3. sort_by {0.783468632804653},或我尝试的任何其他数字,对阵列没有影响

在这种情况下, ruby-doc.org对我没什么帮助.

有人可以一步一步地解释这个吗？

更新

我现在一直在使用Ruby,我发现我在这里错过了一两个概念.关键是:

1. rand是一种方法(在内核上定义); 它会生成一个随机数
2. {rand}是一个块,它sort_by保持,每次想要比较集合中的两个项目时调用它.如果集合是一堆代表国家的对象,它需要能够抓取其中的两个并确定哪个是第一个.你先放一个名字最长的那个吗？土地面积最大的那个？该区块应该通过返回一个值"回答一个问题"来回答这个问题:"你问过西班牙对喀麦隆,我说喀麦隆是第一个." (你可以这样做{|country| country.name.length}

其余的sort_by工作原理在文档中进行了解释.我仍然不太确定为什么返回一个随机数可行 - 大概是将sort_by它舍入为-1,0或1,哪个最接近？但无论如何,每次调用块时获取不同的随机数与每次获取相同的数字完全不同.什么时候sort_by说"这两个国家中的哪一个先来？",{rand}戴上眼罩,转过10次,然后说"那个!" :)

Answer 1

在Ruby 1.8/1.9都sort与sort_by用C实现,这是如何工作的一个大致相当于:

假设你开始[1,2,3,4]并致电sort_by{rand}:

1. (我发明了一些随机数字):

   创建一个元组数组: [[0.12232, 1],[0.53434, 2],[0.333, 3],[0.99, 4]]

   在大致相当的Ruby代码中,这是: [1,2,3,4].map{|x| [rand, x]}

2. Ruby的快速排序基于第一个元素在数组上执行:(注意内部实现远非微不足道,并且对已经排序的数组包含大量优化等)

   [[0.12232, 1],[0.333, 3],[0.53434, 2],[0.99, 4]]
   

   在粗略的Ruby中,这一步是: ary.sort{|x,y| x[0] <=> y[0]}

3. 将指针从新排序的数组复制到原始数组中的正确位置.

   [1,3,2,4]
   

   在粗略的Ruby中,这一步是: ary.map{|x,y| y}

该技术有时被称为" Schwartzian变换 ".缓存意味着昂贵的操作执行不超过N次.意思是,这是随机化数组的一种非常有效的方法.

注意:array.shuffle!因为它使用现代版本的Fisher-Yates,所以将是最有效的内置方式来对数组进行混洗(就地):

static VALUE
rb_ary_shuffle_bang(VALUE ary)
{
    long i = RARRAY_LEN(ary);

    rb_ary_modify(ary);
    while (i) {
  long j = rb_genrand_real()*i;
  VALUE tmp = RARRAY_PTR(ary)[--i];
  RARRAY_PTR(ary)[i] = RARRAY_PTR(ary)[j];
  RARRAY_PTR(ary)[j] = tmp;
    }
    return ary;
}

Answer 2

该块rand产生一个用于排序的键.每次评估时都会有所不同,因此您可以获得随机订单.

当你在那里放一个数字时,每次都是一样的,所以订单不会改变.这意味着排序算法是"稳定的" - 它不会按顺序移动.

这里有一些甚至更短,甚至更清晰的代码:

someArray.shuffle