PDI^2

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

1. dividere tutti in piccoli e mediograndi
2. 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.