Ruby 的 sort_by {rand} 如何工作? [英] How does Ruby's sort_by {rand} work?

问题描述

我认为这是一个很棒的 Ruby one-liner:

I think this is a great Ruby one-liner:

someArray.sort_by {rand}

它简洁、易读且有效——但我不太明白是如何做到的.以下是我所知道的:

It's concise, it's readable, and it works - but I don't quite understand how. Here's what I know:

1. rand 计算结果为 0 到 1 之间的数字(如 0.783468632804653)
2. rand 在上面的代码中被重复计算，因为将它分配给 x 首先打破了随机排序
3. sort_by {0.783468632804653} 或我尝试过的任何其他数字对数组没有影响

1. rand evaluates to a number between 0 and 1 (like 0.783468632804653)
2. rand is being repeatedly evaluated in the code above, because assigning it to x first breaks the random sort
3. sort_by {0.783468632804653}, or any other number I tried, has no effect on the array

ruby-doc.org 对我帮助不大在这种情况下.

ruby-doc.org wasn't much help to me in this case.

有人能一步一步解释这个吗?

Can someone explain this step-by-step?

我现在使用 Ruby 的时间更长了，我发现我在这里遗漏了一两个概念.关键是:

I've been using Ruby longer now, and I see that I was missing a concept or two here. The key thing is that:

1. rand 是一个方法(定义在内核上)；它生成一个随机数
2. {rand} 是一个块，由 sort_by 保存，每次调用它来比较集合中的两个项目.如果集合是一堆代表国家的对象，它需要能够抓取其中的两个并确定哪个先出现.你把名字最长的放在第一位吗?陆地面积最大的那个?该块应该通过返回一个值来回答这个问题，该值表示您询问了西班牙与喀麦隆的情况，我说喀麦隆是第一位的".(你可以用 {|country| country.name.length}

1. rand is a method (defined on Kernel); it generates a random number
2. {rand} is a block, which sort_by keeps, calling it each time it wants to compare two items in the collection. If the collection is a bunch of objects representing countries, it needs to be able to grab two of them and determine which one comes first. Do you put the one with the longest name first? The one with the largest land mass? The block should answer that question by returning a value that says "you asked about Spain vs Cameroon, and I say Cameroon comes first." (You could do that with {|country| country.name.length}

sort_by 的其他工作方式在文档中进行了说明.我仍然不太确定为什么返回一个随机数完全有效 - 大概 sort_by 将其四舍五入为 -1、0 或 1，以最接近的为准?但无论如何，每次调用块时获得不同的随机数与每次都获得相同的数字完全不同.当 sort_by 说这两个国家中哪个先出现?"时，{rand} 蒙上眼罩，转身 10 次，指着说那个国家"！":)

The rest of how sort_by works is explained in the documentation. I'm still not quite sure why returning a random number works at all - presumably sort_by rounds it to -1, 0, or 1, whichever is closest? But in any case, getting a different random number every time you call the block is quite different from getting the same number every time. When sort_by says "which of these two countries comes first?", {rand} puts on a blindfold, turns around 10 times, points and says "that one!" :)

推荐答案

在 Ruby 1.8/1.9 中，sort 和 sort_by 都是用 C 实现的，这是一个粗略的等价物这是如何工作的:

In Ruby 1.8/1.9 both sort and sort_by are implemented in C, this is a rough equivalent of how this works:

假设您以 [1,2,3,4] 开头并调用 sort_by{rand}:

Say you start with [1,2,3,4] and call sort_by{rand}:

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

1. (I invented some random numbers):

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

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

In roughly equivalent Ruby code this is: [1,2,3,4].map{|x| [rand, x]}

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

Ruby's quick sort is performed on the array based off the first element: (note the internal implementation is far from trivial and contains a ton of optimisations for already ordered arrays and such)

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

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

In rough Ruby this step is: ary.sort{|x,y| x[0] <=> y[0]}

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

Pointers are copied from the new sorted array, to the correct position in the original array.

[1,3,2,4]

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

In rough Ruby this step is: ary.map{|x,y| y}

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

This technique is sometimes referred to as a "Schwartzian Transform". Caching means that the expensive operation is not performed more than N times. Meaning, this is a very efficient way of randomizing an array.

注意:array.shuffle! 将是最有效的内置数组(就地)混洗的方法，因为它使用了现代版本的 Fisher-Yates:

Note: array.shuffle! will be the most efficient built-in way to shuffle an array (in-place) since it uses a modern version of 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;
}

这篇关于Ruby 的 sort_by {rand} 如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！