Как работает Ruby sort_by {rand}?

Ответ 1

В 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]}

• Быстрая сортировка Ruby выполняется на массиве, основанном на первом элементе: (обратите внимание, что внутренняя реализация далека от тривиальной и содержит тонну оптимизаций для уже упорядоченных массивов и т.д.)

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

  В грубом Ruby этот шаг: ary.sort{|x,y| x[0] <=> y[0]}

• Указатели копируются из нового отсортированного массива в правильное положение в исходном массиве.

  [1,3,2,4]
  

  В грубом Ruby этот шаг: ary.map{|x,y| y}

Этот метод иногда называют " Schwartzian Transform". Кэширование означает, что дорогостоящая операция выполняется не более 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;
}

Ответ 2

В блоке rand появляется ключ, который используется при сортировке. Он отличается каждый раз, когда он оценивается, поэтому вы получаете случайный порядок.

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

И вот какой-то еще более короткий, еще более четкий код:

someArray.shuffle

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

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

Ответ 4

Что sort_by можно разбить на два простых шага:

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

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

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

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

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