In occasione del Ruby Social Club milanese Matteo ci aveva proposto un problemino, che ri-riscrivo qui:
vogliamo ordinare un array in modo che tutti gli elementi X vengano prima di quelli Y.
Ad esempio, ordinare [1,2,3,4,5,6,7] in modo che tutti i dispari vengano prima dei pari: [1,3,5,7,2,4,6].
In spazio costante (quindi in place).
Come si fa con una partizione in tre (minori, medi, maggiori) ?
Matteo ci aveva presentato la cosa da un punto di vista interessante, ovvero quello dell’osservazione delle invarianti. Di recente ha parlato della stessa cosa (invarianti, non il giochino) al XP Day Benelux e ha postato slide & problemini che sono interessanti, e in questo modo mi ha fatto tornare in mente questo problema, che mi ero scordato continuamente.
La mia soluzione al problema
Quando ho cercato di risolvere questo problema son partito da questo codice:
def order(ary,&big)
start = 0
fin = ary.size-1
while start < fin
if big[ary[start]]
# this is big, we move it to end and ..
ary[start],ary[fin] = ary[fin], ary[start]
# ..skip end
fin = fin -1
else
# this is small and shall be here, we skip it
start = start+1
end
end
ary
end
Per ordinare un array composto da 1 e 2 si userebbe così:
tc do
def chk(*ary)
# the definition of the \"not small\" property
order(ary) {|x| x==2}
is ary.sort, ary # as assert_equal
end
t \"mini\" do
chk 1,2
end
t \"three els\" do
chk 1,2,2
end
t \"inverse\" do
chk 2,1
end
t \"middle\" do
chk 2,1, 2
end
t \"last \" do
chk 2, 2, 1
end
t \"middle 2 in 4 \" do
chk 1, 2, 2, 1
end
t \"two 1 in 4\" do
chk 2, 1, 1,2
end
t \"mixed\" do
chk 1, 2, 1, 1,2
end
t \"mixed large\" do
chk \"2 2 1 2 1 1 2 1\".split
end
end
Come estendo questa cosa a tre valori o n? Per pigrizia ho pensato di riusare tutto: l’ordinamento/partizionamento in 3 è semplicemente
- dividere tutti in piccoli e mediograndi
- dividere i mediograndi in medi e grandi
In codice, avendo fattorizzato la logica del metodo order in un helper, un ordinatore per 1,2 e 3 è semplice:
def order_helper(ary,start,fin,big)
while start < fin
if big[ary[start]]
# this is big, we move it to end and skip end
ary[start],ary[fin] = ary[fin], ary[start]
#skip end
fin = fin-1
else
# this is small and shall be here, we skip it
start = start+1
end
end
[ary,start,fin]
end
def order2(ary)
start = 0
fin = ary.size-1
_ , _, start = order_helper(ary,start,fin, proc {|x| x>1})
order_helper(ary,start,fin, proc {|x| x>2})
end
Questo codice fa esattamente quello che dicevamo: lavora sull’intero array per partizionare tra piccoli (gli 1) e mediograndi (2,3), poi lavora sul sub-array che inizia dalla fine dei piccoli per partizionare medi (2) e grandi (3).
E ovviamente i test
tc do
def chk(*ary)
order2(ary)
is ary.sort, ary
end
t \"sorted\" do
chk 1,2,3
end
t \"mixed\" do
chk 2,1,3
end
t \"reversed \" do
chk 3, 2,1
end
t \"half rev \" do
chk 3,1, 2
end
t \"five els \" do
chk 1,2, 3,1, 2
end
t \"large \" do
chk 1,2, 3,1, 2
end
t \"it still works with lesser arity sets!\" do
chk 2,2
end
end
Giovanni nella sua soluzione effettuava una partizione tra maschi (piccoli), femmine (grandi) e gender-neutral (medi). Ok chiaramente lui intendeva “gay”.
Da me diventerebbe questa:
def order_sex(ary)
start = 0
fin = ary.size-1
# put males at the start
_ , _, start = order_helper(ary,start,fin, proc {|x| x!='m'})
# put gays at the start of the end. No moral judgement intendend 
order_helper(ary,start,fin, proc {|x| x=='f'})
end
tc do
def chk(*ary)
order_sex(ary)
is ary.sort.reverse, ary
end
t \"gio 1\" do
chk(*%w(g g g g f f f m g f))
end
t \"gio 2\" do
chk(*%w(g m f g f g f g f m g f))
end
end
Sei un Deficiente! che è successo alla OOP?
Beh, due cose: primo non mi serviva, secondo non mi bastava.
Mi spiego, sarebbe banale spostare la definizione di big in un metodo di, diciamo, Integer piuttosto che Person, no?
No. Perché ovviamente il concetto di piccolo o grande è relativo alla dimensione della nostra partizione. Se per due valori basta avere piccolo e grande, per tre ci serve un medio, il che significa che dobbiamo ridefinire tutto e rompere le cose.
La soluzione, pensata qualche miliardo di anni fa, è di stabilire un ordinamento tra X e Y. Strano, vero, ma adesso ha senso tutta quella fuffa su <=>, cmp() etc, vero?
Solo che è noioso da fare per tipi generici quando non c’è il multiple dispatch _e_ i subset type stile perl6. Poi ne riparliamo.
Comunque si, si può fare ad oggetti. L’unico problema è che se introduciamo una relazione di ordine su cui basare la partizione allora avremo bisogno di controllare due elementi per volta (i.e. non possiamo dire array[x]!=2 ma dobbiamo dire array[x] != array[y]). Per ora sorvoliamo, poi ci torno.
Ma non siamo un po’ lenti?
Penso di si, in fondo questa cosa impiega un tempo N per scorrere l’array la prima volta, e un tempo N-S (tutti meno i numeri piccoli) per farlo la seconda volta.
Il numero di swap, immaginando sia l’operazione più costosa, è al max M+B (medi più grandi, primo loop) + B.
La soluzione di Giovanni invece fa tutto in un passaggio, il che per un sacco di tempo mi ha lasciato convinto che fosse largamente migliore. Però non ne sono sicuro: il loop è N, ma l’interno del loop ha un numero maggiore di confronti. Questo perché c’è quell’ if annidato. Ma non lo capisco bene, per cui, benchmark, con una lista creata così:
require 'benchmark'
n = 50000
Benchmark.bm do |x|
a=(\"m f g \"*150000).split
b= a.dup
x.report { 2.times{a.sex_partition}}
x.report { 2.times{b.order_sex}}
end
Sembra che la soluzione del nemico sia consistentemente più veloce della mia, cavolo
user system total real
5.500000 0.020000 5.520000 ( 5.601005)
4.820000 0.020000 4.840000 ( 4.918940)
Ingrandendo un po’ il set (150k a 200k):
user system total real
6.860000 0.030000 6.890000 ( 6.996474)
6.000000 0.030000 6.030000 ( 6.114625)
e un altro po’ (200k a 300k)
user system total real
12.050000 0.070000 12.120000 ( 12.287683)
10.620000 0.050000 10.670000 ( 10.937084)
Mannaggia, la mia soluzione è consistentemente la più lenta. Mh. consistententemente.
Eh si, sembra che tutte e due crescano allo stesso modo, e quindi la lentezza è overhead implementativo (probabilmente le proc, stupido ruby) e non algoritmica. Fico.
Tanto per verificare, ho provato a cambiare l’array aumentando il numero di femmine o di gay, e i cambiamenti sembrano nuovamente consistenti.
E, si, i risultati sono uguali, a parte quando ci sono input semi-invalidi (i.e. un array con soli tre maschi).
Si, lo so, sono assolutamente antiscientifico 
E che c’entra la storia delle invarianti?
Ah! Ne parlo la prossima volta, che adesso è ora di pranzo, c(hi)are fresche et dolci patate con i cavoli.
