Plinq in tram
In un post riguardante il mondo Qt avevo parlato della gestione dei thread e dell'elaborazione parallela grazie a classi che permettevano la gestione di elaborazione di liste distribuendola sui core della macchina. Allora parlavo del mondo della programmazione Qt con il C++. Ho sempre dato largo respiro della programmazione del framework .net sul mio blog, e naturalmente non potevo esimermi di parlare, anche se per sommi capi, di PLINQ.
Dietro alla parola plinq che la cui P sta per parallel, unisce il mondo della gestione dei dati con Linq con la parallelizzazione dell'elaborazione. Semplicemente:
IList<int> results = Enumerable.Range (1, 30).Select(t=>t*t).ToList();
Nella collection results, alla fine dell'elaborazione, sarà presente il quadrato di tutti i numeri da 1 a 30. In input saranno dati i numeri in sequenza fino a 30, quindi il codice elaborerà ogni singolo numero, uno alla volta, per calcolarne il quadrato. Su macchine moderne dove il numero dei core è addirittura esagerato e per la maggior parte del tempo sono lì a fare nulla, perché non usarne la potenza di queste cpu per la computazione di più numeri contemporaneamente e ottenere, di conseguenza, un'elaborazione molto più veloce?
Con PLINQ niente di più facile:
IList<int> results = Enumerable.Range (1, 30).AsParallel().Select(t=>t*t).ToList();
Proviamo a vedere però il risultato:
Riporto in caso l'immagine non fosse perfettamente leggibile:
Without parallel: 1, 4, 9, 16, 25... With parallel: 4, 9, 1, 36, 100...
Si nota nel primo caso l'ordine di calcolo così come ci si aspetta, ma nel secondo caso: 4, 9, 1, 36, 100... la sequenza è casuale perché il framework gestisce parallelamente l'esecuzione degli elementi della lista in modo ottimale - ciò comporta l'ordine casuale.
Anche con il parallel possiamo forzare il framework per mantenere l'ordine nell'esecuzione e lista di uscita:
IList<int> results = Enumerable.Range (1, 30).AsParallel().AsOrdered().Select(t=>t*t).ToList();
Ma vengono usati realmente tutti i core della macchina? Nel mio caso, essendo un I5 con quattro core, vediamo se vengono usati realmente tutti modificando il codice precedente in modo da scoprire se è vero:
var lockitem = new object();
var corelist = new List<int>();
Console.WriteLine("With parallel anche core check:");
IList<int> results = Enumerable.Range(1, 30).AsParallel().Select(t => {
lock (lockitem)
{
var singleCore = System.Threading.Thread.CurrentThread.ManagedThreadId;
if (!corelist.Contains(singleCore)) corelist.Add(singleCore);
}
return t * t;
}).ToList();
for (int i = 0; i < results.Count; i++)
{
Console.Write("{0}, ", results[i]);
}
Console.WriteLine();
for (int i = 0; i < corelist.Count; i++)
{
Console.WriteLine("Core: {0}", corelist[i]);
}Risultato:
With parallel... 9, 1, 25, 36... Core: 3 Core: 1 Core: 5 Core: 4
Ed ecco i quattro core. Per assurdo, un'operazione potrebbe essere così pesante che l'uso di tutti i core potrebbe creare problemi al resto del sistema o dell'applicativo. Possiamo anche decidere il numero di core:
IList<int> results = Enumerable.Range(1, 30).AsParallel().WithDegreeOfParallelism(2).Select(t => {...}).ToList();
With Parallel... Core: 1 Core: 3
Ecco che sono stati usati solo due core della cpu. Possiamo anche rendere il tutto dinamico, qualsiasi numero di core abbia la nostra macchina, una deve sempre rimanere disponibile:
int cores = System.Environment.ProcessorCount-1;
if (cores < 1) cores = 1;
IList<int> results = Enumerable.Range(1, 30).AsParallel().WithDegreeOfParallelism(cores).Select(t => {...}).ToList();Prima di buttarsi sullo scopo di questo post, vediamo un'altra piccola curiosità; ma quanti elementi sono stati eleborati, nell'esempio del codice qui sopra, per ogni core? Scriviamo qualche riga di codice per scoprirlo:
var lockitem = new object();
var corelist = new Dictionary<int,int>();
Console.WriteLine("With parallel core check with number:");
IList<int> results = Enumerable.Range(10, 30000).AsParallel().Select(t =>
{
lock (lockitem)
{
var singleCore = System.Threading.Thread.CurrentThread.ManagedThreadId;
if (!corelist.ContainsKey(singleCore))
corelist.Add(singleCore, 1);
else
corelist[singleCore] += 1;
}
return t * t;
}).ToList();
Console.WriteLine();
foreach (KeyValuePair<int,int> item in corelist)
{
Console.WriteLine("Core: {0} = {1}", item.Key, item.Value);
}
Console.WriteLine("\r\n");
Core: 4 = 7160 Core: 3 = 6904 Core: 1 = 6392 Core: 6 = 9544
Guardando questo risultato - è casuale, eseguendolo più volte si ottengono risultati differenti, si nota che ogni core ha un numero diverso di elementi elaborati per la giusta suddivisione di carico dell'elaborazione. Questa suddivisione è utile soprattutto nel caso di singole elaborazione che possono avere tempi di elaborazione differenti. Oltre al numero dei core, possiamo cambiare anche questo comportamento; vogliamo che il numero degli item sia equamente suddiviso? Ecco il codice:
IList<int> results =System.Collections.Concurrent.Partitioner.Create(Enumerable.Range(10, 30000).ToArray(),false).AsParallel().Select(t => {...}).ToList();Il secondo parametro di "Create" di "Partitioner" forza l'elaborazione come la vogliamo (con true abbiamo il comportamento ottimale di default):
Facendo test approfonditi però ci si rende conto che il funzionamento non è simile a quello del monto Qt trattato nel post precedente. Infatti tenendo d'occhio il task manager per controllare se veramente la cpu e i suoi core sono utilizzare pienamente, si vedrà che non si raggiungerà mai il 100%. Ma perché? Leggendo a fondo la documentazione a riguardo, vengono presi come numero massima di processi da creare il numero dei core, ma il framework .net instanzierà tanti Task quandi sono i core... ma questi NON saranno mai legati in alcun modo al singolo core. Nel mio caso la cpu I5 ha 4 core? Il framework .net instanzierà 4 oggetti Task, ma questi saranno poi usati/gestiti nel modo ottimale al momento dell'esecuzione, in poche parole è possibile che due o più task vengono assegnati ad un singolo core.
Ma che centra il tram del titolo con tutta questa discussione?
Premessa: non sono un matematico e neanche mi ci avvicino a tale nomea. Scopo di questo post è la cavalcata per risolvere un enigma matematico che mi è stato posto da un ex amico - ex dopo questo quiz.
Due matematici (A e B) parlano fra di loro sul tram:
A: "Ho un numero intero positivo di figli, le cui età sono interi positivi, la somma dei quali è il numero di questo tram, mentre il prodotto è la mia età."
B: "Interessante! Forse se tu mi dicessi la tua età e il numero dei tuoi figli, potrei ricavare le loro età?"
A: "No."
B: "Aha! ADESSO so quanti anni hai!"
Domanda: qual è il numero del tram?
Inizialmente stupito pensando ad una presa in giro, mi sono chiesto se c'era qualcosa che mi potesse essere d'aiuto. Non c'erano costanti in tutto questo enigma matematico... qualcosa che una equazione - assolutamente lineare e di primo grado, già con il secondo non ci capisco più niente - mi potesse aiutare.
Provo a pensare nel mondo più semplice possibile sperando che Occam e il suo rasoio mi sia d'aiuto... e partendo dalla semplice dichiarazione del primo matematico: "la somma dell'età dei miei figli è uguale al numero di questo tram, mentre il prodotto è la mia età", mi sparo subito lì due numeri che rispondono in modo corretto a queste due regole:
10 e 4: il matematico ha due figli di 10 e 4 anni, il tram di conseguenza è il 14 e la sua età 40.
Fortuna del principiante: no, semplice ingenuità, perché anche la sequenza successiva - così come molte altre, rispondono perfettamente a quelle due regole:
5, 4, 2: tre figli di 5, 4 e 2 anni, tram numero 11 ed età 40 anni
8, 6: due figli, 8 e 6 anni, tram numero 14 ed età 48
...
Non capivo cosa non funzionasse nel mio ragionamento... di risposte plausibili ce n'erano non un paio, ma a centinaia... ergo la risposta erano nelle frasi successive?
"Forse se tu mi dicessi la tua età e il numero dei tuoi figli, potrei ricavare le loro età?"
"No."
"Aha! ADESSO so quanti anni hai!"
Allora butto lì altri numeri per capire quali rispettano anche queste regole: padre: 30 anni e 2 figli.
Peggio di prima, la serie di coppie di numeri (due figli) che moltiplicati fa 30 non aiuta:
30 1 15 2 10 3 6 5
Ma che casino! Anche così non posso recuperare un numero univoco di tram... nel primo caso 31, nel secondo 17, poi 13 e 11. E di sequenze così e con un numero teorico di figli, il numero di casistiche aumentano esponenzialmente.
Il mondo reale mi ha dato una mano: spesso torno a casa dal lavoro in tram, ma con me non ci sono mai matematici. Ma a quel punto una cosa logica mi ha spinto a pensare che c'era una costante che mi stava sfuggendo: quale persona sale su un tram non sapendone il numero? Ergo, il primo matematico ovviamente conosce il nome del tram perché dice che sommando l'età dei suoi figli di ottiene proprio quel numero, ma anche il secondo matematico deve sapere quel numero. Dunque lui può partire da quel numero per cercare, con non so quale teorema matematico, quelle serie di età dei figli che moltiplicati diano un numero univoco - serie che permette al matematico, con assoluta certezza, di aver dedotto l'età.
L'idea meno stupida che poteva venirmi era di trovare, per ogni numero naturale, una qualsiasi sequenza di numeri anch'essi naturali che sommati facessero quel numero. Per esempio:
3 2 1 1 1 1 5 4 1 3 2 2 2 1 2 1 1 1 1 1 1 1 1 6 5 1 4 2 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1
In questo caso, per il numero 6 per esempio, potevo avere come tram il numero 6, due figli di 4 e 2 anni, e l'età del padre, per assurdo, 8 anni. Ma a farsi a mano una roba del genere non ne avevo assolutamente voglia. Mi decido di scrivere del codice, per ora in C++ - ma poi tornerò a parlare di c# - perché armato di pc senza compilatore e con un browser e una connessione a internet... tempestando questo sito che permette di compilare e provare al volo del codice c++, mi sono scritto questo semplice programmino che costruisce tutte le serie numeriche che ottengono come somma un numero:
#include <string>
#include <iostream>
void calculateOtherNumber(int total, int partial, int maxValue, std::string text, int counter)
{
// togliere il commento alla riga successiva per limitare i numeri delle serie (a 5 nell'esempio)
// if (counter>=3) return;
int restart=maxValue;
if (partial+restart>total) restart=total-partial;
std::string bufferText=text;
for (int i=restart;i>0;i--)
{
// togliere il commento alla riga successiva se si vuole che i numeri che compongono
// la serie sia differenti
//if (text.find(" "+std::to_string(i) + " ") != std::string::npos) continue;
text=text + std::to_string(i) + " ";
if (partial+i==total)
{
// togliere il commento alla riga successiva
// se si vuole avere un numero esatto di numeri che compongono la serie
//if (counter+1==3)
std::cout << text << std::endl;
text=bufferText;
}
else
{
calculateOtherNumber(total,partial+i,i,text,counter+1);
text=bufferText;
}
}
}
void calculateSubNumber(int number)
{
std::string text=" ";
for (int i=number;i>0;i--)
{
text=" " +std::to_string(i) + " ";
if (i!=number)
{
calculateOtherNumber(number,i,i,text,1);
}
else
{
std::cout<< text<<std::endl;
}
}
}
int main()
{
int _numberFinal=10; // <- Numero naturale da cui estrarre le serie
calculateSubNumber(_numberFinal);
std::cout << std::endl;
return 0;
}Il codice è abbastanza semplice e usa la ricorsione per trovare tutti i numeri delle serie. Dopo vari tentativi - quello qui sopra è il codice ripulito - faccio girare per ottenere le serie per il numero 10:
10 9 1 8 2 8 1 1 7 3 7 2 1 7 1 1 1 6 4 6 3 1 6 2 2 6 2 1 1 6 1 1 1 1 5 5 5 4 1 5 3 2 5 3 1 1 5 2 2 1 5 2 1 1 1 5 1 1 1 1 1 4 4 2 4 4 1 1 4 3 3 4 3 2 1 4 3 1 1 1 4 2 2 2 4 2 2 1 1 4 2 1 1 1 1 4 1 1 1 1 1 1 3 3 3 1 3 3 2 2 3 3 2 1 1 3 3 1 1 1 1 3 2 2 2 1 3 2 2 1 1 1 3 2 1 1 1 1 1 3 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 1 1 2 2 2 1 1 1 1 2 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Perfetto, il risultato è quello voluto, non so se è il codice ottimale o se altre routine più performanti e fatte meglio - sicuramente ci sono ma io non le ho trovate - sono presenti in rete, ma era quello che mi serviva. Inoltre, solo per mio divertimento, ho aggiunto anche tre condizioni qui commentate per avere un massimo di numeri naturali che ottengono la somma voluta, o la condizione per avere solo numeri univoci, o per avere un numero fisso di numeri nella serie.Nel primo caso, se volessi al massimo 3 elementi nelle serie, mi basterebbe togliere il commento e lasciare il numero 3 per avere:
10 9 1 8 2 8 1 1 7 3 7 2 1 6 4 6 3 1 6 2 2 5 5 5 4 1 5 3 2 4 4 2 4 3 3
Nel secondo caso, rimettendo il commento nel primo caso e togliendolo nel secondo:
10 9 1 8 2 7 3 7 2 1 6 4 6 3 1 5 4 1 5 3 2 4 3 2 1
Se attivassi entrambe le condizioni, nell'ultimo risultato non apparirebbe l'ultima riga perché possiede 4 elementi.
Infine, con l'ultima opzione, se voglio avere solo le serie con un numero fisso di elementi, togliendo il commento, ottengo:
10 9 1 8 2 7 3 6 4 5 5
Ok, c'è sempre il primo numero di troppo, ma basta una riga di codice di controllo per evitarlo... Soddisfatto per questo codice mi scontro contro l'amara realtà: un controllo anche solo visivo sarebbe da esaurimento nervoso, dunque, tempo dopo e avendo tra le mani un compilatore, mi decido a scrivere una routine che faccia questo controllo per me... d'accordo, ma quale controllo? La risposta del secondo matematico sul tram è d'aiuto: infatti quando si sente rispondere che, anche sapendo l'età dell'altro matematico e il suo numero di figli non sarebbe stato possibile ipotizzare quelle dei figli, lui deduce immediatamente la sua; questo vuol dire che, il secondo matematico, che sapendo il numero tram, ha trovato due serie di numeri differenti che sommati danno lo stesso numero (numero di tram) e moltiplicati danno un numero univoco (età del padre). Solo in questo caso il secondo matematico avrebbe potuto affermare con certezza di sapere l'età del collega. Ecco, il mio codice doveva fare proprio questo! Una parte me l'ero già scritta in c++ e convertirla in c# sarebbe stato banale, ma dovevo anche effettuare quel controllo.Ecco il codice:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace tram1
{
public class CalculateSimple
{
public CalculateSimple()
{ }
public void Run(int numberFinal)
{
List<Tuple<int, string, int>> allKeys = new List<Tuple<int, string, int>>();
CalculateSubNumber(numberFinal, allKeys);
var duplicated = allKeys.GroupBy(t => new { product = t.Item1, numbers = t.Item3 }).Where(t => t.Count() > 1).Select(t => t).ToList();
Console.WriteLine("############ {0} ###############", numberFinal);
duplicated.ForEach(t =>
{
allKeys.Where(y => y.Item1 == t.Key.product && y.Item3 == t.Key.numbers).ToList().ForEach(y =>
{
Console.WriteLine("{0}: {1}", t.Key.product, y.Item2);
});
});
}
private void CalculateSubNumber(int number, List<Tuple<int, string, int>> allKeys)
{
string text;
for (int i = number; i >= 0; i--)
{
text = i.ToString() + " ";
if (i != number)
{
CalculateOtherNumber(number, i, i, text, allKeys, 1);
}
else
{
InsertProductIntoCollection(text, allKeys);
}
}
}
private void CalculateOtherNumber(int total, int partial, int maxValue, string text, List<Tuple<int, string, int>> allKeys, int counter)
{
int restart = maxValue;
if (partial + restart > total) restart = total - partial;
string bufferText = text;
for (int i = restart; i > 0; i--)
{
text = text + i.ToString() + " ";
if (partial + i == total)
{
InsertProductIntoCollection(text, allKeys);
text = bufferText;
}
else
{
CalculateOtherNumber(total, partial + i, i, text, allKeys, counter + 1);
text = bufferText;
}
}
}
private void InsertProductIntoCollection(string text, List<Tuple<int, string, int>> allKeys)
{
int product = 1, counter = 0;
text.Trim().Split(' ').ToList().ForEach(t => { product *= int.Parse(t); counter++; });
allKeys.Add(new Tuple<int, string, int>(product, text, counter));
}
}
}A differenza del codice precedente, questo salva tutte le serie di numero naturali con il loro prodotto in una collection dictionary; alla fine di tutte le serie eseguo il controllo per vedere se c'è una serie che rispetta quanto detto prima: stesso numero di figli, somma uguale, prodotto e uguale, ma età dei figli per le due serie differenti. La classe qui sopra si può richiamare in modo semplice:
var cs = new CalculateSimpe(); cs.Run(15); // <- numero di tram
Avvio il programma prendendo proprio d'esempio il numero 15 del tram, ma l'output non è quello che mi aspettavo:
################ 15 ################## 40: 10 2 2 1 40: 8 5 1 1 72: 9 2 2 2 72: 8 3 3 1 72: 6 6 2 1 ...
Addirittura ottengo più serie... con il prodotto 40 ottengo due serie, con la serie 72 ottengo addirittura tre serie di numeri naturali... Il secondo matematico, se il tram fosse stato il 15, non avrebbe mai potuto dedurre di aver capito l'età del collega in modo univoco! Penso che la soluzione abbia necessità di maggior potenza... ed ecco il motivo di questa prima parte di post dedicato al calcolo parallelo. Ecco la classe che esegue il calcolo in parallelo di tutti i possibili tram - dal numero 8 al numero 50:
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace tram1
{
public class CalculateConcurrent
{
static object lockWrite = new object();
static Dictionary<int, int> names = new Dictionary<int, int>();
public CalculateConcurrent()
{ }
public void Run()
{
Partitioner.Create(Enumerable.Range(8, 42).ToList(), true).AsParallel().WithDegreeOfParallelism(Environment.ProcessorCount).ForAll(numberFinal =>
{
List<Tuple<int, string, int>> allKeys = new List<Tuple<int, string, int>>();
CalculateSubNumber(numberFinal, allKeys);
var duplicated = allKeys.GroupBy(t => new { product = t.Item1, numbers = t.Item3 }).Where(t => t.Count() > 1).Select(t => t).ToList();
if (duplicated.Count == 1)
{
lock (lockWrite)
{
Console.WriteLine("############ {0} ###############", numberFinal);
duplicated.ForEach(t =>
{
allKeys.Where(y => y.Item1 == t.Key.product && y.Item3 == t.Key.numbers).ToList().ForEach(y =>
{
Console.WriteLine("{0}: {1}", t.Key.product, y.Item2);
});
});
}
}
});
}
private void CalculateSubNumber(int number, List<Tuple<int, string, int>> allKeys)
{
string text;
for (int i = number; i >= 0; i--)
{
text = i.ToString() + " ";
if (i != number)
{
CalculateOtherNumber(number, i, i, text, allKeys, 1);
}
else
{
InsertProductIntoCollection(text, allKeys);
}
}
}
private void CalculateOtherNumber(int total, int partial, int maxValue, string text, ListTuple<int, string, int>> allKeys, int counter)
{
int restart = maxValue;
if (partial + restart > total) restart = total - partial;
string bufferText = text;
for (int i = restart; i > 0; i--)
{
text = text + i.ToString() + " ";
if (partial + i == total)
{
InsertProductIntoCollection(text, allKeys);
text = bufferText;
}
else
{
CalculateOtherNumber(total, partial + i, i, text, allKeys, counter+1);
text = bufferText;
}
}
}
private void InsertProductIntoCollection(string text,List<Tuple<int, string, int>> allKeys)
{
int product = 1, counter = 0;
text.Trim().Split(' ').ToList().ForEach(t => { product *= int.Parse(t); counter++; });
allKeys.Add(new Tuple<int, string, int>(product, text, counter));
}
}
}Il codice precedente viene richiamato in parallelo per quanti sono i core della macchina con questa riga di codice:
Partitioner.Create(Enumerable.Range(8, 42).ToList(), true).AsParallel().WithDegreeOfParallelism(Environment.ProcessorCount).ForAll(...);
Inoltre controllo che ci sia solo una coppia di sequenze di numeri per ogni numero di tram:
var duplicated = allKeys.GroupBy(t => new { product = t.Item1, numbers = t.Item3 }).Where(t => t.Count() > 1).Select(t => t).ToList();
if (duplicated.Count == 1) ...Il momento della verità... eseguo il codice (evito di riportare errori logici e quant'altro di assurdo che avevo scritto durante lo sviluppo) e ottengo in pochi secondi:
Eccolo: il numero 12 è l'unico numero che ha all'interno una sola coppia di sequenze di numeri che sommati e moltiplicati danno lo stesso risultato:
############## 12 ############## 48: 6 2 2 2 48: 4 4 3 1
Vado a riprendere il link con la risposta che mi era stata girata con il quesito... ed è quella esatta - ecco il link con tutta la spiegazione.
Solo in quel momento mi rendo conto della perdita di tempo, quando il tutto era semplice anche con la classe SimpleCalculate: mi bastava inserire a tentativi il numero di tram sempre minore di 15 fino a trovare la singola coppia di serie di numeri che avrei avuto con il 12 (numeri precedenti non avrebbero portato alcuna coppia). Va be', è stato utile per provare la dimostrazione finale...
Un matematico in questo tempo avrebbe risolto questo quesito? Sicuramente in un tempo infinitamente inferiore al mio nello scrivere tutto quel codice.
Piccola curiosità matematica - so dei miei limiti in questo campo, ma se tutti si permettono di sentenziare ricette per risollevare la politica e l'economia Italiana non sapendo la differenza tra un bot e un btp, allora io posso parlare di matematica. Nella tabella successiva ho inserito quattro colonne e i relativi valori calcolati dal mio codice:
O graficamente:
Numero: è il numero naturale cui vengono calcolate le serie.
Serie: numero di serie possibili per ottenere come somma il numero naturale della prima colonna.
Serie1: come sopra, ma nelle serie non sono presenti numeri ripetuti.
Prodotto: numero di prodotti in comune (*)
SerieProdotto: numero di serie che hanno il prodotto in comune (**)
(*) Si ricorderà nel caso del numero 12 che ha due serie che danno come prodotto 48, mentre il numero 13 ne aveva due serie che davano come valore 36 e due serie con 48.
(**) Come nella nota precedente, due nel primo caso (serie convolte nel prodotto comune), e 4 nel secondo.
Interessante la colonna prodotto per avere le serie che hanno lo stesso prodotto. Questa serie può essere utile e calcolata avendone solo il numero naturale nella prima colonna? Se fosse utile potrei chiederlo a Andrew Wiles se può aiutarmi... Però ora devo scusarmi, devo andare a riprendere i vecchi libri di algebra per andare a rinfrescarmi almeno le basi prima che qualche matematico dimostri tutta la mia ignoranza.
Per inserire un commento, devi avere un account.
Fai il login e torna a questa pagina, oppure registrati alla nostra community.
- Asincronia, l'8 febbraio 2014 alle 22:30
- Disabilitare tutti i web control in una pagina?, l'8 luglio 2009 alle 14:21
- C# 4.0 Beta 1, quello che io ho visto, il 24 maggio 2009 alle 20:33