Siamo alla quarta puntata dedicata alla libreria CAPermutations, uno dei progetti a cui dedico il mio (poco) tempo libero. Trovate le puntate precedenti (nell'ordine) in questo, questo, e quest'altro post. Ancora un volta, ricordo che la libreria è liberamente utilizzabile nei propri programmi, purchè siano freeware e no-profit.

In questi giorni ho provato ad utilizzare le capacità combinatorie di CAPermutation per risolvere un problema combinatorio decisamente complesso, quello della enumerazione dei quadrati magici di ordine N. Per chi non lo sapesse, un quadrato magico è una griglia di NxN celle, ciascuna contenente un numero intero naturale compreso tra 1 e N*N (senza ripetizioni), in modo che la somma dei numeri lungo le N righe, le N colonne, e le due diagonali sia sempre uguale a un numero detto costante magica, il cui valore è pari a N * (N * N + 1) / 2. Ad esempio, la figura seguente mostra il primo dei quadrati magici di ordine 4 (corrispondente alla costante magica 34).

Questi quadrati si chiamano "magici" perchè nel Medioevo ad essi venivano attribuite delle proprietà, per l'appunto, magiche. Quadrati di ordine 3 e 4 si trovano spesso nascosti in dipinti e incisioni, ed esiste un bel po' di narrativa su questo tema - scientifica, mistica, e numerologica. Ma sembra che addirittura i primi a usare questi quadrati siano stati i Cinesi, almeno una decina secoli prima dell'era cristiana. Inutile dire che tramite Google potete trovare un sacco di riferimenti interessanti, incluso siti interamente dedicati all'argomento (ad es. Grogono Magic Squares)

Nel XXI secolo l'interesse per l'aspetto magico di questi quadrati è ovviamente molto scemato - anche se sicuramente esisteranno dei fanatici numerologi che non si sono accorti dei secoli che passano - mentre resta sicuramente l'interesse dal punto di vista computazionale. Come molti problemi di matematica ricreativa, la enumerazione di tali quadrati non ha alcuna applicazione pratica, eppure vi assicuro che se sapete impostare correttamente un programma di questo tipo allora siete in grado di risolvere anche una classe di problemi complessi di ottimizzazione molto più pratici e utili. A me sicuramente questo tipo di "ginnastica mentale" è servita tantissimo in mille progetti più commerciali.

Riducendo il problema all'osso, si tratta di trovare una permutazione dei numeri 1,2,.... N*N in grado di soddisfare il critero della somma costante lungo le righe, le colonne, e le diagonali. Ma già con i quadrati di ordine 4 si vede subito che occorre lavorare con ben 20,922,789,888,000 permutazioni, ovvero il fattoriale di 16. Incrementando N di una sola unità il numero cresce di ben 741,354,768,000 volte, e diventa pari a 15,511,210,043,330,985,984,000,000, ovvero oltre 15 milioni di miliardi di miliardi di combinazioni da analizzare!!! Un personal computer deve lavorare per alcune ore (e fare girare un programma super-ottimizzato) per arrivare alla conclusione che ci sono esattamente 68,826,306 quadrati magici di ordine 5, se si scartano le riflessioni e le rotazioni. A tutt'oggi il numero dei quadrati magici di ordine 6 è sconosciuto, e il loro numero è stato solo stimato. In altre parole, scrivete un programma per contare i quadrati magici di ordine 6 e passerete alla storia!

Lo scopo di questo articolo è, molto più mestamente e modestamente, mostrare come utilizzare la libreria CAPermutations per risolvere il problema dei quadrati magici di ordine 3, 4, e 5. E' anche pronto a risolvere il problema di ordine 6, ma probabilmente dovreste lasciare acceso il vostro PC per qualche secolo o millennio per poter davvero contare tutte le soluzioni. A dire il vero, io non ho neanche provato a enumerare tutte le soluzioni di ordine 5, che potrebbe richiedere anche un giorno o due di CPU.

E' abbastanza facile ereditare dalla classe Permutations<int> e imporre che i vincoli del problema siano rispettati ogni volta che viene aggiunto un numero alla grigia. Ecco la prima parte della classe:

public class MagicSquares : Permutations<int>
{
   // these fields are initialized by the constructor
   public readonly int Side;
   public readonly bool DiscardDerivates = true;
   private readonly int Length;
   private readonly int MagicSum;

   // these arrays contain the row/col corresponding to a given index
   public int[] IndexRow;
   public int[] IndexCol;

   // these fields are used by the filter method to keep track of how many elements are on each row, column, diagonal
   int[] rowCount;
   int[] colCount;
   int mainDiagCount;
   int secDiagCount;

   // these fields are used by the filter method and keep track of sums along rows, columns, and diagonals
   int[] rowSums;
   int[] colSums;
   int mainDiagSum;
   int secDiagSum;

   // the constructor 
   public MagicSquares(int side, bool discardDerivates) : base( CreateIndices(1, side*side), side*side, PermutationKind.Permutations, 1)
   {
      this.Side = side;
      this.DiscardDerivates = discardDerivates;
      this.Length = side * side;
      this.MagicSum = side * ( side * side + 1 ) / 2;
   }

Invece di generare tutte le permutazioni e poi scartare quelle che non vanno bene, il programma controlla per quanto possibile che i vincoli siano rispettati di volta in volta, ovvero cerca di potare l'albero delle soluzioni il prima possibile, in modo da scartare la maggior parte delle sequenze che non possono portare mai a dei risultati. Per questo motivo, i numeri sono posizionati sulla griglia secondo un ordine particolare, che dipende dalla dimensione del quadrato. Ad esempio, nel caso dell'ordine 4, sono prime sistemate i numeri nelle caselle d'angolo (perchè in questo modo è possibile scartare subito rotazioni e riflessioni), poi si completa la prima riga (riga 0), poi l'ultima riga (riga 3), poi la prima colonna e l'ultima colonna (colonna 0 e colonna 3), e infine le caselle non ancora riempite in riga 1 e 2. Per determinare quale ordine seguire, la classe utilizza due array, IndexRow e IndexCol, in modo che l'elemento IndexRow[n] contiene il numero di riga della N-simo numero posto sulla griglia, e IndexCol[n] la sua colonna. Per inizializzare questi array e le altre variabili usate durente il backtracking si fa l'override del metodo OnInitialize:

// init the fields and counters used by the filter method

protected override PermutationResult OnInitialize()
{
   // init index*** fields
   IndexRow = new int[Length];
   IndexCol = new int[Length];

   // but next, refill the same arrays again with sequences optimized for each value of Side
   // it is essential that the first four elements are the four corners, in this order
   // top-left, top-right, bottom-left, bottom-right
   if ( Side == 3 )
   {
      // optimized case when side = 3
      IndexRow = new int[] { 0, 0, 2, 2, 1, 0, 1, 1, 2};
      IndexCol = new int[] { 0, 2, 0, 2, 1, 1, 0, 2, 1};
   }
   else if ( Side == 4 )
   {
      // optimized case when side = 4
      // four corners + row 0 + row 3 + col 0 + col 3 + row 1 + row 2
      IndexRow = new int[] { 0, 0, 3, 3, 0, 0, 3, 3, 1, 2, 1, 2, 1, 1, 2, 2};
      IndexCol = new int[] { 0, 3, 0, 3, 1, 2, 1, 2, 0, 0, 3, 3, 1, 2, 1, 2};
   }
   else if ( Side == 5 )
   {
      // optimized case when side = 5
      // four corners + main diag + sec diag + row 1 + col 1 + col 3 + row 4 + row 2 + col 2 + row 1 + row 3
      IndexRow = new int[] { 0, 0, 4, 4, 1, 2, 3, 1, 3, 0, 0, 0, 2, 4, 2, 4, 4, 2, 2, 1, 3, 1, 1, 3, 3};
      IndexCol = new int[] { 0, 4, 0, 4, 1, 2, 3, 3, 1, 1, 2, 3, 1, 1, 3, 3, 2, 0, 4, 2, 2, 0, 4, 0, 4};
   }
   else if ( Side == 6 )
   {
      // optimized case when side = 6
      // four corners + row 0 + row 5 + col 1 + col 4 + main diag + sec diag + row 2 + row 3 + col 0 + col 5 + row 1 + row 4
      IndexRow = new int[] { 0, 0, 5, 5, 0, 0, 0, 0, 5, 5, 5, 5, 1, 2, 3, 4, 1, 2, 3, 4, 2, 3, 2, 3, 2, 2, 3, 3, 1, 4, 1, 4, 1, 1, 4, 4 };
      IndexCol = new int[] { 0, 5, 0, 5, 1, 2, 3, 4, 1, 2, 3, 4, 1, 1, 1, 1, 4, 4, 4, 4, 2, 3, 3, 2, 0, 5, 0, 5, 0, 0, 5, 5, 2, 3, 2, 3 };
   }
   else
   { 
      // unsupported side
      throw new Exception("Unsupported Side value");
   }

   // init other values used by the filter
   rowCount = new int[Length];
   colCount = new int[Length];
   mainDiagCount = 0;
   secDiagCount = 0;
   // initialize ***sum fields
   rowSums = new int[Side];
   colSums = new int[Side];
   mainDiagSum = 0;
   secDiagSum = 0;
   // signal it's ok to proceed
   return PermutationResult.Proceed;
}

Il metodo di filtro deve controllare se la permutazione parziale appena generata dalla classe base soddisfa i vincoli. Invece però di contare ogni volta le somme lungo righe, colonne e diagonali, il programma conserva le somme parziali nelle variabili ***Sums, mentre nelle variabili ***Count conserva il numero di celle riempite lungo le stesse righe, colonne e diagonali. Una permutazione viene scartata quando il numero appena aggiunto completa una riga, colonna, o diagonale ma la somma dei numeri su quella riga, colonna o diagonale non corrisponde alla costante magica. In alcuni casi, pero', è possibile scartare un numero anche se non completa una riga, colonna o diagonale: questo avviene quando la somma dei valori lungo la riga, colonna o diagonale è già superiore alla costante magica. Per controllare e scartare le permutazioni occorre fare l'override del metodo OnNewPermutations:

protected override PermutationResult OnNewPermutation(int[] permutation, int level)
{
   // this is the element just added
   int number = permutation[level];
   // evaluate row and col of the element just added
   int row = IndexRow[level];
   int col = IndexCol[level];
   // detect whether the number is on the main or secondary diagonal
   bool onMainDiag = ( row == col );
   bool onSecDiag = ( row == ( Side - 1 - col ) );

   // check sum of value along the current row
   if ( rowCount[row] == Side - 1 )
   {
      // if the element completes a row, the sum along the row must be equal to the magic sum
      if ( rowSums[row] + number != MagicSum )
         return PermutationResult.Backtrack;
   }
   else
   {
      // if the element doesn't complete a row, the sum along the row must less than magic sum
      if ( rowSums[row] + number >= MagicSum )
         return PermutationResult.Backtrack;
   }

   // check sum of values along the current column
   if ( colCount[col] == Side - 1 )
   {
      // if the element completes a column, the sum along the column must be equal to the magic sum
      if ( colSums[col] + number != MagicSum )
         return PermutationResult.Backtrack;
   }
   else
   {
      // if the element completes a column, the sum along the column must be less than the magic sum
      if ( colSums[col] + number >= MagicSum )
         return PermutationResult.Backtrack;
   }

   // if the element is on the primary diagonal
   if ( onMainDiag )
   {
      if ( mainDiagCount == Side - 1 )
      {
         // if the element completes the diagonal, the sum along the diagonal must be equal to the magic sum
         if ( mainDiagSum + number != MagicSum )
            return PermutationResult.Backtrack;
      }
      else
      {
         // if the element doesn't complete the diagonal, the sum must be less than the magic sum
         if ( mainDiagSum + number >= MagicSum )
            return PermutationResult.Backtrack;
      }
   }

   // if the element is on the secondary diagonal
   if ( onSecDiag )
   {
      if ( secDiagCount == Side - 1 )
      {
         // if the element completes the diagonal, the sum along the diagonal must be equal to the magic sum
         if ( secDiagSum + number != MagicSum )
            return PermutationResult.Backtrack;
      }
      else
      {
         // if the element doesn't complete the diagonal, the sum must be less than the magic sum
         if ( secDiagSum + number >= MagicSum )
            return PermutationResult.Backtrack;
      }
   }

   // if we get here, the permutation is ok and we can update partial sums
   rowCount[row]++;
   rowSums[row] += number;
   colCount[col]++;
   colSums[col] += number;
   if ( onMainDiag )
   {
      mainDiagCount++;
      mainDiagSum += number;
   }
   if ( onSecDiag )
   {
      secDiagCount++;
      secDiagSum += number;
   }

   // signal that new permutation is ok
   return PermutationResult.Proceed;
}

In realtà si potrebbe scrivere del codice ancora più ottimizzato, che sia in grado di scartare una permutazione anche quando manca un solo elemento per completare una riga, colonna o diagonale - basta controllare che la differenza tra la somma corrente e la costante magica corrisponde a un numero non ancora utiizzato - ma non ho voluto complicare troppo il codice. L'ultima cosa che resta da fare è l'override del metodo OnBacktrack, per aggiornare i vari vettori quando in fase di backtracking un numero viene tolto dalla griglia:

protected override PermutationResult OnBacktrack(int[] permutation, int level)
{
   // this is the element to be removed
   int number = permutation[level];
   // evaluate row and col of the element 
   int row = IndexRow[level];
   int col = IndexCol[level];
   // detect whether the number is on the main or secondary diagonal
   bool onMainDiag = ( row == col );
   bool onSecDiag = ( row == ( Side - 1 - col ) );
   // updates counters and return 
   rowCount[row]--;
   rowSums[row] -= number;
   colCount[col]--;
   colSums[col] -= number;
   if ( onMainDiag )
   {
      mainDiagCount--;
      mainDiagSum -= number;
   }
   if ( onSecDiag )
   {
      secDiagCount--;
      secDiagSum -= number;
   }
   return PermutationResult.Backtrack;
}

Il programma completo - che include anche il codice per scartare rotazioni e riflessioni - è disponibile in sorgente a questo link: MagicSquares.zip (70.2 KB). Lo zippone comprende anche le versioni più recenti dei programmi che ho mostrato nei precedenti articoli, il tutto in un unico progetto Visual Studio 2005.

UPDATE: dopo aver messo online questo articolo ho modificato leggermente la libreria CAPermutations, e il link ora punta alla versione aggiornata. Tutto quanto scritto nel post originario resta valido, eccetto che i metodi in override restituiscono un enumerativo anzichè un booleano.

Nel primo e nel secondo post di questa serie ho introdotto la libreria CAPermutations e ho mostrato come sia in grado di risolvere alcuni problemi combinatori classici, tipo la generazione di anagrammi e il problema delle regine e amazzoni. In questo articolo mostrerò alcune altre feature molto interessanti di questa libreria e le userò per realizzare un semplice - ma potente e super-efficiente - programma per lo sviluppo di sistemi Totocalcio.

Prima di tutto un veloce ripasso. Come ho mostrato nei precedenti esempi, il costruttore della classe Permutations riceve in input i seguenti argomenti, tutti opzionali eccetto il primo:
1. l’array degli elementi da permutare
2. il numero di elementi che dovranno apparire nella permutazione
3. un enumerativo che indica se desideriamo listare le permutazioni o le combinazioni degli elementi
4. il numero massimo di occorrenze di ciascun elemento
5. l’indirizzo di un metodo di filtro

Ecco ad esempio il codice che permette di generare tutte le parole di cinque lettere e contenenti esclusivamente i caratteri A-G, dove ciascun carattere non può comparire più di due volte:

char[] elements = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
Permutations<char> perms = new Permutations<char>(elements, 5, PermutationKind.Permutations, 2);
foreach ( char[] chars in perms )
   Console.WriteLine(new string(chars));

In aggiunta ai dati che si passano al costruttore, è però possibile impostare numerosi altri campi della classe dopo averla istanziata. In particolare, la classe espone gli array MinOccurrences e MaxOccurrences, che permettono di impostare il numero minimo e massimo di occorrenze di ciascun elemento nel risultato finale. Per default, tutti gli elementi del vettore MinOccurrences sono impostati a zero e tutti gli elementi di MaxOccurrences sono uguali al valore del 4° argomento passato al costruttore – il che di fatto significa che non imponiamo alcun vincolo specifico al numero di occorrenze - ma dopo aver creato una istanza di Permutations è possibile modificare questi array per imporre delle condizioni particolari.

Ad esempio, possiamo affinare il codice precedente specificando che i caratteri ‘A’ e ‘E’ devono essere sempre presenti e anzi possono comparire fino a tre volte, mentre il carattere ‘B’ può comparire al massimo una volta:

char[] elements = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
Permutations<char> perms = new Permutations<char>(elements, 5, PermutationKind.Permutations, 2);
perms.MinOccurrences[0] = 1; // 0 = index of char 'A' in the elements array
perms.MaxOccurrences[0] = 3;
perms.MaxOccurrences[1] = 1; // 1 = index of char 'B' in the elements array
perms.MinOccurrences[4] = 1; // 4 = index of char 'E' in the elements array
perms.MaxOccurrences[4] = 3;
foreach ( char[] chars in perms )
   Console.WriteLine(new string(chars));

L’oggetto Permutation espone anche il vettore MaxConsecutiveOccurrences, che indica per ciascun elemento quante occorrenze consecutive possono trovarsi nel risultato. Quindi ad ad esempio possiamo scartare AABCD ma accettare ABACD usando questo codice:

// aggiungere a tutti i vincoli precedenti...
perms.MaxConsecutiveOccurrences = new int[] {1, 1, 1, 1, 1, 1, 1};
foreach ( char[] chars in perms )
   Console.WriteLine(new string(chars));

A cosa può servire impostare il numero massimo di occorrenze consecutive? Ad esempio, se i caratteri A-G rappresentano altrettante città, l’output del codice precedente rappresente tutti i percorsi possibili che potete seguire per visitarne alcune di esse (massimo 5), ripassando se necessario fino a tre volte per A oppure E, oppure fino a due volte per tutte le altre città eccetto B. Visto che le permutazioni rappresentano un tratto di viaggio, occorre scartare le tratte che cominciano e terminano nella stessa città, cosa che si fa appunto impostando pari a 1 il valore di MaxConsecutiveOccurrences per tutti gli elementi.

Così formulato, l’esempio può sembrare poco realistico, ma nel settore dei problemi combinatoriali imporre un limite massimo alle occorrenze consecutive può essere molto utile. Ad esempio, nella stesura di un orario scolastico di solito si impone che un professore non possa occupare la stessa aula per più di due ore oppure che gli alunni di una determinata classe non possano occupare un laboratorio per più di un numero stabilito di ore. Vedremo anche tra un attimo che i vettori MinOccurrences, MaxOccurrences, e MaxConsecutiveOccurrences saranno molto utili nella preparazione di un programma per lo sviluppo dei sistemi di totocalcio.

Una feature molto potente della classe Permutations è la possibilità di indicare esattamente quali elementi si possono trovare in determinate posizioni del risultato. Tornando a considerare l’esempio precedente, potremmo voler imporre che il nostro viaggio tra le città A-G possa cominciare e terminare solo dalle città A, D e E, perchè sono le uniche che sono servite da un aereoporto. Una possibile soluzione al problema è di impostare un metodo di callback che scarta tutte le permutazioni che non soddisfano questa condizione, ma è molto più facile agire sul campo ValidIndices della classe Permutations. Questo campo è un vettore di vettori di tipo T (dove T è il tipo parametro della classe generica Permutations), quindi occorre modificare l’elemento con indice 0 (che contiene gli indici validi che può assumere l’elemento nella prima posizione del risultato) e l’elemento 4 (che contiene gli indici validi che può assumere il quinto e ultimo elemento del risultato).

// aggiungere a tutti i vincoli precedenti...
//
// indica che il primo e ultimo elemento della soluzione
// deve essere scelto tra A,D,E, che nel vettore elements
// si trovano agli indici 0,3,4
perms.ValidIndices[0] = new int[] { 0, 3, 4 };
perms.ValidIndices[4] = new int[] { 0, 3, 4 };
foreach ( char[] chars in perms )
   Console.WriteLine(new string(chars));

Passiamo ora ad una applicazione pratica “seria”, benchè dedicata al gioco del Totocalcio. Attualmente il Totocalcio non è più un gioco molto popolare, ma quelli di voi con più di vent’anni si ricorderanno sicuramente la rivoluzione che il personal computer portò nel mondo degli scommettitori “professionali”. Improvvisamente era possibile impostare, sviluppare e ridurre un sistema di Totocalcio comodamente a casa propria, e magari stampare pure le schedine su una apposita stampante. Ricordo numerose software house che negli anni ’80 avevano a catalogo programmi di questo tipo, e per molti sviluppatori questo tipo di software ha rappresentato una grande fonte di reddito.

Certo, resta valida la ovvia considerazione che se un programmatore trovasse davvero la “sistema perfetto” per azzeccare il 13 (anzi il 14, visto che da qualche anno si gioca su 14 partite...) allora potrebbe fare molti più soldi giocando il sistema perfetto egli stesso, piuttosto che vendere il software. Ma questo è un dettaglio: quello che è importante in questa sede è che lo sviluppo di sistemi di Totocalcio (ma anche di altri giochi simili, come il Totip e il TotoGol) rappresenta un irresistibile banco di prova per chi si diletta di calcolo combinatorio.

La figura seguente mostra la videata principale (nonchè l’unica ) del programma per lo sviluppo di sistemi Totocalcio che potete scaricare in sorgente da questo link: SistemaTotocalcio.zip (55.56 KB). Il file contiene anche la nuova versione della libreria CAPermutations (che è stata finalmente arricchita dai commenti XML dei vari metodi e campi) e delle altre demo già mostrate dei post precedenti. Ricordo che la libreria è usabile liberamente nei propri programmi freeware e no-profit ma potete contattarmi se volete utilizzarla in altri contesti.

Un breve disclaimer prima di continuare: spero sia chiaro che la mia intenzione non è di creare un programma professionale per lo sviluppo di sistemi, anche perchè ce ne sono di ottimi in giro. Il mio unico obiettivo è di mostrare come risolvere il problema combinatorio legato a questo gioco utilizzando la libreria CAPermutations.

Come vedete, il programma permette di impostare il pronostico sulle 14 partite, e una serie di vincoli, tra cui il numero minimo, massimo e massimo consecutivo dei tre segni.

Lo scommettitore dovrebbe impostare i 14 pronostici indicando come primo simbolo (il simbolo principale) il risultato più probabile; come secondo simbolo un risultato prevedibile ma non quanto il simbolo principale; come terzo simbolo quello che lo scommettitore considera una vera e propria sorpresa. Agendo sui controlli nel gruppo “Varianti e sorprese” lo scommettitore può dosare in un certo senso il grado di “imprevedibilità” su cui vuole puntare. È evidente, ad esempio, che se impostando un valore alto come numero minimo di varianti o di sorprese, si ottiene di ridurre notevolmente il numero di colonne dello sviluppo (e quindi la probabilità di vincere) ma in compenso si punta ai risultati meno prevedibili e quindi che potenzialmente potrebbero dare una vincita più alta della media.

Vediamo ora una breve descrizione di come funziona il programma dietro le quinte. Lo sviluppo di un sistema di Totocalcio si riduce in un certo senso a creare tutte le permutazioni dei simboli 1, 2, e X. Per comodità, internamente il programma non permuta questi caratteri ma più semplicemente le cifre 0 (corrispondente al segno ’1’), 1 (corrispondente al ’2’) e 2 (corrispondente al simbolo ’X). Il programma non deve creare davvero tutte le permutazioni delle triple ‘12X’, ma solo le permutazioni che rispondono ai pronostici delle partite, cosa che il codice fa assegnando valori adeguati agli elementi del vettore ValidIndices. Ad esempio, per specificare che per la quarta partita i simboli validi sono sono 1 e X (vedi figura) il codice esegue qualcosa del genere:

perms.ValidIndices[3] = new int[] { 0, 2 };

mentre per la quinta partita (il cui pronostico è ‘1X2’) il codice è il seguente:

perms.ValidIndices[3] = new int[] { 0, 2, 1 };

(notate quindi che è anche possibile impostare sequenze di indici non crescenti).

Grazie alla presenza dei campi ValidIndices, MinOccurrences, MaxOccurrences, e MaxConsecutiveOccurrences, la maggior parte dei vincoli legati allo sviluppo del sistema sono di fatto implementati dalla classe Permutations. Gli unici vincoli che la classe base non risolve sono quello sul numero minimo e massimo di segni principali, varianti, e sorprese, ma anche questi vincoli si implementano facilmente.

Infatti, la classe Permutations espone il vettore Indices, che per ciascuna partita indica la posizione in ValidIndices del simbolo inserito nella soluzione. Quindi contare quante varianti sono presenti nella soluzione corrente significa contare – nel metodo di filtro - quanti elementi pari a 1 sono presenti nel vettore Indices. E contare quante sorprese vi sono corrisponde a contare gli elementi del vettore pari a 2.

Se a questo punto non riuscite più a seguire la mia descrizione non vi preoccupate: il problema non è affatto banale e la cosa migliore da fare è studiare il sorgente della classe SistemaTotocalcio. Questa classe eredita da Permutations<int> e aggiunge un paio di vettori che conservano il valore minimo e massimo di segni principali, varianti e sorprese:

public class SistemaTotocalcio : Permutations<int>
{
   const int NumPartite = 14;

   // valori usati per il filtro del sistema
   public int[] MinVarianti = new int[3];
   public int[] MaxVarianti = new int[3];

   // questo è il numero di varianti (privato, perchè usato solo dal filtro)
   // varianti[0] sono le principali, varianti[1] le varianti, varianti[2] le sorprese
   private int[] Varianti = new int[3];

   // il costruttore non ha argomenti
   public SistemaTotocalcio()
      : base( new int[] { 0, 1, 2}, NumPartite, PermutationKind.Permutations, NumPartite)
   {
      // imposta il valore max di varianti (modificabile in seguito dal client)
      for ( int i = 0; i <= 2; i++ )
         this.MaxVarianti[i] = NumPartite;

      // tutti gli altri array sono correttamente inizializzati
   }

   // ... (continua)....

Quando parte il computo delle permutazioni – ovvero delle colonne generate dallo sviluppo del sistema – occorre inizializzare il vettore Varianti, che viene usato poi dal filtro. Questo si ottiene facendo l’override del metodo OnInitialize, che è chiamato al momento opportuno dalla classe Permutations. Questo metodo deve restituire PermutationResult.Proceed se i dati in input sono OK, oppure PermutationResult.Cancel se vi è un problema e l'enumerazione non deve neanche partire:

   // override del metodo per validare i dati e
   // inizializzare i valori usati dal filtro
   protected override PermutationResult OnInitialize()
   {
      // inizializza l'array Varianti e indica che si può proseguire
      this.Varianti = new int[3];
      return PermutationResult.Proceed
   }

Poichè la classe SistemaTotocalcio eredita da Permutations, per filtrare le permutazioni man mano che vengono generate non si usa un metodo di callback, ma si deve fare l’override del metodo protetto OnNewPermutation. Come ho spiegato sopra, il controllo sul numero minimo, massimo e massimo consecutivo dei segni lo fa la classe base Permutations, quindi nel filtro dobbiamo solo controllare il valore minimo e massimo dei segni principali, delle varianti e delle sorprese.

   // il filtro, sotto forma di override

   protected override PermutationResult OnNewPermutation(int[] colonna, int partita)
   {
      // questo è l'indice usato per questa partita (0=princ, 1=variante, 2=sorpresa)
      int index = base.Indices[partita];
      // esci se vi sono già troppe varianti di questo tipo
      if ( Varianti[index] >= MaxVarianti[index] )
         return PermutationResult.Backtrack;

      // aggiornal il contatore delle varianti di questo tipo
      Varianti[index]++;
      // restituisci false se il numero di varianti è minore del minimo
      // e non potrebbe diventare mai pari o maggiore del
      // minimo perchè non ci sono sufficienti partite da analizzare
      int rimaste = 13 - partita;
      if ( Varianti[0] + rimaste < MinVarianti[0] || Varianti[1] + rimaste < MinVarianti[1]
         || Varianti[2] + rimaste < MinVarianti[2] )
      {
         // ripristina il valore precedente prima di restituire false
         Varianti[index]--;
         return PermutationResult.Backtrack;
      }

      // restituisci di procedere se tutti i vincoli sono soddisfatti
      return PermutationResult.Proceed;
   }

Ricordo che il filtro viene chiamato ogni volta che la classe base prova a mettere un simbolo per la partita N-esima nel risultato (ossia nel vettore colonna), scegliendolo però tra i simboli validi specificati in ValidIndices[partita]. Invece di ricalcolare il numero di segni principali, varianti e sorprese ad ogni chiamata del metodo OnNewPermutations, la classe SistemaTotocalcio tiene traccia di questi valori nel vettore Varianti, dove Varianti[0] è il numero dei segni principali, Varianti[1] delle varianti, e Varianti[2] delle soprese.

Per mantenere sempre aggiornato questo vettore è necessario che i suoi elementi siano aggiornato in fase di backtracking, ovvero quando la classe base “toglie” un simbolo sistemato precedentemente. La classe SistemaTotocalcio implementa il backtracking facendo l’override del metodo protetto OnBacktrack:

   // backtracking 
   protected override PermutationResult OnBacktrack(int[] colonna, int partita)
   {
      // questo è l'indice usato per questa partita (0=princ, 1=variante, 2=sorpresa)
      int index = base.Indices[partita];
      // ripristina il contatori di Varianti ed esci
      Varianti[index]--;
      return PermutationResult.Backtrack;
   }
} // fine della classe SistemaTotocalcio

In definitiva, grazie alla classe Permutations è stato possibile risolvere un problema combinatorio davvero complesso con appena una ventina di istruzioni eseguibili!

La cosa a mio avviso davvero notevole è che, nonostante il fatto che la classe Permutations sia molto generica e sia in grado di risolvere problemi combinatori anche molto differenti tra loro, le prestazioni che si ottengono sono eccezionali. Sul mio desktop, un Pentium D a 2.80GHz, le 4.782.969 colonne di un sistema integrale di 14 triple senza alcun vincolo viene sviluppato interamente in meno di un secondo! Ed ovviamente, più vincoli imponiamo più veloce è lo sviluppo, perchè l'albero delle permutazioni viene "potato" prima di arrivare ad analizzare la 14-esima colonna. La figura mostra ad esempio un sistema 6 triple e 6 doppie con qualche vincolo che sviluppa 701 colonne in soli 2 millisecondi!

Nei fatti il programma è così veloce che una opzione del menu Sistema permette di attivare il ricalcolo automatico, un po’ come in Excel: ogni volta che modificate un pronostico o un vincolo, il programma è in grado di ricalcolare il sistema che ne risulta, ed eventualmente mostrarne le prime N colonne. Se avete un computer veloce non vi accorgerete neanche del ritardo.

Il mio primo programma per lo sviluppo dei sistema era scritto in assembly Z80, girava su Sinclair ZX Spectrum e generava circa 700 colonne al secondo. E ci vollero un paio di settimane, per il debug e il fine tuning, per arrivare a quel risultato che per i tempi era di tutto rispetto.

Al confronto, questa versione è implementata in un linguaggio di alto livello, ha richiesto mezz'ora per l'algoritmo vero e proprio (è stato più faticoso creare l'interfaccia utente) eppure è oltre settemila volte più veloce. Certo, un Pentium D non si può paragonare a uno Z80, ma un parte del merito è proprio nelle tecniche di potatura che ho affinato in questi anni e che ho cablato nella classe Permutations.

UPDATE: dopo aver messo online questo articolo ho modificato leggermente la libreria CAPermutations, e il link ora punta alla versione aggiornata. Tutto quanto scritto nel post originario resta valido, eccetto che il metodo di callback restituisce un enumerativo anzichè un booleano.

Nel mio precedente post ho introdotto la nuova libreria CAPermutations, a cui sto lavorando nel tempo libero. In questi giorni ho potenziato la libreria e modificato leggermente la sintassi del costruttore. Nel post originale trovate una piccola nota sulle differenze rispetto alla versione originale.

In questo articolo descriverò invece la feature più potente della libreria CAPermutations, ovvero la possibilità di impostare dei criteri di selezione delle varie permutazioni. In pratica, è possibile fornire alla libreria l'indirizzo di un metodo di callback: questo metodo viene chiamato mentre viene generata una nuova permutazione, e quindi il programma client ha la possibilità di scartare le permutazioni che non interessano. La cosa interessante è che la routine di callback viene chiamata non soltanto quando la permutazione è stata completata, ma anche durante le fasi intermedie. Supponiamo ad esempio di voler calcolare le permutazioni dei numeri 1-9 ma con la condizione che il numero N non si trovi in posizione N-esima. Ovviamente possiamo generare le 9! permutazioni dei numeri in questione e poi scartare quelli che non soddisfano la condizione, ma il metodo di callback permette di accellerare notevolmente i tempi di elaborazione: infatti non ha senso provare per poi scartare i milioni di permutazioni che presentano la cifra 1 al primo posto, ma è molto più efficiente dire "non farlo!" nel momento il cui la classe Permutations prova a generare la prima permutazione errata, dicendole in pratica di saltare tutte le permutazioni di quel tipo.

Ecco un programma Visual Basic che risolve il problema delle permutazioni di questo tipo:

Sub GeneratePermutations() 
   ' generate permutations of digits 1-5
   Dim elements() As Integer = {1, 2, 3, 4, 5}
   Dim permutations As New Permutations(Of Integer)(elements, 5, PermutationKind.Permutations, 1, AddressOf PermutationFilter)
   For Each perm() As Integer In permutations
      Dim sb As New System.Text.StringBuilder
      For Each n As Integer In perm
         sb.Append(n)
      Next
      Console.WriteLine(sb.ToString)
   Next
End Sub

Private Function PermutationFilter(ByVal permutation() As Integer, ByVal level As Integer, ByVal backtracking As Boolean) As PermutationResult
   ' this is the element just added
   Dim number As Integer = permutation(level)
   ' backtrack if the element is equal to its position
   If number <> (level + 1) Then Return PermutationResult.Proceed Else Return PermutationResult.Backtrack
End Function

La procedura di callback, detta anche procedura di filtro, accetta tre argomenti e restituisce un enumerativo PermutationResult. Il primo argomento è il vettore che rappresenta la permutazione che è stata costruita fino a quel momento; il secondo argomento rappresenta il livello di costruzione della permutazione, ovvero l'indice zero-based dell'elemento che è stato appena aggiunto prima di chiamare il metodo di callback. Il terzo argomento è False se la permutazione è stata costruita, True se siamo in fase di backtrack (vedi dopo). Il metodo deve restituire il valore PermutationResult.Proceed se la permutazione può essere accettata, PermutationResult.Backtrack se deve essere scartata. Vi sono altri possibili valori di ritorno, ma li vedremo meglio in altri articoli di questa serie.

La possibilità di effettuare backtracking, ovvero di tornare indietro sui suoi passi se il metodo di callback restituisce PermutationResult.Backtrack, aumenta enormemente il potenziale della libreria e le permette di risolvere problemi combinatoriali molto complessi. Ecco ad esempio una classe che risolve il famoso problema delle regine, ovvero come sistemare N regine su una scacchiera N*N in modo che non si diano scacco a vicenda. Si tratta di un classico problema combinatorio su cui, prima dell'avvento dei computer, si sono arrovellati dei geni come Gauss e altri famosi matematici. Per una introduzione molto sintetica al problema, date una occhiata a questa pagina oppure googlate per "queens' problem" (virgolette incluse).

Questo problema corrisponde a trovare una permutazione dei numeri 1-N, dove ogni elemento P(n) della permutazione rappresenta la colonna in cui posizionare la regina della riga N. Il solo fatto di richiedere permutazioni delle cifre 1-N (dove ogni elemento della permutazioni può apparire una sola volta) assicura che le regine si trovino su colonne oltre che su righe separate. Di fatto quindi, il metodo di callback deve soltanto tenere traccia di quali diagonali (principali e secondarie, ovvero quelle in direzione NO-SE e quelle in direzione NE-SO) sono occupate dalle regine poste sulla scacchiera fino a quel momento. Ecco il codice C# di una classe che calcola tutte le soluzioni del problema, con N qualsiasi:

Con qualche piccola aggiunta alla procedura di callback è anche possibile risolvere il problema delle amazzoni (o delle super-regine) dove una amazzone è una regina con super-poteri che è anche in grado di muoversi come un cavallo. Queste sono le sole righe che occorre aggiungere nel punto segnato da un commento nel listato della classe:

         // additional tests for the amazons' problem
         if ( Kind == ProblemKind.Amazons )
         {
            // check the cells in previous row
            if ( row > 0 && ( columns[row - 1] == col - 2 || columns[row - 1] == col + 2 ) )
               return PermutationResult.Backtrack;
            // check cells two rows above
            if ( row > 1 && ( columns[row - 2] == col - 1 || columns[row - 2] == col + 1 ) )
               return PermutationResult.Backtrack;
         }

Ho preparato un programma che permette di risolvere il problema delle regine e delle amazzoni con N compreso tra 4 e 20. In aggiunta alle feature appena descritte, il programma è anche in grado di scartare le riflessioni e le rotazioni, per ottenere quelle che si definiscono le soluzioni base del problema. Grazie alla classe Permutations, con una manciata di istruzioni è stato possibile risolvere un problema combinatorio davvero complesso. E il tutto in modo super-efficiente: sul mio computer il problema delle regine di ordine 12 è risolto in circa 1.5 secondi, per trovare tutte le 1787 soluzioni base.

Questo è il link al sorgente del programma delle regine e amazzoni, che contiene anche la versione aggiornata della libreria CAPermutations e del programma per generare anagrammi: QueensProblem.zip (37.25 KB)

Ieri mi scrive un mio lettore, Claudio Fontana, con una richiesta apparentemente semplice: come fare per evitare sfarfallii strani quando si devono aggiornare la maggior parte dei controlli sul form? Il problema si fa sentire soprattutto quando occorre aggiungere migliaia di elementi a listbox e treeview.

In VB6 questo problema si risolveva molto semplicemente impostando la proprietà Visible (o Enabled) a False durante l'aggiornamento, e re-impostandola a True alla fine delle operazioni: la cosa interessante è che, a meno di non inserire una istruzione Refresh esplicita, il controllo non veniva effettivamente reso invisibile o "grayed", ma il suo nuovo contenuto appariva di botto, senza alcun effetto di flickering. Non solo: se il controllo veniva reso invisibile l'aggiornamento veniva anche eseguito molto più velocemente, tipicamente nella metà del tempo solitamente necessario. Sfortunatamente, in .NET il trucco di rendere i controlli temporaneamente invisibili non funziona più, nel senso che il refresh avviene effettivamente e quindi il controllo scompare effettivamente per tutta la durata dell'aggiornamento. Occorre pensare a qualcos'altro.

Alcuni controlli Windows Forms espongono i metodi BeginUpdate e EndUpdate, che di fatto ottengono non solo di "congelare" un controllo durante le operazioni di aggiornamento ma anche di sveltire notevolmente le operazioni stesse, che diventano anche 2.5 volte più veloci. Però solo quattro controlli espongono questa proprietà: ListBox, ComboBox, TreeView e ListView. Se il vostro form contiene molti controlli di altro tipo è necessario pensare a qualcos'altro, e questo è il problema che mi ha sottoposto Claudio, dopo aver googlato a destra e a manca sulla Rete alla ricerca di una soluzione, senza alcun esito.

Poichè il problema era intrigante, ho deciso di dedicarci qualche minuto, e sono arrivato ad una soluzione abbastanza interessante e (se Claudio ha googlato bene) anche inedita. L'idea è davvero molto semplice: (1) si "fotografa" l'aspetto corrente del form, copiandolo pixel per pixel in una bitmap, (2) si crea un controllo PictureBox grande quanto il form e si carica la bitmap nella PictureBox, (3) si aggiunge la PictureBox alla collection Controls e la si porta in primo piano, in modo da coprire tutti gli altri controlli, (4) mentre l'utente vede l'immagine congelata del form, si aggiornano tutti i controlli, usando i metodi BeginUpdate/EndUpdate se possibile per velocizzare le operazioni, (5) quando l'update è completato, si elimina la PictureBox in modo che l'utente torni a vedere il vero contenuto del form.

Tutto questo algoritmo è in realtà molto semplice, e si riduce a una decina di righe. Però ho pensato di creare una classe ad-hoc, in modo che il codice sia facilmente riutilizzabile, rilasci correttamente le risorse, e si protegga da utilizzi errati:

Public Class FormFreezer
   Implements IDisposable

   ' The form being frozen
   Dim Form As Form
   ' the auxiliary PictureBox that will cover the form
   Dim PictureBox As PictureBox
   ' the number of times the Freeze method has been called
   Dim FreezeCount As Integer = 0

   ' create an instance associated with a given form
   ' and optionally freeze the form right away
   Public Sub New(ByVal form As Form, Optional ByVal freezeIt As Boolean = False)
      Me.Form = form
      If freezeIt Then Me.Freeze()
   End Sub

   ' freeze the form 
   Public Sub Freeze()
      ' Remember we have frozen the form once more
      FreezeCount += 1
      ' Do nothing if it was already frozen
      If FreezeCount > 1 Then Exit Sub

      ' Create a PictureBox that resizes with its contents
      PictureBox = New PictureBox()
      PictureBox.SizeMode = PictureBoxSizeMode.AutoSize
      ' create a bitmap as large as the form's client area and with same color depth
      Dim frmGraphics As Graphics = Form.CreateGraphics()
      Dim rect As Rectangle = Form.ClientRectangle
      PictureBox.Image = New Bitmap(rect.Width, rect.Height, frmGraphics)
      frmGraphics.Dispose()

      ' copy the screen contents, from the form's client area to the hidden bitmap
      Dim picGraphics As Graphics = Graphics.FromImage(PictureBox.Image)
      picGraphics.CopyFromScreen(Form.PointToScreen(New Point(rect.Left, rect.Top)), New Point(0, 0), New Size(rect.Width, rect.Height))
      picGraphics.Dispose()

      ' Display the bitmap in the picture box, and show the picture box in front of all other controls
      Form.Controls.Add(PictureBox)
      PictureBox.BringToFront()
   End Sub

   ' unfreeze the form
   ' Note: calls to Freeze and Unfreeze must be balanced, unless force=true 
   Public Sub Unfreeze(Optional ByVal force As Boolean = False)
      ' exit if nothing to unfreeze
      If FreezeCount = 0 Then Exit Sub
      ' remember we've unfrozen the form, but exit if it is still frozen
      FreezeCount -= 1
      ' force the unfreeze if so required
      If force Then FreezeCount = 0
      If FreezeCount > 0 Then Exit Sub

      ' remove the picture box control and clean up
      Form.Controls.Remove(PictureBox)
      PictureBox.Dispose()
      PictureBox = Nothing
   End Sub

   ' return true if the form is currently frozen
   Public ReadOnly Property IsFrozen() As Boolean
      Get
         Return FreezeCount > 0
      End Get
   End Property

   ' ensure that resources are cleaned up correctly
   Public Overridable Sub Dispose() Implements IDisposable.Dispose
      Me.Unfreeze(True)
   End Sub
End Class

Questo è invece la versione C#, tradotta da Claudio:

Usare la classe FormFreezer è semplicissimo. Ecco un esempio di codice (che deve trovarsi all'interno di una classe Form, in modo che Me punti al form corrente):

   Dim ff As New FormFreezer(Me, True)
   ' update controls here
   ' ...
   ff.Unfreeze()

Incoraggiato dalle buone risposte al mio ultimo quizzettino sulla ottimizzazione, ne ho preparato un'altro sullo stesso tenore, anzi abbastanza simile, anche se credo sia abbastanza più semplice del precedente. Ma potro' dirlo solo dopo aver visto in quanto tempo lo risolverete (perchè oramai sono sicuro che lo risolverete, e presto!)

Supponiamo di avere un vettore bidimensionale di interi, e di voler calcolare il massimo della somma dei numeri in ciascuna colonna. Ecco il programma C# che risolve il problema

const int ROWS = 4000;
const int COLS = 4000;
int[,] arr = new int[ROWS, COLS];
// fill the array with random data (or read it from file, etc.)
Random rnd = new Random(1234);
for (int r = 0; r < ROWS; r++)
   for (int c = 0; c < COLS; c++)
      arr[r, c] = rnd.Next(1, 10000);
// eval the max of the sum of all elements in each given column
Stopwatch sw = Stopwatch.StartNew();
int sumMax = int.MinValue ;
for (int c = 0; c < COLS; c++)
{
   // eval the sum of elements in this column
   int colsum = arr[0,c];
   for (int r = 1; r < ROWS; r++)
      colsum += arr[r, c];
   // update the summax value
   if ( sumMax < colsum )
      sumMax = colsum;
}
Console.WriteLine(sw.ElapsedMilliseconds);
Console.WriteLine("Max is {0}", sumMax);       // Max is 20576003

Ecco un altro quizzettino concettualmente molto semplice, ma la cui soluzione potrebbe fornire qualche buono spunto per ottimizzare le vostre applicazioni. Supponiamo di avere un array di numeri floating-point e di voler dividere tutti i valori del vettore per il valore minimo nel vettore stesso. Ecco una possibile soluzione in VB e in C#:

' VB
' An array of 10 million elements
Dim arr(9999999) As Double
' Fill it with random values.
Dim rnd As New Random(1234)
For i As Integer = 0 To arr.Length - 1
   arr(i) = rnd.NextDouble() * 1000000 + 100
Next
' Start the benchmark
Dim sw As Stopwatch = Stopwatch.StartNew()
' Find the min value.
Dim min As Double = arr(0)
For i As Integer = 1 To arr.Length - 1
   If min > arr(i) Then min = arr(i)
Next
' Divide all elements by the min value
For i As Integer = 0 To arr.Length - 1
   arr(i) /= min
Next
Console.WriteLine(sw.ElapsedMilliseconds)

// C#
// an array with 10 million elements
double[] arr = new double[10000000];
// fill it with random values.
Random rnd = new Random(1234);
for (int i = 0; i < arr.Length; i++)
   arr[i] = rnd.NextDouble() * 1000000 + 100;
// start the benchmark
Stopwatch sw = Stopwatch.StartNew();
// find the min value
double min = arr[0];
for (int i = 0; i < arr.Length; i++)
   if (min > arr[i]) min = arr[i];
// divide all elements by the min value
for (int i = 0; i < arr.Length; i++)
   arr[i] /= min;
Console.WriteLine(sw.ElapsedMilliseconds);

Il codice è davvero semplice, eppure è possibile ottimizzarlo ulteriormente in modo significativo, anche del 100% (ossia due volte più veloce). Come?

Oggi stavo rivedendo il capitolo sui tipi base di .NET, in particolare sul boxing e unboxing, e ho guardato con più attenzione il seguente codice:

' The version that does NOT cache the value type in a reference variable.
Dim start As Date = Now
For i As Integer = 1 To 1000
   For j = 1 As Integer To 100000
      GetObject(i, j)
   Next
Next
Console.WriteLine("Version 1: " & Now.Subtract(start).ToString)
GC.Collect() : GC.WaitForPendingFinalizers()

' The version that caches the value type in a reference variable.
start = Now
For i = 1 As Integer To 1000
   ' Cache the value type in an Object variable.
   Dim o As Object = i
   For j As Integer = 1  To 100000
      GetObject(o, j)
   Next
Next
Console.WriteLine("Version 2: " & Now.Subtract(start).ToString)

Private Function GetObject(ByVal o As Object, ByVal o2 As Object) As Object
   Return o
End Function

Come indicano i commenti, la seconda parte del codice "ottimizza" l'esecuzione conservando in una variabile Object la versione boxed del contatore i, che non varia all'interno del ciclo piu' interno. C'è da aspettarsi che la seconda versione dei due cicli sia più veloce, anche se di poco, e infatti questo è quello che accade con Visual Basic .NET 2003. Per fortuna ho rifatto tutti i test con la nuova versione e mi sono accorto che in VB2005 le cose non stanno cosi': per quanto possa sembrare poco intuitivo, la versione che esegue il cache della variable boxed è il 30-40% più lenta dell'altra!

Per capire cosa accade ci vuole un po' di ILDASM, grazie al quale si vede che ogni volta che VB, prima di passare una variabile Object a un argomento Object, chiama il metodo GetObjectValue della classe RuntimeHelpers (namespace System.Runtime.CompilerServices). Questo spiega l'overhead osservato. La cosa strana è che questa chiamata è generata anche in VB2003, eppure non ribalta le conclusioni del benchmark. Poichè sto lavorando con la RTM ne deduco che l'overhead è reale (e non dovuto a pezzi di codice del CLR compilato in debug mode) quindi l'unica conclusione possibile, per il momento, è che la versione 2.0 del metodo GetObjectValue sia meno efficiente della versione 1.1.

Mi sono chiesto cosa faccia GetObjectValue esattamente, ma non mi sono spinto a usare Anakrino per disassemblare quella parte. Immagino che quella chiamata - che è generata dal compilatore VB ma non da C# - serva a compensare il fatto che in VB sono possibili chiamate late-bound e che quella variabile potrebbe anche conservare un pointer a un oggetto COM. Un giorno risolverò i miei dubbi, ma per adesso starò bene attento a eseguire sempre dei benchmark accurati prima di "ottimizzare" il mio codice in questo modo.

UPDATE: Come potete leggere nei commenti, mentre io mi chiedevo cosa facesse GetObjectValue, c'era Adrian Florea che già da tempo aveva scovato dei commenti nei sorgenti di Rotor che chiarivano il mistero. Ecco il suo post, che spiega tutto.

Sto revisionando il 3° capitolo sul controllo del flusso, e ho pensato di mettere in forma di quiz un piccolo tip che spiego nel libro. Considerate il seguente codice:

For i As Integer = 1 To 10
   Dim exiting As Boolean = False
   For j As Integer = 1 To 20
      ' If the Evaluate function returns zero you want to exit both loops
      If Evaluate(i, j) = 0 Then
         exiting = True
         Exit For
      End If
   Next
   If exiting Then Exit For
Next

Supponete ad esempio di avere un componente nel data tier che contiene la stringa di connessione al database. Questa stringa di connessione è letta al momento di istanziare il componente - ad esempio da un file di configurazione XML - e quindi il compilatore non può memorizzarla nell'intern pool. Se questo componente è istanziato N volte vi saranno N copie della stringa di connessione in memoria, il chè costituisce uno spreco di memoria se la stringa è lunga e N è molto alto. Ci sono due modi per evitare questo spreco, a seconda di come la stringa di connessione può variare.

Se la stringa di connessione è esattamente la stessa per tutte le istanze allora la si può conservare in una variabile statica (Shared in VB), in modo che un'unica stringa è condivisa tra tutte le istanze del componente. Questo è il caso più semplice e non credo valga la pena approfondirlo ulteriormente.

Se invece la stringa di connessione può variare - per esempio, se usate un unico tipo le cui istanze possono collegarsi a due o più differenti database - non è possibile usare una variabile static, ma si può ricorrere ad una tecnica basata sul metodo String.Intern. Questo metodo riceve un argomento stringa e lo ricerca nell'intern pool: se la stringa è nel pool, il metodo restituisce un riferimento all'elemento esistente; se la ricerca fallisce, il metodo inserisce la stringa nel pool e restituisce un riferimento all'elemento appena aggiunto. Ecco come si potrebbe implementare la proprietà ConnectionString nell'ipotetico data object per sfruttare il pool di stringhe:

// C#
private string m_ConnectionString;

public string ConnectionString
{
  get { return m_ConnectionString; }
  set { m_ConnectionString = String.Intern(value);}
}

La prima volt ache un certo valore è assegnato alla proprietà ConnectionString, la ricerca nel pool fallisce, il metodo String.Intern aggiunge la stringa al pool e restituisce un riferimento al nuovo elemento del pool. Se la stessa stringa di connessione è assegnata a una istanza differente del data object, il metodo String.Intern restituisce un riferimento all'elemento che è già nel pool e non è creato alcun duplicato. In questo modo la quantità di memoria complessiva usata dal componente è minore e si riduce anche il numero delle garbage collection necessarie. 

Sto aggiustando il capitolo sul controllo del flusso di esecuzione, dove parlo (tra le variecose) anche delle funzioni ricorsive. Nella maggior parte dei libri di programmazione che conosco (incluso molti "classici") la ricorsione è trattata in modo superficiale con il tipico esempio del fattoriale (che può essere risolto in modo più efficiente con un ciclo For) oppure per visitare strutture ad albero. Sembrerebbe che la ricorsione non serva in una applicazione gestionale "normale", il che ovviamente non è vero. Come tutte le tecniche di programmazione, basta essere attenti a sfruttare le occasioni.

Ecco ad esempio un metodo che trasforma un numero nel suo corrispondente alfanumerico (ad es. 1234 in "One Thousand Two Hundreds Thirty Four"). Il codice è preso dal libro per Microsoft Press e quindi il risultato è in inglese, ma è facile ottenere una versione che emette il risultato in italiano:

Function NumberToText(ByVal n As Integer) As String
   Select Case n
      Case Is < 0
         Return "Minus " & NumberToText(-n)
      Case 0
         Return ""
      Case 1 To 19
         Dim arr() As String = {"One", "Two", "Three", "Four", "Five", "Six", _
            "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", _
            "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}
         Return arr(n - 1) & " "
      Case 20 To 99
         Dim arr() As String = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", _
            "Seventy", "Eighty", "Ninety"}
         Return arr(n \ 10 - 2) & " " & NumberToText(n Mod 10)
      Case 100 To 199
         Return "One Hundred " & NumberToText(n Mod 100)
      Case 200 To 999
         Return NumberToText(n \ 100) & "Hundreds " & NumberToText(n Mod 100)
      Case 1000 To 1999
         Return "One Thousand " & NumberToText(n Mod 1000)
      Case 2000 To 999999
         Return NumberToText(n \ 1000) & "Thousands " & NumberToText(n Mod 1000)
      Case 1000000 To 1999999
         Return "One Million " & NumberToText(n Mod 1000000)
      Case 1000000 To 999999999
         Return NumberToText(n \ 1000000) & "Millions " & NumberToText(n Mod 1000000)
      Case 1000000000 To 1999999999
         Return "One Billion " & NumberToText(n Mod 1000000000)
      Case Else
         Return NumberToText(n \ 1000000000) & "Billions " _
            & NumberToText(n Mod 1000000000)
   End Select
End Function

Ecco la versione per gli amanti delle parentesi graffe. Poichè lo switch di C# non supporta i range, ho dovuto modificare il codice per usare una serie di istruzioni elseif. Un dettaglio interessante è come il codice costruisce un array di stringhe al volo per poi selezionare un elemento. E' possibile farlo anche in VB.NET, ma è una di quelle feature che piacciono soprattutto ai programmatori C#:

string NumberToText( int n)
{
   if ( n < 0 )
      return "Minus " + NumberToText(-n);
   else if ( n == 0 )
      return "";
   else if ( n <= 19 )
      return new string[] {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", 
         "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}[n-1] + " ";
   else if ( n <= 99 )
      return new string[] {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}[n / 10 - 2] + " " + NumberToText(n % 10);
   else if ( n <= 199 )
      return "One Hundred " + NumberToText(n % 100);
   else if ( n <= 999 )
      return NumberToText(n / 100) + "Hundreds " + NumberToText(n % 100);
   else if ( n <= 1999 )
      return "One Thousand " + NumberToText(n % 1000);
   else if ( n <= 999999 )
      return NumberToText(n / 1000) + "Thousands " + NumberToText(n % 1000);
   else if ( n <= 1999999 )
      return "One Million " + NumberToText(n % 1000000);
   else if ( n <= 999999999)
      return NumberToText(n / 1000000) + "Millions " + NumberToText(n % 1000000);
   else if ( n <= 1999999999 )
      return "One Billion " + NumberToText(n % 1000000000);
   else 
      return NumberToText(n / 1000000000) + "Billions " + NumberToText(n % 1000000000);
}

Non è codice complesso, ma non ho mai visto sui mille siti Internet una routine per la trasformazione di numeri in lettere altrettanto concisa ed efficace. Adoro la programmazione ad oggetti, i generics, gli attributi, e le regular expression, ma mi piace ricordare (e ricordarmi) che spesso si può scrivere ottimo codice, compatto e veloce, anche solo sfruttando feature che i principali linguaggi hanno da venti o trent'anni.

Oggi ho scoperto un'altra di quelle feature non documentate delle regex in .NET che invece dovrebbero essere un pubblicizzate a dovere, fosse solo per dimostrare che in Microsoft prendono la cosa molto seriamente. Considerate il seguente codice:

Stasera vado in vacanza, o meglio, lascio la città e mi sposto in collina, dove si soffre meno il caldo e ho comunque il mare a cinque minuti di macchina. Non posso dire che vado realmente in vacanza, visto che passerò la maggior parte del tempo lavorando sul primo dei due libroni su VB 2005. Avrò accesso a Internet, ma con un lentissimo dialup, quindi non potrò frequentare il blog e la Rete come al solito. Ma non mi lamento, nè mi pesa vivere unplugged per un po' di tempo.

A proposito del libro, oggi sto rivedendo il capitolo sui generics, e ho fatto una piccola-grande scoperta che mi era sfuggita e che non ho trovato documentata da nessuna parte. Anzi è stata una doppia scoperta. Andiamo con ordine.

Come è noto, la classe System.Array ha sempre avuto il metodo IndexOf, che serve a restituire l'indice di un elemento nel vettore, oppure -1 se l'elemento cercato non esiste. In .NET 2.0 hanno affiancato un metodo generico, IndexOf<T>. Provate il seguente codice:

' VB
Dim arr(999) As Integer
arr(999) = -1
' standard version
Dim index As Integer = Array.IndexOf(arr, -1)
' geneeric version
Dim index2 As Integer = Array.IndexOf(Of T)(arr, -1)

Secondo tutto quello che si può leggere in giro, la versione che usa IndexOf<int> dovrebbe andare molto più veloce della precedente, in quanto la ricerca è ottimizzata e perchè non viene eseguito il boxing del secondo argomento. Beh, ecco la prima sorpresa: le due sintassi producono esattamente lo stesso codice IL e quindi hanno la stessa velocità. Sia il compilatore VB che il compilatore C# si rendono conto che è possibile usare il metodo IndexOf<T> anzichè il meno efficiente IndexOf e quindi in entrambi i casi chiamano il metodo IndexOf<int> per produrre il codice più efficiente possibile. Ovviamente questo comportamento non è specifico per i soli metodi della classe Array, ma vale in tutti i casi in cui una classe espone due metodi con lo stesso nome, uno standard e uno generico: se il compilatore riesce a sfruttare il metodo generico lo farà, e voi ve ne potete accorgere solo esplorando l'assembly con ILDASM, come ho fatto io.

Tutto bene, quindi? Ovviamente no. Come ho detto, ho fatto anche una seconda scoperta, un po' meno piacevole della precedente. Il compilatore riesce ad usare il metodo generico solo se i tipi degli argomenti coincidono perfettamente! Attenzione, perchè - a differenza di quel che accade con gli overload dei metodi, in cui il compilatore è in grado di capire che un argomento Int32 può essere passato ad un argomento Int64 - quando cerca la corrispondenza dei metodi generici il compilatore non tenta neanche di eseguire una coercion degli argomenti per trovare il metodo generic più conveniente, e use direttamente il metodo standard.

' VB
' questo codice usa la versione nongeneric, meno efficiente
Dim search As Short = -1
Dim index2 As Integer = Array.IndexOf(arr, search)

Buono a sapersi, direte voi, ma nella pratica non si capisce perchè dovremmo passare un Int16 quando stiamo cercando un elemento di un array Int32, quindi è giusto uno di quei dettagli teorici che non impattano sullo stile di scrittura del codice, tanto nella maggioranza dei casi se la vedrà il compilatore. Se credete questo, allora date una occhiata a questo codice dall'aria innocente:

' VB
Dim arr(999) As Long
arr(999) = -1
' quale versione verrà usata, IndexOf oppure IndexOf(Of Long) ?
Dim index As Integer = Array.IndexOf(arr, -1)

Soluzione del quesito: sia il compilatore VB che il compilatore C# userà la versione "tradizionale" di IndexOf, perchè tutte le costanti intere sono considerate essere degli Int32 (a meno di non specificare altrimenti), e come ho appena ribadito ambedue i compilatori usano la versione "generica" solo se il tipo corrisponde perfettamente. La soluzione è evidentemente quella di specificare la clausola (Of Long) (in VB) o <long> (in C#) oppure forzare il tipo del secondo argomento:

' VB
' forza il secondo argomento come Long per usare la versione "generica"
Dim index As Integer = Array.IndexOf(arr, -1L)

Sembra una cosa da nulla, ma con la Beta 2 quella "L" aggiunta in coda alla costante -1 fa andare il vostro codice circa 100 volte più veloce!!! Non mi pare di conoscere altri casi in cui un singolo carattere in più o in meno riesce ad aumentare l'efficienza del codice di circa 2 ordini di grandezza!

Per essere più precisi, il guadagno di velocità dipende dal numero di volte che ci chiama il metodo IndexOf. Infatti, ad ogni chiamata avviene una operazione di boxing, che a sua volta crea un oggetto temporaneo che prima o poi dovrà essere "reclamato" dal GC. Eseguendo quel metodo 10mila o 100mila volte, il tempo complessivo della versione standard è circa 100 volte quello della versione che usa il metodo generico. Nella versione definitiva di .NET 2.0 i rapporti di velocità potrebbero essere differenti, e magari il divario potrebbe essere minore (o maggiore) a seconda della RAM installata e altri dettagli, ma certamente il comportamento dei compilatori rimarrà identico, quindi conviene abituarsi fin da ora a queste sottigliezze sintattiche dei metodi generici.

La cosa più buffa di tutta la questione è che ricordo di aver visto alcuni "benchmark" in giro sulla rete che confrontano la versione standard e la versione generics di IndexOf o di qualche altro metodo di .NET 2.0 che esiste in entrambe le versioni, e tutti i benchmark tentavano di dimostrare che la seconda delle due era il 10-15% più veloce dell'altra. Peccato che in realtà quei "benchmark" (le virgolette sono d'obbligo a questo punto) stavano in realtà testando lo stesso codice IL e che le differenze in performance erano da imputare soltanto alle solite fluttazioni statistiche di cui soffrono tutti i benchmark.

Con mia sorpresa - e un po' di delusione - devo constatare che questa volta nessuno ha risposto il quizzettino che avevo proposto sui generics, se si eccettua il "solito" Stefano. Mi piacerebbe leggere qualche vostro commento, per capire se il quizzettino era troppo difficile, oppure era su un argomento che ancora in pochi conoscono, o semplicemente se siete già tutti al mare

Comunque, nella sua semplicità il quiz era abbastanza interessante. Se con l'object browser si dà una occhiata ai metodi dell'oggetto List<T> si nota un metodo generico che potrebbe fare al caso nostro. Il metodo FindAll, infatti, restituisce un altro oggetto List<T> che contiene solo gli elementi della lista che soddisfano l'azione indicata da un delegate di tipo Predicate<T>. Allora potrei usare il metodo FindAll sull'oggetto List2 e nel predicato testo la condizione che l'elemento sia contenuto anche in List1, ossia qualcosa del genere:

Dim list1 As New List(Of Double)(New Double() {1, 2, 3, 4, 5, 6, 7, 8, 9})
Dim list2 As New List(Of Double)(New Double() {0, 3, 6, 9, 12})
Dim list3 As List(Of Double)

Sub SolveQuiz
   ' Find all eleemnts of list2 that appear also in list2, and remove them from list1
   Dim list3 As List(Of Double) = list2.FindAll(AddressOf FindInList1)
   ' Remove all the elements in list1/list2 that appear also in list3
   list1.RemoveAll(AddressOf FindInList3)
   list2.RemoveAll(AddressOf FindInList3)
End Sub

Function FindInList1(ByVal n As Double) As Boolean
   Return list1.Contains(n)
End Function

Function FindInList3(ByVal n As Double) As Boolean
   Return list3.Contains(n)
End Function

Questa soluzione è poco elegante, anche perchè costringe a dichiarare le tre liste a livello di classe, per metterle a disposizione delle tre procedure. In C# si può aggirare il problema usando gli anonymous methods:

List<double> list1 = new List<double>(new double[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
List<double> list2 = new List<double>(new double[] { 0, 3, 6, 9, 12});

List<double> list3 = list2.FindAll( delegate(double n)
                                  { return list1.Contains(n);});
list1.RemoveAll(delegate(double n)
                                  { return list3.Contains(n); });
list2.RemoveAll(delegate(double n)
                                  { return list3.Contains(n); });

Se contiamo le istruzioni negli anonymous methods (ma non le dichiarazioni di list1 e list2), anche la soluzione C# non riesce a scendere sotto le 6 istruzioni. Quindi probabilmente vi stupirete se vi dico che si può fare con soltanto DUE istruzioni?

La tecnica è molto semplice, una volta che si comprende il trucco. Tutti i libri e gli articoli che ho letto mostrano come usare i metodi generici di Array, List, Dictionary e altri classe con dei delegate che puntano a dei metodi definiti nella propria applicazione o, nel caso di C#, che puntano a degli anonymous methods. Ma i delegate possono puntare a metodi definiti nel framework, purchè ovviamente tali metodi rispettino la signature del delegate. In altre parole, è possibile scrivere del codice molto più compatto come segue:

' VB
Dim list3 As List(Of Double) = list2.FindAll(AddressOf list1.Contains)
list1.RemoveAll(AddressOf list3.Contains)
list2.RemoveAll(AddressOf list3.Contains)

// C#
List<double> list3 = list2.FindAll(new Predicate<double>(list1.Contains));
list1.RemoveAll(new Predicate<double>(list3.Contains));
list2.RemoveAll(new Predicate<double>(list3.Contains));

E così siamo riusciti a ridurre le istruzioni da 6 a 3. Come fare per eliminarne ancora una? Basta ricordare che il metodo Remove di List<T> restituisce True se l'elemento specificato era effettivamente presente nella lista, quindi possiamo passarlo direttamente come predicato per il metodo FindAll:

' VB
Dim list3 As List(Of Double) = list2.FindAll(AddressOf list1.Remove)
list2.RemoveAll(AddressOf list3.Contains)

// C#
List<double> list3 = list2.FindAll(list1.Remove);
list2.RemoveAll(list3.Contains);

... dove in C# ho approfittato della nuova feature del delegate inference (che il VB.NET ha da qualche anno, ).

Certo non si può dire che questo codice sia il massimo della leggibilità, ma di certo è un buon esempio di quello che si riesce a fare con i generics. Che ne dite?

Ora che vi ho spiegato il meccanismo, vi lascio con un piccolo quizzettino accessorio, la cui soluzione si basa sulla medesima tecnica:

Data un oggetto List1 di tipo List<int> che contiene un numero qualsiasi di interi (es 10,16,32), ottenere una nuova lista List2<string> che contiene la rapresentazione esadecimale dei numeri in List1 (es. "A", "10", "20") con una sola istruzione e senza usare anonymous methods.

Con l'uscita di Whidbey arriveranno sul mercato, anzi stanno già arrivando, tonnellate di libri che spiegheranno tutte le nuove feature di Visual Studio 2005. Come ho spiegato in un precedente post non credo che i libri basati sulle versioni beta siano molto affidabili o utili, perchè si basano su feature non ancora stabili ma soprattuto perchè se si tratta di feature veramente nuove neanche l'autore ha avuto probabilmente il tempo di approfondire davvero certi temi, pressato dall'editore che vuole pubblicare al più presto (...e dalla moglie e i figli che rivogliono indietro il marito/padre )

Tutte queste considerazioni continuano a frullarmi in mente in questi giorno che mi sto "spazzolando" per bene i generics, che sono davvero la cosa migliore che poteva capitare al Visual Basic e al C#. Anche se i generics sono spesso in grado di generare codice più efficiente delle tecniche old-styled, la loro vera potenza è nella eleganza e nella concisione, ovvero nella possibilità di ottenere tanto scrivendo pochissimo codice. Gli articoli e i primi libri che sto vedendo in giro non mi pare rendano giustizia a questa nuova feature.

Ero pronto a mostrare qualche esempio particolarmente interessante preso dal mio prossimo libro, ma la tentazione di presentare l'ennesimo quizzettino è stata troppo forte. Partiamo con due liste di numeri in virgola mobile, ad esempio:

Dim list1 As New List(Of Double)(New Double(){1, 2, 3, 4, 5, 6, 7, 8, 9})
Dim list2 As New List(Of Double)(New Double(){0, 3, 6, 9, 12})

Il quizzettino consiste nello scrivere il più breve programma che genera una nuova lista list3 che contiene tutti gli elementi di list2 che compaiono anche in list1 e contemporaneamente rimuove tutti gli elementi di list3 da list1 e list2. Per intenderci, nell'esempio di cui sopra al termine dell'esecuzione list1 dovrà contenere {1,2,4,5,7,8}, list2 dovrà contenere {0,12} e list3 dovrà contenere {3,6,9}. Ecco un esempio di codice che risolve il problema ma non sfrutta adeguatamente i generics:

Dim list3 As New List(Of Double)
For i As Integer = list1.Count - 1 To 0 Step -1
   If list2.Contains(list1(i)) Then
      list3.Add(list1(i))
      list2.Remove(list1(i))
      list1.RemoveAt(i)
   End If
Next

La soluzione deve essere il più generale possibile, ma per semplicità possiamo supporre che nè list1 nè list2 contengano elementi duplicati. Si accettano soluzioni sia in VB2005 che C# 2.0. Non è importante che la soluzione sia la più efficiente, ma solo la più concisa in termini di numero di istruzioni. (Nel conto totale delle istruzioni si includono quelle che fanno parte di un anonymous method.)