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

我认为这是一个很棒的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是一种方法(在Kernel上定义); 它会生成一个随机数
  2. {rand}是一个块, sort_by保持, 每次想要比较集合中的两个项目调用它。 如果集合是一堆代表国家的对象,它需要能够抓住其中的两个并确定哪个是第一个。 你把名字最长的那个放在首位吗? 土地面积最大的那个? 该块应该通过返回一个值“回答一个问题”来回答这个问题:“你问过西class牙对喀麦隆,我说喀麦隆是第一个。” (你可以用{|country| country.name.length}做到这一点

sort_by的其余部分在文档中进行了解释。 我仍然不太确定为什么返回一个随机数可以工作 – 大概是sort_bysort_by到-1,0或1,哪个最接近? 但无论如何,每次调用块时获取不同的随机数与每次获取相同的数字完全不同。 当sort_by说“这两个国家中的哪一个首先出现?”时, {rand}戴上眼罩,转过10次,然后说“那个!” 🙂

在Ruby 1.8 / 1.9中, sortsort_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]} [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]} ary.sort{|x,y| x[0] <=> y[0]}

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

     [1,3,2,4] 

    在粗略的Ruby中,这一步是: ary.map{|x,y| y} 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; } 

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

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

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

 someArray.shuffle 

sort_bysort的细化,使用方式如下:

 people.sort do |person1, person2| person1 <=> person2 end 

当需要知道两个事物的顺序时, sort函数会产生块,在这种情况下,就是人。 如果左边的东西小于正确的东西,则块返回-1,如果它们相等则返回0,如果右边的东西大于左边的东西,则返回1。 宇宙飞船运营商<=>拥有美妙的属性,它返回-1,0或+1,确切地说需要什么样的排序。

我没看过,但Ruby正在使用quicksort算法的可能性很大。

一些聪明的人注意到我们在太空船操作员的左侧做了同样的事情,就像我们在右侧做的那样,并提出了sort_by ,使用如下:

 people.sort_by do |person| person.name end 

该算法不是将两个对象分配给块并让块比较它们的排序算法,而是为块提供单个对象。 然后该块返回应该用于进行排序的任何属性或值。 Ruby会记住块为每个元素返回的值,并比较这些值,知道将内容放入的顺序。很简单,您不必重复自己。

当排序算法产生块时,你的shuffle代码只是“制造东西”。 该块不是返回合理的东西,而是产生随机值。 这会导致排序算法随机排序。

sort_by作用可以分为两个简单的步骤:

  1. 它在提供的数组和提供的块上调用map / collect方法。 在你的情况下,它的结果只是一个随机数的数组 – 让我们调用这个中间数组A1。 注意,它具有初始数组的长度。

  2. A1正常排序,但返回的不是排序的A1,而是原始数组,其中项目的移动方式与A1中相应的方式相同,而它正在排序!

这就是以下示例的工作原理:

 ["Paulo", "Sergito", "Nick"].sort_by {|word| word.length} 

它按照它们的长度对单词进行排序,因为首先将单词数组映射到长度数组中,然后对这些长度进行排序,同时原始数组中的单词相应地移动。