Как работает сортировка Array # при передаче блока?

У меня проблема с пониманием того, как array.sort{ |x,y| block } работает точно, поэтому как его использовать?

Пример из Ruby documentation:

   a = [ "d", "a", "e", "c", "b" ]
   a.sort                     #=> ["a", "b", "c", "d", "e"]
   a.sort { |x,y| y <=> x }   #=> ["e", "d", "c", "b", "a"]

Ответы

Ответ 1

В вашем примере

a.sort

эквивалентно

a.sort { |x, y| x <=> y }

Как вы знаете, для сортировки массива вам нужно иметь возможность сравнивать его элементы (если вы сомневаетесь, просто попробуйте реализовать любой алгоритм сортировки без какого-либо сравнения, no <, >, <= или >=).

Предоставляемый вами блок - это действительно функция, которая будет вызываться алгоритмом sort для сравнения двух элементов. То есть x и y всегда будут некоторые элементы входного массива, выбранные алгоритмом sort во время его выполнения.

Алгоритм sort предполагает, что эта функция сравнения/блок будет соответствовать требованиям метода <=>:

  • return -1, если x < у
  • return 0, если x = y
  • return 1, если x > y

Невозможность обеспечить адекватную функцию сравнения/блок приведет к массиву, порядок которого undefined.

Теперь вы должны понять, почему

a.sort { |x, y| x <=> y }

и

a.sort { |x, y| y <=> x }

возвращает тот же массив в противоположных порядках.

Чтобы уточнить, что добавил Тейт Джонсон, если вы реализуете функцию сравнения <=> для любого из ваших классов, вы получаете следующее

  • Вы можете включить в свой класс модуль Comparable, который автоматически определит для вас следующие методы: between?, ==, >=, <, <= и >.
  • Экземпляры вашего класса теперь могут быть отсортированы с использованием вызова по умолчанию (т.е. без аргумента) на sort.

Обратите внимание, что метод <=> уже предоставляется везде, где он имеет смысл в стандартной библиотеке рубинов (Bignum, Array, File::Stat, Fixnum, String, Time и т.д.)).

Ответ 2

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

Но когда вы сортируете другие объекты, может потребоваться предоставить возможность сравнить (каждый) два из них. Скажем, у вас есть массив объектов класса Person. Вероятно, вы не можете определить, больше ли объект bob объекта mike (т.е. Класс Person не имеет метода <=>). В этом случае вам нужно предоставить некоторый код, чтобы объяснить, в каком порядке вы хотите, чтобы эти объекты отсортировались по методу sort. То, где формируется блок-блок.

people.sort{|p1,p2| p1.age <=> p2.age}
people.sort{|p1,p2| p1.children.count <=> p2.children.count}

и т.д.. Во всех этих случаях метод sort сортирует их одинаково - используется тот же алгоритм. Другое дело - логика сравнения.

Ответ 3

@OscarRyz ответ прояснил многое для меня по вопросу о том, как работает сортировка, esp

 { |x, y| y <=> x }

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

Примечание. Получена ссылка на печать значений параметров блока e1, e2 из ruby-forum

1.9.3dev :001 > a = %w(d e a w f k)
1.9.3dev :003 > a.sort { |e1, e2| p [e2, e1]; e2 <=> e1 }
["w", "d"]
["k", "w"]
["k", "d"]
["k", "e"]
["k", "f"]
["k", "a"]
["f", "a"]
["d", "f"]
["d", "a"]
["d", "e"]
["e", "f"]
 => ["w", "k", "f", "e", "d", "a"]

Угаданное состояние массива во время выполнения после каждого сравнения:

 [e2, e1]    Comparsion Result       Array State
["w", "d"]      1                   ["w", "e", "a", "d", "f", "k"]
["k", "w"]     -1                   ["w", "e", "a", "d", "f", "k"]
["k", "d"]      1                   ["w", "e", "a", "k", "f", "d"]
["k", "e"]      1                   ["w", "k", "a", "e", "f", "d"]  
["k", "f"]      1                   ["w", "k", "a", "e", "f", "d"]    
["k", "a"]      1                   ["w", "k", "a", "e", "f", "d"]  
["f", "a"]      1                   ["w", "k", "f", "e", "a", "d"]  
["d", "f"]     -1                   ["w", "k", "f", "e", "a", "d"]  
["d", "a"]      1                   ["w", "k", "f", "e", "d", "a"]  
["d", "e"]     -1                   ["w", "k", "f", "e", "d", "a"]  
["e", "f"]     -1                   ["w", "k", "f", "e", "d", "a"] (Result)

Спасибо,

Jignesh

Ответ 4

<=> - это метод ruby, который возвращает (self.<=>( argument ))

  • -1, если self < аргумент
  • 0, если аргумент self ==
  • 1, если self > argument

x и y - это элементы массива. Если блок не предусмотрен, функция sort использует x<=>y, в противном случае результат блока говорит, что если x должен быть до y.

array.sort{|x, y| some_very_complicated_method(x, y) }

Здесь, если some_very_complicated_method (x, y) возвращает smth, 0, х считается < чем у и т.д.

Ответ 5

Некоторые другие пункты:

  • x и y называются параметрами блока. Метод сортировки в основном говорит: "Я дам вам x и y, вы определяете, должен ли x или y быть первым, и я буду следить за скучным материалом в отношении сортировки"
  • <=> называется космическим кораблем.

Ответ 6

В:

a.sort {|x,y| y <=> x }   #=> ["e", "d", "c", "b", "a"]

что такое x и y?

x и y - элементы, которые сравниваются алгоритмом сортировки.

Это полезно определить для пользовательских классов, какой элемент должен быть перед другим.

Для базовых данных (числа, строки, дата и т.д.) естественный порядок предопределен, но для элемента клиента (т.е. Employee) вы определяете, кто идет до того, кто в сравнении. Этот блок дает вам возможность определить это.

и что происходит при y <= > x?

Там они сравнивают элементы в порядке убывания (те, у которых "высшее" значение будет идти первым), а не естественный порядок (x<=>y)

Метод <=> означает "compareTo" и возвращает 0, если элементы эквивалентны, или < 0, если x идет раньше, чем y или > 0, если x идет после y

Ответ 7

Я верю | x, y | y <= > x сравнивает два элемента за раз в порядке убывания, как видно из: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-3C-3D-3E Предположим, что сначала используются "d" , "a", "e", "c", "b" ], "d" и "a". Тогда, поскольку он нисходит, оба остаются в том же порядке, потому что d оценивается меньше, чем a. Затем оцениваются d и e. "e" перемещается в положение "d" . Не зная внутренней работы кода c, невозможно узнать, где находится d, но я считаю, что этот процесс продолжается до тех пор, пока все элементы не будут отсортированы. Функции c:

           VALUE
rb_ary_cmp(VALUE ary1, VALUE ary2)
{
    long len;
    VALUE v;

    ary2 = rb_check_array_type(ary2);
    if (NIL_P(ary2)) return Qnil;
    if (ary1 == ary2) return INT2FIX(0);
    v = rb_exec_recursive_paired(recursive_cmp, ary1, ary2, ary2);
    if (v != Qundef) return v;
    len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
    if (len == 0) return INT2FIX(0);
    if (len > 0) return INT2FIX(1);
    return INT2FIX(-1);
}