C# 4.0 LINQ to Object – Zip operator


U prethodnim postovima bilo je dosta govora o novinama u C# 4.0 i VS 2010. Interesantna stvar se pojavila i u LINQ to Object, sa novim operatorom Zip. Ovaj operator nema nikakve veze sa kompresijom, ali sa spajanjem sekvenci ima. Uzmimo jednostavan primjer.

Pretpostavimo da imamo dva polja objekata. Namjerno kažem objekata jer polja mogu biti različiti u smislu da jedno polje ima neki numerički tip, a drugi string ili apstraktni tip ili obrnuto. Npr…

int[] size = { 157, 452 };
string[] fileNames = { "WordDokument1", "WordDokument2" };

Rezultat zipovanja ova dva polja možemo uraditi na sljedeći način:

var res=fileNames.Zip(size, (fname, fsize) => "Velicina datoteke "+fname+" iznosi: " +fsize+" KB.");
foreach(string str in res)
Console.WriteLine(str);

Rezultat zip operacije vidimo na sljedećoj slici:

Kako operator Zip radi?Napišimo deklaraciju operatora odnosno proširene metode:

IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector);

Ako pogledamo deklaraciju ovog operatora vidimo da on uzima dva argumenta, objekat prvog i drugog polja istog indeksa, koji se prosljeđuju Fun delegatu. Fun delegat vraća rezultat koji je u stvari rezultat Zip operatora.

Zip operator ima mnogo primjena u kojima će implementacija vašeg koda biti elegantna i jednostavna. Za ovaj operator izabrao sam primjenu koja na vrlo jednostavan način implementira sabiranje i oduzimanje velikih brojeva. Oko velikih brojeva i izračunavanja decimal broja PI pisao sam u ovom blog postu, u kojem se može pročitati na koji način se veliki brojevi sabiraju i oduzimaju. Metoda koja sabira dva broja prikazana je sljedećim listingom:

public static List<int> Add(List<int> bigNumber1, List<int> bigNumber2)
{
   if (bigNumber1[0] < 0)
      throw new Exception("Number 1 must be a positive!");
   if (bigNumber2[0] < 0)
      throw new Exception("Number 2 must be a positive!");
   //reverse digits
   bigNumber1.Reverse();
   bigNumber2.Reverse();
   var sumBigNumbers = bigNumber1.Zip(bigNumber2, (pp1, pp2) => pp1 + pp2).
   Aggregate(
               new { Digits = new List<int>(), CarryOver = 0 },
               (prev, number) =>
                   {
                     var cumulativeNumber = number + prev.CarryOver;
                     var digit = cumulativeNumber % 10;
                     var carryOver = cumulativeNumber / 10;
                     prev.Digits.Add(digit);
                     return new { Digits = prev.Digits, CarryOver = carryOver };
                   },
               (finalOperation) =>
                  {
                    if (finalOperation.CarryOver != 0)
                     finalOperation.Digits.Add(finalOperation.CarryOver);
                   finalOperation.Digits.Reverse();
                   return new { Digits = finalOperation.Digits, CarryOver = 0 };
                 }
             );
  //reverse digits
  bigNumber1.Reverse();
  bigNumber2.Reverse();
  return sumBigNumbers.Digits;
 }

Agrumenti ove metoda su jednostavne liste brojeva čije vrijednosti prikazuju cifre. Npr. bigNumber={1,3,4,8,9,2} zači da on predstavlja broj 13489, svaka stavka u listi predstavlja cifru. Pozicija stavki u listi je takva da je zadnja stavka predstavlja cifru jedinica, predzadnja stavka cifru desetica itd…

Uslovi da brojevi ne predstavljaju negativne brojeve mora se pretpostaviti jer algoritam sabiranja se bazira čisto na pismenom sabiranju koji smo učili u osnovnoj školi. Pogodnim izborom metoda Add i Substract uvijek je moguće sabrati ili oduzeti bilo koja dva velika broja bili oni negativni ili poitivni.

Naredni dio koda zamjenjuje redoslijed cifara, zbog lakšeg računanja, tako da se brojevi napišu u obrnutom redu.

Sada na scenu stupa operator Zip, koji spaja sekvence na način da svaku cifru prvog broja sabere sa korespodentnom cifrom drugog broja. Naravno zbir mnogih cifara premašuje 9, te se jedinica prenosi u sljedeći rang cifre. Ovaj postupak prenošenja jedinice u sljedeći rang odrađujemo preko operatora Agregate.

Operator Aggregate za prvi argument uzima anonimnu klasu koja sadrži listu cifara i int tip koji treba da se prenese u sljedeci veći rang cifre. Prvi argument je prazan jer počinjemo sa jedinicama, lista je prazna, a broj koji prenosimo (CarryOver) je 0.

Sljedeći argument je (prev , number) agrumenti koji se prenose iz svake sekvence u sljedeću. Prilikom prvog pozivanja drugog delegata oni su jednaki početnim vrijednostima argumenata.

U srednjem delegatu zbrajamo cifru koja je prenešena iz nižeg ranga sa tekućom cifrom. digit varijabla odnosno tekuća cifra se dobija kao ostatak djeljenja kumulattivne cifre sa 10, a broj koji se prenosi u sljedeći rang se dobije kao rezultat djeljenja kumulativne cifre sa 10. Kada su definisane cifre tada tekuće izačunatu cifru stavljamo u listu, a broj koji prenosimo postavljamo u varijablu CarryOver. Na kraju formiramo novu anonimnu klasu kao na početku stim da smo joj pridruđili vrijednosti cifre i ostatka za prenos. Ovaj process se događa dok se sve cifre ne procesuiraju.

Kada se process završi onda se poziva treći delegat koji ima argument naše anonimne klase koju smo vraćali tokom procesuiranja sabiranja. Na kraju je potrebno vidjeti da li je cifra za prenos veća od nule.U potvrdnom slučaju potrebno je dodati još jednu cifru jer je zbir dva broja povećao broj cifara za 1. Na kraju ponovo vraćamo anonimnu klasu koja predstavlja rezultat sabiranja. Na kraju vratimo listu cifara u početni poredak i vratimo listu.

Metoda za oduzimanje dva velika broja slična je prethodnoj samo se koristi logika pismenog oduzimanja. Implementacja metoda Substract izgleda kao na sljedećem listing:

public static List<int> Substract(List<int> bigNumber1, List<int> bigNumber2)
{
   if (bigNumber1 [0] < 0)
      throw new Exception("bigNumber1 must be a positive!");
   if (bigNumber2 [0] < 0)
      throw new Exception("bigNumber2 must be a positive!");

   bool negativeResult = false;
   //Check equality of number of digits
   if (bigNumber1.Count != bigNumber2.Count)
    {
      if (bigNumber1.Count > bigNumber2.Count)
       for (int i = 0; i < bigNumber1.Count - bigNumber2.Count; i++)
        bigNumber2.Insert(0, 0);
     if (bigNumber2.Count > bigNumber1.Count)
      for (int i = 0; i < bigNumber2.Count - bigNumber1.Count; i++)
       bigNumber1.Insert(0, 0);
    }
   //Check if second is grater than first
   for (int i = 0; i < bigNumber1.Count; i++)
    {
       if (bigNumber1[¨i] > bigNumber2[¨i])
        break;
      else if (bigNumber1[ i ] < bigNumber2[ i ])
      {
         List<int> temp = bigNumber1;
         bigNumber1 = bigNumber2;
         bigNumber2 = temp;
         negativeResult = true;
         break;
       }
    }
   bigNumber1.Reverse();
   bigNumber2.Reverse();
   var sumBigNumbers = bigNumber1.Zip(bigNumber2, (pp1, pp2) => pp1 - pp2).
  Aggregate(
               new { Digits = new List<int>(), CarryOver = 0 },
               (prev, number) =>
               {
                 var cumulativeNumber = (number <= 0 ? 20 + (number - prev.CarryOver) : (number - prev.CarryOver));
                 var digit = cumulativeNumber % 10;
                 var carryOver = cumulativeNumber / 10;
                 prev.Digits.Add(digit);
                 return new { Digits = prev.Digits, CarryOver = carryOver };
                },
             (finalOperation) =>
               {
                 Debug.Assert(finalOperation.CarryOver == 0);
                 finalOperation.Digits.Reverse();
                 return new { Digits = finalOperation.Digits, CarryOver = 0 };
               }
             );
   //back reversed digits
   bigNumber1.Reverse();
   bigNumber2.Reverse();
   if (negativeResult)
       sumBigNumbers.Digits[0] = sumBigNumbers.Digits[0] * -1;
   return sumBigNumbers.Digits;
 }

Slično kao u prethodnoj implementaciji Zip operatorom oduzimamo cifre jednu od duge dok agregacijskim operatorom preračunavamo vrijednosti i prenosimo broj u viši rang. Na kraju vraćamo rezultat oduzimanja.

Test za operator Zip možemo implementirati kao na sljedećem listingu:

static void Main(string[] args)
{
   //40 dgit big number
   List<int> bigNumber1 = new List<int>() { 1, 5, 4, 7, 2, 6, 8, 7, 4, 5, 6, 2, 1, 4, 5, 6, 6, 5, 8, 4, 7, 0, 1, 9, 8, 5, 7, 8, 9, 6, 5, 4, 1, 2, 5, 8, 7, 4, 5, 8 };
   //40 dgit big number
   List<int> bigNumber2 = new List<int>() { 5, 2, 4, 5, 3, 4, 7, 0, 2, 4, 6, 1, 7, 3, 4, 0, 8, 7, 0, 1, 3, 2, 3, 5, 4, 6, 4, 3, 2, 2, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1};
   //Result string
   string result = "";
   foreach (int digit in Add(bigNumber1, bigNumber2))
      result += digit.ToString();
   Console.WriteLine("       Result of Add operation is: {0}",result);
   result = "";
   foreach (int digit in Substract(bigNumber1, bigNumber2))
      result += digit.ToString();
   Console.WriteLine("Result of Substract operation is: {0} ", result);
   //Press any key to continue...
   Console.Read();
 }

Formirali smo dva 40-to cifrena broja, te pozvali metodu Add, i ispisali na konzoli rezultat, ista stvar sa metodom Substract.

Ugodno programiranje i nova godina :).

Advertisements

Project Euler i C#


Od 2001 godine pokrenuta je stranica nazvana Project Euler, koja objavljuje zadatke iz matematile koji se rješavaju sa kompjuterskim programima. Do danas je objavljeno 267 zadataka uglavnom iz teorije brojeva koji se rješavaju pogodnim algoritmima. Zadaci koji su postavljeni tiču se teorije brojeva, kombinatorike i vjerojatnosti, a fora je u tome da se nađu pogodni algoritmi koji rješavaju problem. Nekoliko blog stranica rješavaju ove zadatke preko LINQ u C# jer rješenje ovih zadataka čini posebnim, radi same elegancije LINQ upita. Naravno ovim postom nije mi namjera da rješavam sve zadatke postavljene na stranici, ali kroz nekoliko rješenja zadataka može se pokazati prava elegancija i “umjetnost” programiranja sa LINQ i programskog jezika C#.

Problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
Ako prikažemo sve prirodne brojeve manje od 10, koji su multiplikatori brojeva 3 ili 5, dobićemo 3,5,6 i 9. Suma ovih multiplikatora iznosi 23. Pronaći sumu svih multiplikatora 3 ili 5 koji su manji od 1000.

Rješenje:

Pogodnim korištenjem LINQ upita rješenje se dobija u samo jednoj liniji koda:


var rjesenjeP1 = Enumerable.Range(1, 999).Aggregate(0, (parSum, i) => ((i % 3 == 0) || (i % 5 == 0)) ? parSum + i : parSum);

Objašnjenje: Range metoda Enumerable klase daje nam sve prirodne brojeve od 1 do 999, nad kojim vršimo upit prekooperatora Aggregate, koji nam omogućava manipulaciju nad svakim prirodnim brojem u datom intervalu. Ako je neki broj djeljiv sa 3 ili 5 dodaj ga parcijalnoj sumi parSum, čija je početna vrijednost 0, definisana prvim argumentom operatora Aggregate.

Problem 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Svaki član Fibonaccijevog niza dobijen je zbirom prethodna dva. Krenuvši sa 1 i 2, prvih 10 članova niza su:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Potrebno je pronaći sumu svih parnih članova niza manjih od 4 000 000.

Rješenje: Za rješenje ovog problema potreno je implemenirati metodu za vraćanje članova Fibonaccijevog reda.

static IEnumerable<long> FibonacciNiz()
 {
  //Prva dva clana, odnosno prethodna dva
  long a = 1;
  long b = 2;
  //i-ti clan
  long c = 0;
  yield return a;
  yield return b;

 while (true)
  {
   yield return c = a + b;
   //nakon proracuna i-tog clana
   // prethodna dva clana postaju
   a = b;
   b = c;
  }
 }

Nakon što imamo metodu za vraćanje članova Fibonaccievog niza, sada se suma može izračunati kao:

var rjesenjeP2 = FibonacciNiz().TakeWhile(x => x <= 4000000).Sum(x => x % 2 == 0 ? x : 0);

Objašnjenje: Neprestano uzimamo članove Fibonaccievog niza, dok god su članovi manji od 4 miliona. Za to vrijeme pravimo sumu članova koji su parni brojevi odnosno koji su djeljivi sa 2.

Problem 3:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
Prosti faktori broja 13195 su 5,7,13 i29. Pronaći najveći prosti faktor broja 600851475143.

Rješenje: Metoda za rastavljanje na proste faktore implementirana je u blog postu o yield naredbi, koju ćemo iskoristiti za rješavanje ovog problema. Međutim, potrebno je metodu prilagoditi ovom problem u smislu 64-bitnog integera, pa u metodi gdje se koristio int,potrebno je staviti long. Implementacija je prikazana u narednom tekstu:

//Rastavljanje broja n na proste faktore n=n1*n2*n3*...nn
public static IEnumerable<string> Foktoriziraj(string izraz, longn)
{
  //Ako je 1 vrati izraz
  if (n == 1)
    yield return izraz;
  else
  {
    //Prolazimo sve brojeve manje od n
    for (long i = 2; i <= n; i++)
     {
       //Ako je n djeljiv sa i
       if ((n % i) == 0)
        {
          long q = n / i;
          //Zapišimo u izraz broj i
          if (!izraz.EndsWith("= "))
             izraz += " * ";
          izraz += i.ToString();
          //Nad djeljiteljem q ponovimo isti postupak rekurzivno
          foreach (string podizraz in Foktoriziraj(izraz, q))
            yield return podizraz;
            yield break;
        }
     }
  }
}

Kada ovu metodu pozovemo na sljedeći način:

Console.WriteLine(Foktoriziraj(600851475143.ToString() + " = ", 600851475143).SingleOrDefault());

Dobićemo rezultat kao na slici.

Objašnjenje metode  se može pronaći na blog postu o yield komandi.

U nekom od sljedećih postova biće prikazana rješenja drugih interesantnih problema.

BHGridCtrl – Zadnja implementacija


Zadnja implementacija BHGridCtrl projekta, podrazumijevala je povezivanje tabela sa bazom podataka preko ADO. Zadnjom verzijom podaci koji se učitaju nije moguće vršiti modifikaciju. Za zadnji primjer potrebno je imati instaliran SQL server i NorthWind bazu podataka. Svi podaci u tabeli se mogu isprintati i implementirane su funkcije za printanje GridKontrole, zaglavlja i podnožja. Primjer sa zadnjom implementiranom verzijom BHGriCtrl možete skinuti sa ovog  linka. Primjer je kompajliran sa VS 2008.