Ruby的sort_by {rand}是如何工作的?
我认为这是一个很棒的Ruby单行程序:
someArray.sort_by {rand}
它简洁,可读,而且有效 – 但我不太明白。 这就是我所知道的:
-
rand
计算结果为0到1之间的数字(如0.783468632804653) -
rand
在上面的代码中被重复评估,因为将它分配给x
首先会破坏随机排序 -
sort_by {0.783468632804653}
或我尝试的任何其他数字对数组没有影响
在这种情况下, ruby-doc.org对我没什么帮助。
有人可以一步一步地解释这个吗?
更新
我现在一直在使用Ruby,我看到我在这里错过了一两个概念。 关键是:
-
rand
是一种方法(在Kernel上定义); 它会生成一个随机数 -
{rand}
是一个块,sort_by
保持, 每次想要比较集合中的两个项目时调用它。 如果集合是一堆代表国家的对象,它需要能够抓住其中的两个并确定哪个是第一个。 你把名字最长的那个放在首位吗? 土地面积最大的那个? 该块应该通过返回一个值“回答一个问题”来回答这个问题:“你问过西class牙对喀麦隆,我说喀麦隆是第一个。” (你可以用{|country| country.name.length}
做到这一点
sort_by
的其余部分在文档中进行了解释。 我仍然不太确定为什么返回一个随机数可以工作 – 大概是sort_by
它sort_by
到-1,0或1,哪个最接近? 但无论如何,每次调用块时获取不同的随机数与每次获取相同的数字完全不同。 当sort_by
说“这两个国家中的哪一个首先出现?”时, {rand}
戴上眼罩,转过10次,然后说“那个!” 🙂
在Ruby 1.8 / 1.9中, sort
和sort_by
都是用C实现的,这大致相当于它的工作方式:
假设您从[1,2,3,4]
开始并调用sort_by{rand}
:
-
(我发明了一些随机数字):
创建一个元组数组:
[[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]}
-
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]}
-
将指针从新排序的数组复制到原始数组中的正确位置。
[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_by
是sort
的细化,使用方式如下:
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
作用可以分为两个简单的步骤:
-
它在提供的数组和提供的块上调用
map
/collect
方法。 在你的情况下,它的结果只是一个随机数的数组 – 让我们调用这个中间数组A1。 注意,它具有初始数组的长度。 -
A1正常排序,但返回的不是排序的A1,而是原始数组,其中项目的移动方式与A1中相应的方式相同,而它正在排序!
这就是以下示例的工作原理:
["Paulo", "Sergito", "Nick"].sort_by {|word| word.length}
它按照它们的长度对单词进行排序,因为首先将单词数组映射到长度数组中,然后对这些长度进行排序,同时原始数组中的单词相应地移动。