Как работает Ruby's 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}

Эту технику иногда называют « преобразование Шварца ». Кэширование означает, что дорогостоящая операция выполняется не более 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

Answer 3

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 запоминает значение, возвращаемое блоком для каждого элемента, и сравнивает эти значения, знает, в каком порядке их размещать. Опасно, что вам больше не нужно повторяться.

Ваш случайный код работает, просто "составляя вещи", когда алгоритм сортировки уступает блоку. Вместо того, чтобы возвращать что-то разумное, блок возвращает случайное значение. Это приводит к тому, что алгоритм сортировки сортирует вещи случайным образом.

Answer 4

То, что делает sort_by, можно разделить на два простых шага:

1. Вызывает метод map / collect для предоставленного массива и с предоставленным блоком . В вашем случае результатом будет просто массив случайных чисел - назовем этот промежуточный массив A1. Обратите внимание, что он имеет длину исходного массива.

2. A1 сортируется нормально, но возвращается не отсортированный A1, а исходный массив, в котором элементы перемещаются так же, как соответствующие элементы из A1, пока он сортируется!

Вот как работает следующий пример:

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

Он сортирует слова по их длине, потому что сначала массив слов отображается в массив длин, а затем эти длины сортируются, а слова в исходном массиве перемещаются соответственно.