Come funziona Array # sort quando viene passato un blocco?

Question

Ho difficoltà a capire come funziona array.sort{ |x,y| block }, quindi come utilizzarlo?

Un esempio dal 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"] 

Answer 1

Nel tuo esempio

a.sort 

è equivalente a

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

Come sapete, di ordinare un array, è necessario essere in grado per confrontare i suoi elementi (se ne dubiti, prova a implementare qualsiasi algoritmo di ordinamento senza utilizzare alcun confronto , n. <, >, <= o >=).

Il blocco che fornisci è in realtà una funzione che verrà chiamata dalla sort algoritmo per confrontare due elementi. Cioè x e y saranno sempre alcuni elementi della matrice di input prescelto dal sort algoritmo durante la sua esecuzione.

Il sort algoritmo assume che questa funzione di confronto/blocco soddisferà i requisiti per il metodo <=>:

• ritorno -1 se x < y
• ritorno 0 se x = y
• ritorno 1 se x> y

Se non si fornisce una funzione/blocco di confronto adeguata, verrà generato un array di cui der è indefinito.

si dovrebbe ora capire perché

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

e

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

ritorno dello stesso array degli ordini opposti.

---

di elaborare su quello che Tate Johnson ha aggiunto, se si implementa la funzione di confronto <=> su uno qualsiasi dei corsi, si guadagna il seguente

1. Si può includere il modulo Comparable nella tua classe che in automatico verranno definire, per i seguenti metodi: between?, ==, >=, <, <= e >.
2. Le istanze della classe ora possono essere ordinate utilizzando l'invocazione predefinita (cioè senza argomento) a sort.

Si noti che il metodo <=> è già previsto ovunque ha senso nella libreria standard di Ruby (Bignum, Array, File::Stat, Fixnum, String, Time, ecc ...).

Answer 2

<=> è un metodo rubino che restituisce (self.<=>(argument))

• -1 se self < argomento
• 0 se self == argomento
• 1 se self> argomento

x e sono elementi di matrice. Se non viene fornito alcun blocco, la funzione sort utilizza x<=>y, altrimenti il ​​risultato del blocco indica che x deve essere prima di y.

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

Qui se some_very_complicated_method (x, y) restituisce smth che è < 0, x è considerato < di y, e così via ...

Answer 3

Quando si dispone di una serie di, diciamo, interi a sort, è abbastanza semplice per il metodo sort per ordinare correttamente gli elementi - numeri più piccoli prima, più grandi alla fine. Questo è quando usi il numero ordinario sort, senza blocco.

Ma quando si ordinano altri oggetti, potrebbe essere necessario fornire un modo per confrontare (ciascuno) due di essi. Supponiamo che tu abbia una serie di oggetti della classe Person. Probabilmente non è possibile stabilire se l'oggetto bob è maggiore dell'oggetto mike (ad esempio la classe Person non ha il metodo <=> implementato). In tal caso, dovrai fornire un codice per spiegare in quale ordine desideri ordinare questi oggetti al metodo sort. Ecco dove la forma del blocco calci

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

ecc In tutti questi casi, il metodo sort smista allo stesso modo -. Lo stesso algoritmo viene utilizzato. Ciò che è diverso è la logica di confronto.

Answer 4

Alcuni punti vari:

• x e y sono detti parametri di blocco. Il metodo di ordinamento in pratica dice "Ti darò xey, tu decidi se x o y dovrebbero venire prima, e mi occuperò delle cose noiose per quanto riguarda l'ordinamento"
• <=> è chiamato spaceship operator.

Answer 5

In:

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

ciò che è x e y?

x e y sono gli elementi confrontati dall'algoritmo di ordinamento.

Questo è utile per definire per classi personalizzate quale elemento deve essere prima dell'altro.

Per i dati di base (numeri, stringhe, data, ecc.) L'ordine naturale è predefinito, ma per l'elemento cliente (es. Dipendente) si definisce chi precede chi in un confronto. Questo blocco ti dà la possibilità di definirlo.

e cosa succede in y < => x?

Lì stanno confrontando gli elementi in ordine (quelli con valore "superiore" andrà prima) piuttosto che l'ordine naturale decrescente (x<=>y)

Procedimento <=> significa "compareTo" e ritorno 0 se gli elementi sono equivalenti, o < 0 se x va prima di y o > 0 se x va dopo y

Answer 6

credo | x, y | y < => x sta confrontando due elementi alla volta in ordine decrescente, come visto in: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-3C-3D-3E Dire con ["d", "a", "e", "c", "b"], "d" e "a" sembra essere prima comparato. Quindi, poiché è discendente, entrambi rimangono nello stesso ordine poiché d valuta meno di a. Quindi vengono valutati d ed e. "e" viene spostato nella posizione "d". Senza conoscere il funzionamento interno del codice c non è possibile sapere dove si è spostato, ma immagino che questo processo continui fino a quando tutti gli elementi sono ordinati. Le funzioni di 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); 
} 

Answer 7

@OscarRyz fornito risposte chiariti molto per me sulla questione su come funziona l'ordinamento, esp

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

Sulla base della mia comprensione sto fornendo qui ciò che lo stato della matrice sarebbe dopo ogni confronto per i risultati del blocco sopra.

Nota: Ottenuto il riferimento di stampare i valori di paramaters blocco e1, e2 da 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"] 

Uno stato matrice intuito in fase di esecuzione dopo ogni confronto:

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

Grazie,

Jignesh