PDI^2

Auguri bella gente, ci vediamo nel 2009.

Nel frattempo, potete controllare se questi tizi hanno effettivamente dimostrato che P=NP, causando il collasso della gerarchia polinomiale. Everything is possible, baby!

Scusate, vado di fretta, scriverò poi la seconda parte di quei tre post di cui ho scritto la prima, ora scrivo una prima parte di un post secondo me.

• Economia. Leggo un libro in cui è scritto che gli economisti sono scienziati, in quanto basano il loro approccio sul metodo scientifico: osserva, formula una teoria, sperimenta, correggi la teoria. Ovviamente, però non possono sperimentare quindi aspettano che gli capiti davanti un esperimento . Come gli astronomi, dice l’autore, anche quelli sono scienziati. Come gli astrologi, si potrebbe chiosare.
• Finanza. Il signor Madoff ha fregato il mondo con uno schema di ponzi, ovvero:
  

  ti do il 110 euro domani se me ne dai 100, tanto il tuo vicino me ne darà 100 perché io gliene do 110, perché il suo vicino me ne darà 100 visto che gliene do 110, perché il suo vicino..

  La cosa curiosa è vedere chi sono gli ingenui che hanno abboccato. HSBC, Santander, Nomura, RBS.
  Diciamoci la verità, il sor Madoff meriterebbe di cavarsela perché ha fregato gente che di professione deve solo non farsi fregare da queste cose. Peccato, adoro i piani ben riusciti.

• Culinaria. Credo di essere disposto a sposare una donna come questa solo perché mi prepari cestini per il pranzo così.
• Perl. Ho contribuito a Rakudo, la versione di perl6 che gira su parrot! La mia patch è orrenda ma fa passare dei test in più, tipo due. Lo so, Caro Lettore, che sei convinto che non vedrai mai perl6, per cui forse sarai stupito di scoprire che nella test suite del linguaggio ci sono circa 10k test e ne passano 7k
• Python. Intanto python 3 è ufficiale. Non sono convinto che nonlocal sia una buona idea, ma è comunque fico. Non abbastanza fico, però, sarà che già c’era un sacco di roba nella 2.6.
• Javascript. Simpatico podcast da James Robertson che stavolta intervista uno degli sviluppatori di mozilla riguardo TraceMonkey. Frase chiave:
  

  voglio dire, qui il mondo continua ad usare JavaScript che è un linguaggio disegnato davvero in due settimane

• Positivismo storico. La turchia usa la marina militare per bloccare navi che cercano petrolio a largo di cipro. In grecia continua una sommossa. In irlanda non si può più mangiare carne di maiale e manzo. A roma muore gente nel tevere che esonda (da quando si è iniziato a usare il termine “esondare”?). In Kosovo arrestano spie tedesche che mettono bombe (o arrestano poliziotti tedeschi che indagano sulla corruzione del novello stato criminale). Ciao diciannovesimo secolo, che piacere rivederti.
• Etimologico. De Mauro ammazza il dizionario online e lascia solo sinonimi e contrari. Nel frattempo Treccani mette online l’enciclopedia, con tanto di concorso, web tv, toolbar, social fuffa e programmi a lungo termine. Poteva andare peggio.
• Mozilla 1. Inoltro da pseudotecnico l’invito a fare questo sondaggino di mozilla sull’uso di FF nel vostro paese.
• Mozilla 2. E inoltro la scoperta di Perla Scandinava che commentava qua, bypassando i captcha, riguardo la scoperta di Webvisum, plugin per FF che risolve i captcha ottici, liberando persone con problemi di vista da tale idiozia (si lo so, essendo utente di blogsome dovrei stare zitto).
• Italiano. Su SvN chiedono se qualcuno abbia usato rosetta stone, un software per imparare le lingue che dalle demo sembra una figata. Questo è del tutto irrilevante, la cosa interessante è che su 69 persone che rispondono 12 dicono che stanno imparando o hanno imparato l’italiano. Notando che circa una persona su tre dice cosa sta imparando questo significa che il 40% degli americani web2.0 studia l’italiano.
• Ungherese. L’ungherese è huffman encoded, come molte lingue. Ma qua si esagera, al punto che siccome il caso comune di essere è alla terza persona, allora quando parli in terza persona puoi ometterlo. Cane bello. Cibo caldo. Il verbo avere è eliminato in quanto ridondante, basta dire esiste una casa mia, dove ovviamente esiste è optimized away nel secondo passaggio. Visto che la struttura del linguaggio è stack based tipo giapponese o FORTH mi chiedo se capire il compilatore di Factor potrebbe aiutare.
• Latino. Eo, is, ivi, itum, ire.

Piccolo post tanto per notificare i lettori che ancora non lo sapessero della possibilità di scaricare liberamente Higher Order Perl, un bellissimo libro che insegna ad usare perl5 in modo intelligente, non come un awk con la sintassi cambiata. “Cambiata” poi..

Ammetto che io leggendolo a volte mi son sentito uno snob, da nativo rubyista.. un intero capitolo dedicato a implementarsi gli iteratori? Davvero le dispatch tables meritano 22 pagine?
Ma mi rendo conto che in realtà il fatto che abbia già certe conoscenze non significa che siano banali, e MJD è un ottimo autore e gli esempi sono sempre interessanti quindi val la pena rileggerle. E poi viene fuori che alla fine non le conosco tanto bene.

Inoltre, i capitoli avanzati sono oggettivamente fichissimi: chi avrebbe pensato di sviluppare un software per disegnare diagrammi in ASCII spiegando la programmazione con vincoli?

Infine il libro va letto per tre motivi non tecnici.

Primo, il typesetting è bellissimo, se non sbaglio è una versione adattata di quello che si ottiene con ClassicThesis in LaTeX, o comunque qualcosa basato su gli elementi dello stile tipografico.

Secondo, la pagina about the cover, anche non voleste leggere il libro, anche non aveste idea di cosa è perl, non siete programmatori e non lo sarete mai, vi consiglio di leggere questa pagina.

Terzo, perché nella pagina per il download c’è una citazione geniale, che riporto qua in italiano perché so che non cliccate mai sui miei link, in risposta alla domanda perché ci è voluto tanto

[…]Ero.. rimasto senza benzina. Avevo una gomma a terra. Non avevo i soldi per prendere il taxi. La tintoria non mi aveva portato il tight. C’era il funerale di mia madre! Era crollata la casa! C’è stato un terremoto! Una tremenda inondazione!
LE CAVALLETTEEE!!!

Buona lettura

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.