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 :).

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 21/12/2009, in .NET, C#, Project Euler and tagged , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s