Newsgroup: it.lavoro.informatica
Titolo: A proposito dei libri/papers che tutti citano e nessuno legge

Se ne parlava con un collega francese, avete presente no? Una lista
d'esempio qui 
http://www.billthelizard.com/2008/12/books-programmers-dont-really-read.html
,
ma la si potrebbe estendere a molto altro (nei campi che mi
interessano, ad esempio, in troppi parlano di metodi formali, di
ricerche in psicologia e scienze cognitive, di apprendimento
automatico e non etc. senza mai aver letto davvero i testi/papers che
riportano come quello con cui "sono daccordo"/hanno studiato). Il
francioso mi ha fatto un esempio su come ha invogliato colleghi (e
studenti quando insegna) a rivedere la questione "goto" e mi ha
proposto questo test:
 
"Let X be an N by N matrix of integers.  Write a program that will
print the number of the first all-zero row of X, if any."
 
Senza fare alcuna ricerca sulla provenienza(!), chi vuole provi a
modellare il fattariello nei linguaggi (magari anche in quelli più
"antichi") che conosce.

 &quot;antichi&quot;) che conosce.
 
non l'ho provato, eh!! Sicuramente qualche cappella c'e', pero' pressappoco qualcosa del genere in c? Sarebbe interessante una versione concorrente, magari dove la matrice viene caricata in gpu ;-)
 
int getEmptyLine(int **I, int n){
  int line=-1;
  int i=0,j=0,s=0;
  for (i=0;(i<n)&&(line<0);i++){
    s=I[i][0];
    for(j=1;j<n;j++){
      s+=pow(I[i][j],2)
    }
    if (s<1)line=i;
  }
  return line;
}

   return line;
 
beh se cicli tutta la matrice non capisco perché scomodare pow() che
per di più trasforma interi in virgola mobile.
non basta uscire dal ciclo e scartare la riga al primo non-zero che
trovi?

 d'esempio qui 
http://www.billthelizard.com/2008/12/books-programmers-dont-really-read.html
,
 
Martin Fowler (citato) mi piace come scrive e l'ho aggiunto nella TODO
list. Insieme ci sono anche i Design Patterns (GoF), e Algorithms di
Sedgewick&Wayne che mi pare non siano citati.
 
Il problema è il tempo. Anche spizzicando a destra e a manca, è difficile.
 
Ste cose dovrebbero insegnarle obbligatoriamente fin dalle superiori, e
sicuramente all'università, invece delle cagate obsolete (io avevo il
Batini-Aiello...).
 
O forse sono troppo "vecchio" io... e adesso le insegnano!? :-(
 
Poi certo, entra in gioco la lingua...
 
M.

 &quot;antichi&quot;) che conosce.
 
 
La butto giu al volo
 
row:=1;
col:=1;
trovato= false;
 
while row <= n and not trovato do begin
   while matrix[row,col] = 0 and col<n do 
      inc(col);
   trovato=col > n;
   inc(row);
end;
   if trovato then write('la riga richiesta è '+row-1)
              else write('nessuna riga richiesta prevista');
 
Ciao
  Francesco

 &quot;antichi&quot;) che conosce.
 
La faccio dopo. Uhm... essendo che sia C che Python non hanno matrici (ma vettori di vettori) io lo farei così:
 
def getRowEmptyIndex(matrix):
    result = -1
    y = 0
    for row in matrix:
        if  [element for element in row if element != 0]:
           result = y
           break
        y += 1
    return result
 
probabilmente si può compattare ancora...
 
-- 
Ciao!
Luca

 
 
 
row=1
col=1
while $row <= N AND $col <= N {
	if A[$row][$col]!=0 {
		col=1; row++
		continue
	}
	else {col++}
	if $col==N return $row
}
return -1

 trovi?
 
per il pow, non pensavo necessariamente a quello di math.h, pensavo ad una funzione che semplicemente moltiplica n*n. Sarebbe interessante vedere se il processore impiega meno a fare il confronto tra due numeri o a sommarli/moltiplicarli, dipende dall'architettura. In realta' la moltiplicazione non e' neanche necessaria, un valore assoluto va bene uguale. Se la matrice e' positiva poi non c'e' neanche bisogno del valore assoluto. Ad ogni modo, e' vero che da un punto di vista pratico potrebbe essere conveniente metterci un CMP ad ogni iterazione. Non son sicuro che sia la strategia migliore quando devi parallelizzare in architetture tipo GPU, questo si che mi sarebbe d'interesse approfondire ;-)
 
 
 

Il giorno martedì 10 luglio 2012 17:50:17 UTC+2, askaholik ha scritto:
 
funzione che semplicemente moltiplica n*n. Sarebbe interessante vedere se il processore impiega meno a fare il confronto tra due numeri 
 
Per quel - MOLTO - poco che ho studiato di processori, il confronto è una roba ridicola, questione di un paio di cicli di clock... Pero' sto parlando dei vecchi 68000... ;-)
 
-- 
Ciao!
Luca

 per il pow, non pensavo necessariamente a quello di math.h, pensavo ad una funzione che semplicemente moltiplica n*n. Sarebbe interessante vedere se il processore impiega meno a fare il confronto tra due numeri o a sommarli/moltiplicarli, dipende dall'architettura. In realta' la moltiplicazione non e' neanche necessaria, un valore assoluto va bene uguale. Se la matrice e' positiva poi non c'e' neanche bisogno del valore assoluto. Ad ogni modo, e' vero che da un punto di vista pratico potrebbe essere conveniente metterci un CMP ad ogni iterazione. Non son sicuro che sia la strategia migliore quando devi parallelizzare in architetture tipo GPU, questo si che mi sarebbe d'interesse approfondire ;-)
 
Perchè non fare semplicemente la somma di tutti i numeri (interi)
della riga? Poi con una sola if vedi se la somma è zero, in tal caso
stampi l'indice ed esci, perchè si richiede solo la prima riga tutta a
zero.
 


 
select top 1 Riga
from X
group by Riga
having sum (Valore) = 0
order by Riga
 
dove X è una tabellina (Riga, Colonna, Valore).
 
:-)
 
 


resta il fatto che ciò che stai cercando è una riga con tutti zeri e 
procedendo per confronto ovviamente "cortocircuiti" al primo non-zero a 
differenza del tuo codice che processa ogni elemento. 
considerato poi che ciascuna riga è un array di n*sizeof(int) bytes direi 
che si potrebbe ottimizzare ancora: una memchr() adattata allo scopo che 
magari al suo interno scorre il blocco con un puntatore del tipo più 
intero grande per l'architettura scelta (tanto sempre zero/non-zero 
stiamo cercando... posso anche confrontarli a blocchi di ulong invece che 
di int).

 Non son sicuro che sia la strategia migliore quando devi parallelizzare in architetture tipo GPU, questo si che mi sarebbe d'interesse approfondire ;-)
 
Si c'è parecchio da approfondire e sperimentare (per la cronaca, la
cmp del vertex processor è comunque stra-usata, basta stare attenti a
pre-computare tutto quello che puoi prima).
 
 
Tornando al mini test, aspettiamo ancora qualche risposta che sono
curioso di vedere cos'altro salta fuori :)


Si, ai fini del mini-test si può assumere tranquillamente una matrice
di interi (uno e zero) e quindi fare come dici.


A quel punto occhio al data-alignment!

         if  [element for element in row if element != 0]:
if  not [element for element in row if element != 0]:
 
:)



 
O che è più corretto:
having min(Valore) = max(Valore) and min(Valore)  = 0
 
 

 A quel punto occhio al data-alignment!
 
si è vero, anzi sarebbe troppo dipendente dalla compilazione.
anche se... bisogna vedere in che modo costruisce la matrice. 
 

 if  not [element for element in row if element != 0]:
 
Eh, il not mi è rimasto nei ditini... ;-)
 
Che poi, pensavo, non è molto efficiente, perché valuta tutta la riga; mi sa che conviene un ciclo che si interrompe non appena trova un valore non zero.
 
-- 
Ciao!
Luca

 Che poi, pensavo, non è molto efficiente, perché valuta tutta la riga; mi sa che conviene un ciclo che si interrompe non appena trova un valore non zero.
 
OK, V2.0, vediamo che cosa ne viene fuori:
 
def getRowEmptyIndex(matrix):
    result = -1
    y = 0
    for row in matrix:
        nonZero = False
        for element in row:
             if element != 0:
                nonZero = True
                break
        if not nonZero:
           result = y
           break
        y += 1
    return result 
 
Infinitamente meno compatta, anzi, decisamente prolissa, ma dovrebbe ridurre l'uso di cicli di clock al minimo e valutare in modo più efficiente le righe.
 
-- 
Ciao!
Luca

 zero.
 
ottima se sono unsigned ;-) se sono signed, la somma puo' essere zero
anche senza aver alcun valore che e' zero (ad esempio {-2,1,-1,-1,3}
ha somma zero), per questo pensavo al quadrato o al valore assoluto

 ottima se sono unsigned ;-) se sono signed, la somma puo&#39; essere zero
 
Aggiungo: perché tanta paura dell'if? se è un confronto tra due interi, un processore se lo mangia in pochissimi cicli.
La somma ha il difetto che hai detto tu; la moltiplicazione è normalmente molto più affamata (sempre riferito ai Motorola 68000 industriali ;-) ).
 
Ciao!
Luca


Hai ragione, il quadrato o la potenza è più generale (forse l'abs è
più efficiente? boh).

 Aggiungo: perché tanta paura dell'if? se è un confronto tra due interi, un processore se lo mangia in pochissimi cicli.
 
E' vero se  l'intero è manipolato da una singola istruzione assembly,
se invece l'intero è qualcosa di più complesso non è detto sia così.
Per esempio un intero a 16 bit su un processore con word da 8 bit:
caso arcaico sui pc, ma comune anche oggi sui piccoli microcontroller.
Lì dovremmo vedere come il compilatore traduce la if in assembly,
probabilmente fa dei bei giretti contorti. Ma lo stesso se facciamo la
somma sulla riga.... Alla fine è tutto da valutare caso per caso, la
mini specifica dovrebbe diventare un manualetto :-)
 
 

 di interi (uno e zero) e quindi fare come dici.
 
In verità la specifica del minitest dice esattamente "Let X be an N by
N matrix of integers", immagino generici, non solo 0 od 1. L'idea
sarebbe che una add sia più efficiente di una if ripetuta su ogni
elemento (salvo il fatto che con la if puoi uscire precocemente dal
loop sulla riga , come dice bene rootkit, e perciò potresti guadagnare
efficienza per altra via).
Detto questo.... l'efficienza "depende" da mille fattori! :-) Per
esempio qual'è il grado di azzeramento medio della matrice, se è basso
l'ipotesi di if sul singolo elemento potrebbe essere meglio.
 

 curioso di vedere cos'altro salta fuori :)
 
io sono invece curioso di capire dove il "test" vuole andare a parare!
Risolto in assembler con un paio di linee di codice ed un goto? :-)
 
okay, back to work.
 

 Aggiungo: perché tanta paura dell'if? se è un confronto tra due interi, un processore se lo mangia in pochissimi cicli.
 
La pensavo cosi' sino a quelche giorno fa, poi un tizio pignolo m'ha
bacchettato per aver messo un if all'interno del ciclo su un problema
"simile" (matrice mooolto grossa con valori da processare uno a uno).
Visto che questo tipo sa quello che dice in termini di ottimizzazione
del codice, m'ha fatto venire la paranoia per gli if nei cicli.
In matlab, ad esempio, if e iterazioni rallentano che e' una bellezza,
che e' un altro motivo che mi motiva a ragionare in termini di
operazioni numeriche anzicche' selezioni/iterazioni quando si tratta
di matrici grosse.
 


E questo infatti è il primo "risultato" del mini test: di fronte alla
richiesta di un semplice algoritmo, l'attenzione è subito caduta
sull'efficienza (non espressamente richiesta), piuttosto che su
leggibilità del codice, verifiche/provabilità, etc... Come a dire: si
predica bene ma poi al momento di programmare si razzola sempre in
quella direzione :).

 trovi?
 
tagliando la testa al toro:
 
int getEmptyLine(int **I, int n){
  int line=-1;
  int i=0,j=0;
  bool s = 0;
  for (i=0;(i<n)&&(line<0);i++){
    s=(I[i][0]&&1);
    for(j=0; (j<n)&&(s = (I[i][j] && s)); j++ );
    if (s<1)line=i;
  }
  return line;

     for(j=0; (j<n)&&(s = (I[i][j] && s)); j++ );
 
gia', si era detto che si fermava quando son tutti zero, quindi
 for(j=0; (j<n)&&!(s = (I[i][j] && s)); j++ );

 quella direzione :).
 
Farei due osservazioni. La prima: nel caso in questione credo che
nemmeno si possa parlare di "algoritmo", tutti più o meno siamo
d'accordo sulla soluzione leggibile (i due cicli annidati con le if,
mi viene in mente quella di Francesco), magari con un'altra versione
per linguaggi funzionali. La seconda: la richiesta di efficienza non è
che viene dalla luna, è esperienza quotidiana. Perciò, perchè fare due
fasi distinte e se vuoi scolastiche (prima algoritmo generico, poi
ricerca di accorgimenti per efficientarlo) se già si sa in anticipo
che una certa impostazione è più efficiente?
Però hai ragione nel dire: qui non c'erano le specifiche
dell'ambiente, quindi tutti i tentativi di ottimizzazione sono campati
in aria.
Fermiamoci ai due cicli con la if.

"antichi") che conosce.
 
 
Dim n As Integer
        Dim X(n, n)
        '
        ' carica   X(n,n)
        '
        Dim i, j, nzeri, nriga As Integer
        For i = 1 To n
            nzeri = 0
            For j = 1 To n
                If X(i, j) <> 0 Then
                    Exit For
                End If
                nzeri += 1
            Next
            If nzeri = n Then
                nriga = i
                Exit For
            End If
        Next
        ' nriga adesso contiene  il valore cercato
 
Abbastanza antico?
 
 
ciao
fm 
 
 

"antichi") che conosce.
 
Per i linguaggi ....qui sotto ce ne sono 1471 fra antichi e moderni...:-)
 
http://99-bottles-of-beer.net/
 
 
 
 
ciao
fm 
 
 

 Abbastanza antico?
 
Mancano i numeri i riga... ;-)
 
-- 
Ciao!
Luca

 io sono invece curioso di capire dove il "test" vuole andare a parare!
 
Eccoci, il francioso dopo avermi proposto il test mi indica:
 
Marzo 1987, Rubin* scrive che la lettera sul goto del '68 di Dijkstra
ha fatto solo enormi danni, che non ci sono studi a supporto, etc.
quindi si arriva al mini-test e ci mostra i suoi risultati. Seguono le
risposte** ed infine Dijkstra stesso risponde***. Da leggere e
valutate attentamente ogni spiegazione/frammento di programma,
soprattutto le risposte a Rubin e l'analisi con le invarianti di
Dijkstra.
Un recap di McConnell alla fine di questa**** pagina.
 
Non conoscevo il "caso Rubin", me lo studierò la prima sera
disponibile per bene. E dal nostro thread che idea vi siete fatti? Io
mi aspettavo 0 goto's (check), più uso di flags, almeno una soluzione
folle in oop(!), almeno una soluzione di più alto livello ("almeno
una" inteso considerando le prevedibili poche risposte). Idee?
 
 
   * 
http://depcom.uqac.ca/~flemieux/PRO102/goto_Rubin.pdf
 
  ** 
http://wwwens.uqac.ca/~flemieux//PRO102/acm_may87.pdf
 
 *** 
http://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD1009.html
 
**** 
http://www.stevemcconnell.com/ccgoto.htm
 


 
C# + LINQ:
 
int[][] X = bla bla bla bla;
 
var index =
    X.
    Cast<int[]>().
    ToList().
    FindIndex(
     row => row.All(
      itemValue => itemValue == 0
     )
    );
 
Per l'implementazione vera e propria sono cavoli di LINQ... :-)
 

  ***
http://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD1009.html
 
 
LOL, Dijkstra ha massacrato sto Frank Rubin, e ha concluso dando una
soluzione iterativa, magari piu' formale ma del tutto simile a quelle
date qui sul NG, concludendo con "and for me this settles the
problem.". IMHO -tra le righe- gli ha detto "fatti meno pippe" LOL :-)
 
Piccola pipp..ehm...nota: anche Dijkstra ha usato variabili booleane
anzicche' gli if :-) Vabbe' che lui sicuramente l'ha fatto per onorare
il formalismo, ma di fatto evita di mettere if non necessari nei cicli
interni. Io uno l'ho messo nel ciclo piu' esterno, in realta' avrei
potuto(/dovuto?) cavare anche quello IMHO.
 
 


Ecco un esempio in Ocaml (funzionale) (chi conosce Ocaml perdonerà la
primitività :-):
 
let rec isZero row i =
		try
			match row.(i) with
				| 0 -> isZero row (i+1)
				| _ -> false
		with
			| Invalid_argument s -> true
 
 
let rec hasZeroRow mat i =
		let r = isZero mat.(i) 0 in
		try
			match r with
			| true -> i
			| false -> hasZeroRow mat (i+1)
		with
			| Invalid_argument s -> -1
 
uso:
hasZeroRow matrix 0
 
Nel caso di ricorsione viene spontaneo usare una condizione di uscita
anticipata.
Ma in realtà anche mettere i break, goto, iterate per anticipare
l'uscita da un ciclo è una forma di ottimizzazione, per quanto più
generica. A rigore non andrebbe messa se non richiesta dalla specifica
o dal linguaggio.


Per la verità avevo più in mente un Algol/Lisp/Fortran :)

 o dal linguaggio.
 
Beh non è detto, nel test d'esempio potrebbero esserci più rows nulle
nella matrice e il break mi consentirebbe di fermarmi alla prima,
quella corretta.

 potuto(/dovuto?) cavare anche quello IMHO.
 
Semplicemente, più ti attieni ad uno stile sequenziale dove ogni
statement S_i costa uno step in termini di ragionamento (evitando
quindi dove possibile le forme "if C then S_1 else S_2" che ne costano
evidentemente due di steps) e meno complesso sarà ragionare sul
risultato. Potuto/dovuto dipende, un conto è l'interrogativo
pragmatico che ti ponevi prima riguardo un if in un tight loop, un
altro è quello alla Dijkstra di creare un design il meno logicamente
complesso possibile in partenza.

 quella corretta.
 
Il fatto di non scorrerle tutte è solo un'ottimizzazione, però. Molto
ragionevole, certo.

 Poi certo, entra in gioco la lingua...
 
Con l'inglese (o quello che ti serve) bisogna insistere, deve essere
un appuntamento quotidiano.

 un appuntamento quotidiano.
 
Almeno su questo non transigo. E' divenuto un appuntamento più che
quotidiano.
Anche qui... molti errori sono stati fatti in passato, da parte mia e di
chi mi stava intorno.
 
M.

 ragionevole, certo.
 
Dipende sempre dall'algoritmo.
 
def f(X, ret=-1):
    for i,r in enumerate(X):
        if not filter(None,r):
            ret = i
            break
    return ret

 complesso possibile in partenza.
 
si, ma tutti e due concorrono alla soluzione del problema
<<ingegneristico>> che Rubin proponeva :-)

 quotidiano.
 
Ecco, sai qual è il problema? Che dovrei avere qualcuno di madre lingua con cui chiacchierare. Finché si tratta di leggerlo, problemi pochi; qualcuno di più, ma solo per abitudine, quando lo ascolto (e in effetti capisco di più la CNN che la BBC, o almeno li capivo quando c'erano su DTT).
 
In effetti, dovrei farmi qualche annetto di lavoro in USA...
 
-- 
Ciao!
Luca

 Infinitamente meno compatta, anzi, decisamente prolissa, ma dovrebbe ridurre l&#39;uso di cicli di clock al minimo e valutare in modo più efficiente le righe.
 
Mi sa che era meglio quella di prima con qualche aggiustatina. Per le performance, non parlare di "cicli di clock" (anche considerando lignuaggi nativi, chi è che ne parla ancora tranquillo tra branch prediction e compilazione?) ma osserva il bytesource delle due function e usa timeit per iniziare a farti un'idea.

 &lt;&lt;ingegneristico&gt;&gt; che Rubin proponeva :-)
 
Una tra "make it work, make it right, make it fast" e quella che ho proposto ai nuovi babbioni italiani/americani che sto aiutando* per me andrà bene.
 
* 1. correttezza; 2. espressività; 3. ...; n. (iff necessario) performance
 
 
p.s. meh. vorrei avere più tempo per discutere di tecniche e risorse sui metodi formali effettivamente utili, applicabili ed usati correntemente ma è troppo lungo il fatto.

 In effetti, dovrei farmi qualche annetto di lavoro in USA...
 
 
Credo ci sia in giro qualche sito che organizza chat on-line (con Skype
o affini) a scopi didattici a pagamento e non (il "non" credo sia
riservato solo a "studenti").
 
Questo perň č piů un argomento adatto all'altro thread "BBC: (Top)
Italian university switches to English" ...
 
 
M.

 &gt;
 
oh my questo nuovo Google Groups cos'è, già il vecchio era quello che era... :O

 Italian university switches to English&quot; ...
 
Ancora meglio chiedere su it.cultura.linguistica.inglese, tra l'altro frequentato anche da Adam Atkinson che ha sempre dispensato i migliori consigli (ascoltate Radio 4!).

 lungo il fatto.
 
gia', io in informatica mi affaccio ogni tanto, ma fondamentalmente mi
occupo di altro.