Una struttura per i coefficienti binomiali
Recentemente mi sono trovato di fronte alla necessità di fare dei calcoli con coefficienti binomiali, ma la presenza di tutti quei fattoriali non è certo di buon auspicio. Se dovessi calcolare ogni coefficiente binomiale secondo la definizione dovrei calcolare tre fattoriali. Essendo una funzione che diverge in modo estremamente veloce, sarebbe già un'impresa calcolare qualcosa di irrisorio come 30! Per questo ho scritto una struttura che semplicemente memorizza i fattori moltiplicativi presenti al numeratore e al denominatore della frazione, immaginando di sviluppare tutti i fattoriali. Inoltre, elimina i fattori uguali, ossia semplifica la frazione. Per ottenere il risultato come double, poi, moltiplica e divide alternativamente per i coefficienti presenti al numeratore o al denominatore, per arginare la perdita di precisione dovuta al passaggio di ordine di grandezza (questa parte si può migliorare ulteriormente). Spero che possa essere utile a qualcuno:
struct BinomialCoefficient
{
private List<Int32> numFactors, denFactors;
public BinomialCoefficient(Int32 n, Int32 k)
{
numFactors = Enumerable.Range(1, n).ToList();
denFactors = Enumerable.Range(1, k).Concat(Enumerable.Range(1, n - k)).ToList();
this.Simplify();
}
public static BinomialCoefficient operator *(BinomialCoefficient binom1, BinomialCoefficient binom2)
{
BinomialCoefficient result = new BinomialCoefficient();
result.InitFields();
result.numFactors.AddRange(binom1.numFactors.Concat(binom2.numFactors));
result.denFactors.AddRange(binom1.denFactors.Concat(binom2.denFactors));
result.Simplify();
return result;
}
public static BinomialCoefficient operator /(BinomialCoefficient binom1, BinomialCoefficient binom2)
{
BinomialCoefficient inverse2 = new BinomialCoefficient();
inverse2.numFactors = binom2.denFactors;
inverse2.denFactors = binom2.numFactors;
return binom1 * inverse2;
}
public static explicit operator Double(BinomialCoefficient binom)
{
binom.numFactors.Sort();
binom.denFactors.Sort();
Double result = 1.0;
Int32 minCount = Math.Min(binom.numFactors.Count, binom.denFactors.Count);
for (Int32 i = 0; i < minCount; i++)
result *= (Double)binom.numFactors[i] / binom.denFactors[i];
if (binom.numFactors.Count > binom.denFactors.Count)
for (Int32 i = minCount; i < binom.numFactors.Count; i++)
result *= (Double)binom.numFactors[i];
else
for (Int32 i = minCount; i < binom.denFactors.Count; i++)
result /= (Double)binom.denFactors[i];
return result;
}
private void InitFields()
{
numFactors = new List<int>();
denFactors = new List<int>();
}
private void Simplify()
{
for(Int32 i = 0; i < this.numFactors.Count; i++)
for(Int32 j = 0; j < this.denFactors.Count; j++)
if (this.numFactors[i] == this.denFactors[j])
{
this.numFactors.RemoveAt(i);
this.denFactors.RemoveAt(j);
i--;
break;
}
}
}
Hamlet: to tree or not to tree?
Sto sviluppando una libreria per gestire e analizzare grafi e alberi. Si chiama Hamlet! Proprio come l’omonima opera di Shakespear. Spero che a qualcuno possa servire… Per darvi un’idea approssimativa, su un grafo con 1000 vertici e 33000 connessioni, l’implementazione dell’algoritmo di Dijkstra in modalità Release impiega circa 60-70 millisecondi su un Intel i5 a 3.3GHz.
Parsing di un file .ini in un solo statement
Questo post è un po' una prosecuzione del precedente, in cui ho dato una rapida occhiata alla possibilità di approcciarsi al paradigma funzionale con LINQ. Il codice che vi propongo di seguito è in grado di eseguire il parsing completo di un file di configurazione usando solo due variabili di appoggio e condensando tutta l'elaborazione in una cascata di metodi di estensione linq. Ogni funzione lavora sull'output della precedente e fornisce l'input alla successiva. In questi casi l'inferenza di tipo diventa un'alleata preziosa:
static void Main(string[] args)
{
if (args.Length < 2)
return;
String fileName = args[1];
Regex sectionRegex = new Regex(@"\[(?<Section>\w+)\]");
Regex fieldRegex = new Regex(@"(?<Field>\w+)\s*\=\s*(?<Value>.*)");
Match match;
String lastSection = "<No Section>";
var ini = File.ReadAllLines(fileName)
.Select (line => line.Contains(';') ?
line.Remove(line.IndexOf(';')) :
line)
.Select (line => line.Trim())
.Where (line => !String.IsNullOrEmpty(line))
.GroupBy(line => (match = sectionRegex.Match(line)).Success ?
lastSection = match.Groups["Section"].Value :
lastSection)
.Select (group => new
{
SectionName = group.Key,
Fields = group
.Select(line => (match = fieldRegex.Match(line)).Success ?
new { Name = match.Groups["Field"].Value,
Value = match.Groups["Value"].Value } :
null)
.Where(element => element != null)
});
foreach (var section in ini)
{
Console.WriteLine("Section: {0}", section.SectionName);
foreach (var field in section.Fields)
Console.WriteLine(" Field {0} = {1}", field.Name, field.Value);
}
}
Un'altra funzionalità che ho sfruttato pesantemente è una costante di tutti i linguaggi C-like dagli albori della programmazione letterale imperativa: il valore di ritorno dell'operatore di assegnazione. Notate come non sarebbe stato possibile definire la chiave di raggruppamento se l'assegnazione di lastSection non avesse di fatto restituito il nuovo valore della variabile e come sarebbe stato necessario usare dei metodi anonimi anziché delle espressioni lambda se non avessi potuto richiamare la proprietà Success dall'oggetto esposto dall'assegnazione della variabile match.
Metodi di estensione, null-checks e programmazione funzionale
Se vi capita spesso di dover controllare se una certa variabile di tipo reference contiene un valore nullo (null o Nothing), allora questo articolo è quello che fa per voi. Usare i metodi di estensione per evitare di nidificare decine di if, switch e condizioni varie è veramente un'ottima idea. Se ci fate caso, questo approccio è decisamente più funzionale che imperativo, ed il trend degli ultimi anni per quanto riguarda .NET è proprio una tendenza spiccata verso il paradigma funzionale. Pensateci un attimo: già le espressioni lambda del fw3.5 e successivamente i metodi anonimi del fw4.0 sono state delle grandi aggiunte, ma più di tutti LINQ si fa sentire vigorosamente con la mole di estensioni che mette a disposizione. Certe volte non mi sembra nemmeno di scrivere in C# XD.
Ecco un esempio. Qualche settimana fa stavo scrivendo una libreria con metodi di estensione che uso spesso (per stringhe e collezioni generics). Trovandomi a dover scrivere il codice per la funzione ToProperCase, sono venuto fuori con questo:
public static String ToProperCase(this String instance)
{
if (String.IsNullOrEmpty(instance))
return instance;
return instance.Trim()
.Split(' ')
.Where(word => !String.IsNullOrEmpty(word))
.Select(word => word.Length > 1 ?
Char.ToUpper(word[0]) + word.Substring(1).ToLower() :
word.ToUpper())
.Aggregate("", (accumulator, word) => accumulator + word + ' ')
.Trim();
}
Notate come abbia usato LINQ pesantemente. Il proper case è una formattazione delle stringhe in cui ogni parola ha l'iniziale maiuscola. Nel codice sopra, Trim() elimina gli spazi in testa e in coda alla stringa, Split() spezza la stringa in parti separate da uno spazio, Where() filtra i risultati scartando le stringhe vuote, Select() trasforma ogni parola imponendo il carattere iniziale maiuscolo, Aggregate() aggrega ogni parola in una stringa completa, usando come separatore ancora lo spazio e infine Trim() elimina il carattere spazio incluso alla fine della stringa dal passo precedente.
Se volete altri esempi di programmazione funzionale in C# vi consiglio di leggere anche questo articolo e le altre due pubblicazioni dello stesso autore sempre su c-sharpcorner.
Ascii Art!
Oggi ho letto un simpatico articolo su The Code Project e mi sono preso la libertà di renderlo un po' più formale ed efficiente. Ho racchiuso la funzionalità di creazione in una classe factory e quella di salvataggio in un'altra classe che ha un costruttore dichiarato come internal, cosicché possa essere usato solo da classi dello stesso assembly (nella fattispecie, una volta compilata la libreria, solo dalla classe factory). Ecco il codice:
namespace AsciiArt
{
public class AsciiArtCreator
{
// Contiene i caratteri che rappresentano varie tonalità di grigio, a seconda di
// quanto è "densa" la rappresentazione del carattere
private static Char[] asciiGreyScale = { '@', '#', '8', '&', 'o', ':', '*', '-', ' ' };
// Queste due proprietà indicano a quanti pixel corrisponde un carattere,
// in larghezza e in lunghezza. Di default un carattere è 6x8 pixel
public Int32 AsciiUnitX { get; set; }
public Int32 AsciiUnitY { get; set; }
public AsciiArtCreator()
{
this.AsciiUnitX = 6;
this.AsciiUnitY = 8;
}
public AsciiArtDocument CreateFromImage(String imagePath)
{
if (!File.Exists(imagePath))
throw new FileNotFoundException(imagePath);
return CreateFromImage(Image.FromFile(imagePath) as Bitmap);
}
public AsciiArtDocument CreateFromImage(Bitmap image)
{
AsciiArtDocument document = new AsciiArtDocument();
BitmapData bmData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
Int32 stride = bmData.Stride;
IntPtr Scan0 = bmData.Scan0;
// Usare un'iterazione unsafe tramite puntatori è molto più veloce
// della stessa operazione con il metodo GetPixel(x, y)
document.AsciiFormat = new Size(AsciiUnitX, AsciiUnitY);
unsafe
{
byte* baseAddress = (byte*)(void*)Scan0;
byte red, green, blue, grey;
for (int i = 0; i < image.Height / AsciiUnitY; i++)
{
for (int j = 0; j < image.Width / AsciiUnitX; j++)
{
int greySum = 0;
float greyAverage;
for (int x = 0; x < AsciiUnitX; x++)
for (int y = 0; y < AsciiUnitY; y++)
{
// Calcola la posizione in memoria del colore di questo pixel
byte* position = (byte*)(baseAddress + stride * (i * AsciiUnitY + y) + (j * AsciiUnitX + x) * 3);
blue = position[0];
green = position[1];
red = position[2];
// Ne fa la media per convertirlo in scala di grigi
grey = (byte)((float)(red + green + blue) / 3);
greySum += grey;
}
// Quindi ricava la media di tutte le tonalità di grigio presenti nell'area
// AsciiUnitX x AsciiUnitY che rappresenta un caratere
greyAverage = (float)greySum / (AsciiUnitY * AsciiUnitX);
// E stampa sul documento il carattere ascii corrispondente alla tonalità
// di grigio prevalente nel rettangolino considerato
document.Append(asciiGreyScale[(Int32)(greyAverage / (256.0f / asciiGreyScale.Length))]);
}
document.AppendLine();
}
}
image.UnlockBits(bmData);
return document;
}
}
public class AsciiArtDocument
{
private StringBuilder buffer;
public Size AsciiFormat { get; internal set; }
internal AsciiArtDocument()
{
this.buffer = new StringBuilder();
}
internal void Append(Char c)
{
this.buffer.Append(c);
}
internal void AppendLine()
{
this.buffer.AppendLine();
}
public void SaveAsPlainText(String fileName)
{
File.WriteAllText(fileName, buffer.ToString());
}
public void SaveAsHtml(String fileName)
{
StringReader reader = new StringReader(buffer.ToString());
StreamWriter writer = new StreamWriter(fileName);
writer.WriteLine("");
writer.WriteLine(" ");
writer.WriteLine("
", this.AsciiFormat.Height * 2, this.AsciiFormat.Height * 2 + 2);
while (reader.Peek() > -1)
{
writer.Write(reader.ReadLine());
writer.WriteLine("");
}
writer.WriteLine("
");
writer.WriteLine("");
writer.Close();
reader.Close();
}
}
}
Esempi:
versione ascii (tagliata perché era troppo grande):
Funzioni lambda e metodi di estensione
Dalla versione 3.5 del framework, il .NET supporta ufficialmente il lambda calcolo e i metodi di estensione, mentre i generics sono amici affezionati già dalla release 2.0. Negli ultimi tempi l’impulso a scrivere del codice più elegante, funzionale e generale è stato quindi fortemente favorito. In questo breve e semplice prospetto vorrei mostrare come usare queste tecniche per migliorare la riusabilità e l’utilità del codice.
N.B.: la conoscenza dei generics è data per scontata.
Metodi di estensione
Un metodo di estensione viene dichiarato come un metodo statico, ma viene utilizzato come un metodo d’istanza. Grazie a questa peculiare caratteristica, è possibile aggiungere ai tipi già esistenti – ad esempio String, Int32, Point, eccetera… – altri metodi, pur non avendo accesso al codice che originariamente ne contiene la definizione. Sfortunatamente non è possibile fare lo stesso con gli operatori, le proprietà o i metodi sottoposti a polimorfismo, mentre in altri linguaggi, come ad esempio in Ruby, è possibile anche fare questo.
Dato che i metodi di estensione si comportano in maniera atipica, anche la loro dichiarazione non segue le normali regole. Poiché agiscono come se fossero metodi d’istanza, è necessario specificare da qualche parte su quale istanza si debba lavorare. Si fa questo passando un parametro del tipo che si vuole estendere nella dichiarazione della signature, facendolo precedere dal modificator “this”. E’ inoltre necessario inserire questa dichiarazione in una classe pubblica e statica, in modo che sia accessibile da ogni parte del codice client, il quale dovrà a usa volta eventualmente importare il namespace in cui essa è scritta. Ecco un esempio:
namespace ExtensionMethods
{
// Classe statica e pubblica
public static class Methods
{
// Il metodo di estensione è pure pubblico e statico
public static Int32 Double(this Int32 instance)
{
return instance * 2;
}
}
}
namespace Esempio
{
// Importa il namespace in cui è definita Double
using ExtensionMethods;
class Program
{
static void Main(string[] args)
{
Int32 a = 32;
// Richiama Double come se fosse un metodo d'istanza della classe Int32
Int32 b = a.Double();
Console.WriteLine(a); // 32
Console.WriteLine(b); // 64
Console.ReadKey();
}
}
}
Espressioni lambda
Il lambda calcolo si basa sulla manipolazione di funzioni definite inline. In .NET, esiste un tipo deputato a contenere una funzione lambda. Invece che contenere un valore, variabili di quel tipo contengono invece quelle funzioni che, a seconda dei punti di vista, si possono chiamare inline, anonime o lambda. Tale tipo è Func, ed è dichiarato usando svariati tipi generics collegati. Una funzione lambda si dichiara in questo modo:
parametri => valore_restituito
Se i parametri sono più di uno, vanno specificati tra parentesi e separati da virgole, opzionalmente preceduti dal tipo.
Ad esempio:
// Rappresenta una funzione che, dato x, restituisce x al quadrato
x => Math.Pow(x, 2)[/code]
Detto questo, un semplice codice dimostrativo:
[code]namespace Esempio
{
class Program
{
static void Main(string[] args)
{
// Func indica una funzione che accetta un parametro double e
// restituisce un risultato di tipo double
Func square = x => x * x;
// Analogamente la prossima accetta in input due double e restituisce un altro double
Func weightedAverage = (x, y) => Math.Sqrt(x * y);
// Richiama la funzione contenuta in square
Console.WriteLine(square(4)); // 2.0
Console.WriteLine(weightedAverage(2, 8)); // 4.0
Console.ReadKey();
}
}
}
Mettere tutto insieme
Se l'utilità dei metodi di estensioni può essere lampante, forse lo è di meno quella delle espressioni lambda. Perciò ecco degli esempi pratici.
Nel prossimo codice scriverò una funzione che, data una qualsiasi collezione, applica a tutti gli elementi una certa funzione e restituisce una lista di tutti i risultati. Ad esempio, data una lista di numeri interi, restituisce una lista che ne contiene i quadrati, oppure dato un array di stringhe, restituisce un array che ne contiene le lunghezze. Questi due compiti sembrano molto diversi, ma è possibile implementarli usando lo stesso codice e modificando solo i parametri:
using System;
using System.Linq;
using System.Collections.Generic;
namespace ExtensionMethods
{
public static class Methods
{
/* Transform è un metodo di estensione, perciò lo potremo usare su di ogni tipo o derivato di
IEnumerable, il che equivale a dire che lo potremo usare su ogni collezione di qualsiasi tipo.
transformation è una funzione che accetta come input un parametro di tipo T e restituisce come output
un valore di tipo TResult, quindi la collezione da restituire sarà una IEnumerable di TResult. */
public static IEnumerable
Transform(this IEnumerable instance, Func transformation)
{
// Come vedete il codice è semplice. Crea una lista vuota
List
result = new List
();
// La popola con i risultati della funzione
foreach (T element in instance)
result.Add(transformation(element));
// E la restituisce come IEnumerable
return result.AsEnumerable();
}
}
}
namespace Esempio
{
using ExtensionMethods;
class Program
{
static void Main(string[] args)
{
Int32[] numbers = new Int32[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
String[] strings = new String[] { "tizio", "caio", "sempronio" };
// numbers.Transform(x => x * x) prende la collezione numbers e restituisce una collezione
// contenente i quadrati dei numeri in numbers
foreach (Int32 square in numbers.Transform(x => x * x))
Console.WriteLine(square);
// Allo stesso modo questa ottiene l'insieme delle lunghezze delle stringhe in strings
foreach (Int32 length in strings.Transform(s => s.Length))
Console.WriteLine(length);
Console.ReadKey();
}
}
}
E' talmente utile questa funzione che è implementata di default nel namespace System.Linq e si chiama Select.
Ora, avete presenta la funzione Array.IndexOf? Essa restituisce l'indice del primo elemento dell'array che risulta uguale al parametro specificato. Volendo scrivere una funzione simile, ma che funzioni per tutte le collezioni, potremmo usare un metodo di estensione e qualche vincolo generics:
using System;
using System.Linq;
using System.Collections.Generic;
namespace ExtensionMethods
{
public static class Methods
{
/* Notate il vincolo di interfaccia IComparable. Se il tipo di dato degli elementi della collezione non
rappresenta qualcosa di "comparabile", allora non c'è modo di stabilire se due elementi sono o meno
uguali, o meglio non c'è modo di farlo con le informazioni che si hanno ora sul tipo. Usando il vincolo
stiamo imponendo che questa condizione sia verificata. E' come usare le ipotesi di un teorema. */
public static IEnumerable IndicesOf(this IEnumerable instance, T seed) where T : IComparable
{
List indices = new List();
Int32 i = 0;
foreach(T element in instance)
{
if (element.CompareTo(seed) == 0)
indices.Add(i);
i++;
}
return indices.AsEnumerable();
}
}
}
namespace Esempio
{
using ExtensionMethods;
class Program
{
static void Main(string[] args)
{
String[] strings = new String[] { "mela", "pera", "banana", "mela", "uva", "arancia", "mela" };
// Scrive gli indici a cui compare la parola "mela", ossia 0, 3 e 6
foreach (Int32 index in strings.IndicesOf("mela"))
Console.WriteLine(index);
Console.ReadKey();
}
}
}
Come avete visto, usando i metodi di estensione, le espressioni lambda e poco codice è possibile porre le basi per implementare un'enormità di funzionalità differenti. Visto questo trend verso la programmazione funzionale che si sta insinuando in C# tramite linq, consiglio vivamente di studiare linq to objects e linq to entities.
