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

Question

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

Пример из Ruby документации :

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

Answer 1

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

a.sort

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

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

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

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

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

• вернуть -1, если x
• вернуть 0, если x = y
• вернуть 1, если x> y

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

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

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

и

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

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

<Ч />

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

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

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

Answer 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 сортирует их одинаково - используется один и тот же алгоритм. Чем отличается логика сравнения.

Answer 3

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

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

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

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

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

Answer 4

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

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

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

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

Здесь, если some_very_complicated_method (x, y) возвращает что-то, что <0, x считается <чем y и так далее ... </p>

Answer 5

Несколько разных точек:

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

Answer 6

В:

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

что такое х и у?

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

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

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

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

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

Метод <=> обозначает «CompareTo» и возвращает 0, если элементы эквивалентны, или < 0, если x идет раньше, чем y, или > 0, если x идет после * 1033. *

Answer 7

Я верю | х, у | y <=> x сравнивает два элемента одновременно в порядке убывания, как показано в: http://www.ruby -doc.org / ядро-1.9.3 / Array.html # метод-я-3C-3D-3Е Предположим, что сначала сравниваются слова «[d», «a», «e», «c», «b»], «d» и «a». Тогда, так как он по убыванию, оба остаются в том же порядке, потому что d оценивается как меньше чем a. Затем d и e оцениваются. «е» перемещен в положение «д». Не зная внутренней работы кода 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);
}