Comment fonctionne Array#sort lorsqu'un bloc est transmis ?

Question

J'ai du mal à comprendre comment array.sort{ |x,y| block } fonctionne exactement, et donc comment l'utiliser ?

Un exemple de Documentation 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

Dans votre exemple

a.sort

est équivalent à

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

Comme vous le savez, pour trier un tableau, vous devez être en mesure de comparer ses éléments (si vous en doutez, essayez d'implémenter un algorithme de tri sans utiliser de comparaison, pas d'algorithme de tri). < , > , <= o >= ).

Le bloc que vous fournissez est en réalité une fonction qui sera appelée par l'application sort algorithme permettant de comparer deux éléments. C'est-à-dire x y y seront toujours des éléments du tableau d'entrée choisis par la fonction sort l'algorithme pendant son exécution.

En sort supposera que cette fonction/bloc de comparaison répondra aux exigences de la méthode <=> :

• retourner -1 si x < y
• retourner 0 si x = y
• retourner 1 si x > y

Si l'on ne fournit pas une fonction/bloc de comparaison adéquate, on obtient un tableau dont l'ordre est indéfini.

Vous devriez maintenant comprendre pourquoi

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

et

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

retournent le même tableau dans des ordres opposés.

---

Pour développer ce que Tate Johnson a ajouté, si vous implémentez la fonction de comparaison <=> sur l'une de vos classes, vous gagnez les éléments suivants

1. Vous pouvez inclure le module Comparable dans votre classe qui définira automatiquement pour vous les méthodes suivantes : between? , == , >= , < , <= y > .
2. Les instances de votre classe peuvent maintenant être triées en utilisant l'invocation par défaut (c'est-à-dire sans argument) de la fonction sort .

Notez que le <=> est déjà fournie partout où cela a un sens dans la bibliothèque standard de ruby ( Bignum , Array , File::Stat , Fixnum , String , Time etc...).

Answer 2

Lorsque vous avez un tableau de, disons, nombres entiers à trier, il est assez facile pour sort méthode permettant d'ordonner correctement les éléments - les petits chiffres en premier, les plus grands à la fin. C'est à ce moment-là que vous utilisez la méthode ordinaire sort sans blocage.

Mais lorsque vous triez d'autres objets, il peut être nécessaire de prévoir un moyen de comparer (chacun) de deux d'entre eux. Disons que vous avez un tableau d'objets de classe Person . Vous ne pouvez probablement pas dire si l'objet bob est supérieur à l'objet mike (c'est-à-dire la classe Person n'a pas de méthode <=> mis en œuvre). Dans ce cas, vous devrez fournir du code pour expliquer dans quel ordre vous voulez que ces objets soient triés. sort méthode. C'est là que la forme de bloc entre en jeu.

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

etc. Dans tous ces cas, sort les trie de la même manière - le même algorithme est utilisé. Ce qui est différent, c'est la logique de comparaison.

Answer 3

La réponse de @OscarRyz m'a permis d'éclaircir beaucoup de choses sur la question du fonctionnement du tri.

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

D'après ce que j'ai compris, j'indique ici quel serait l'état du tableau après chaque comparaison pour les résultats du bloc ci-dessus.

Remarque : Pour imprimer les valeurs des paramètres de bloc e1, e2 de l'application 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"]

Un état du tableau deviné au moment de l'exécution après chaque comparaison :

 [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)

Merci,

Jignesh

Answer 4

<=> est une méthode en ruby qui retourne ( self.<=>( argument ) )

• -1 si self < argument
• 0 si self == argument
• 1 si self > argument

x y y sont des éléments du tableau. Si aucun bloc n'est fourni, le sort la fonction utilise x<=>y sinon le résultat du bloc indique si x doit être avant y.

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

Ici, si une méthode très compliquée (x, y) renvoie quelque chose de < 0, x est considéré comme < à y et ainsi de suite...

Answer 5

Quelques points divers :

• x y y sont appelés paramètres de bloc. La méthode de tri dit essentiellement "Je vous donne x et y, vous déterminez si x ou y doit venir en premier, et je m'occupe des choses ennuyeuses en ce qui concerne le tri".
• <=> est appelé opérateur de vaisseau spatial .