LINQ és a lineáris keresés

Élő kódokban láttam több alkalommal az alábbi, nagyon pazarló eljárást. Adva van n darab objektum példányom, amivel dolgozom. Vegyünk egy egyszerű típust:

public class Stuff
{
   public int Id { get; set; }
} // class Stuff

A példányokat jellemzően így hordozom a programban:

List<Stuff> stuffs = ...

Hogy ez most lokális változó, vagy valamilyen osztály mezője, az teljesen mindegy. A lényeg, hogy olyan műveletet implementálok, amiben kapok egy másik listát:

List<int> isoCompatibleStuffIds = ...

Esetleg:

IEnumerable<int> isoCompatibleStuffIds = ...

A feladatom, hogy a saját stuffjaim közül kiválogassam az iso kompatibiliseket:

var isoCompatibleStuffs =
        from s in this.stuffs
        where isoCompatibleStuffIds.Contains(s.Id)
        select s;

vagy mindegyik iso kompatibilis stuffal elvégzek egy műveletet:

foreach (var stuff in this.stuffs)
{
  if (isoCompatibleStuffIds.Contains(stuff.Id))
  {
    DoSomething(stuff);
  } // if
} // foreach

A lényeg a isoCompatibleStuffIds.Contains(stuff.Id) részen van, ami nyiltan vagy kicsit bújtatva egy ciklusban helyezkedik el.

Tömbökre hangolódva

A tanuló programozók, amikor először szembesülnek azzal a feladattal, hogy több, hasonszőrű dolgot kell tárolniuk/kezelniük, a tömböket (array) fogják megtalálni. A tömb egy egyszerű eszköz, jól ábrázolható a számítógépek memóriájában, legtöbb programozási nyelv közvetlenül támogatja őket. A tömb lényegében annak a számítógépes analógiája, amit a mindennapi életünkben egy sor vagy listázott “valaminek” látunk (az angol array szó ezt sokkal jobban kifejezi, mint a magyarított tömb)

A tömb azonban mást is tud, mint amire szükség van akkor, ha csak annyi a feladat, hogy valahány dolgot kell tárolni. A tömb ugyanis egy rendezést is kifejez az elemek között. Néha ez szükséges tulajdonság (például ha neveket névsorban akarunk használni) sokszor viszont csak egy következménye annak, ahogy a tömb, mint adatszerkezet fel van építve.

De más következménye is van annak, ahogy a tömb, mint adatszerkezet fel van építve: máshogy nem is tudunk benne egy adatot elérni, csak ha tudjuk a tömb által leírt rendezés szerinti sorszámát. Ismertebb kifejezéssel élve, tudjuk az indexét.

Ha nem tudjuk az elérni kívánt adat indexét, akkor azt meg kell keresnünk. Ha a tömb által leírt rendezés a gyakorlatban is használható relációt fejez ki (például az adatok névsor szerint következnek a tömbben, és mi tudjuk az adat által leírt nevet), akkor használhatjuk a bináris keresést, ezt alkalmazva viszonylag kevés számú lépéssel megtalálhatunk egy adatot a tömbben. Ha azonban a tömb által leírt rendezés nem ad támpontot, akkor kénytelenek vagyunk próbálgatással meghatározni az adat helyét, például az első indextől kezdve, egyesével haladva.

Miért érdekes ez? Azért, mert a fentiek olyan mélyen belénk ivódtak, hogy esetleg nem is gondolunk rá, hogy másként, nem tömb vagy lista jelleggel is lehet több objektumot kezelni.

Fertőzött absztrakciók

A modern programozási nyelvek osztálykönyvtárakkal érkeznek, melyekben találhatóak különböző adatszerkezetek, például több dolog együttes kezelésére. Ezeket kollekció osztályoknak hívjuk, a .NET framework több ilyen osztállyal érkezik. A kollekció osztályok gyakran hasonló műveletekkel bírnak, és hogy egy adott algoritmus vagy programrész több különböző típusú adatszerkezettel is használható legyen, a műveletek interfészeken keresztül is elérhetőek.

Ahogy vannak egyszerűbb tudású és bonyolultabb adatszerkezetek, a műveletek is több szintre vannak bontva, ezáltal több interfészbe vannak csoportosítva. Ami érdekes, hogy az első .NET verziókban ezeket az interfészeket csúnyán elhibázták.

Mi lehet egy értelmes minimális igény egy adatszerkezettel vagy objektummal szemben, amelynek a célja, hogy több dolog kezeléséről gondoskodjon? Például, hogy a kezelt dolgokat sorra tudjuk venni feldolgozás céljából. Ezt szolgálja ki az IEnumerable interfész, amely mindössze annyit tud, hogy el lehet rajta keresztül érni egy enumerátort, ami viszont képes sorra venni a kezelt elemeket. Az az adatszerkezet (vagy objektum), ami megvalósítja az IEnumerable interfészt, nem kell, hogy képes legyen megmondani, hogy hány elemet tart karban. Az IEnumerable-t tehát úgy lehet elképzelni, hogy egy lyukba nyúlkálva rántjuk elő a dolgokat, és nem tudjuk előre, hogy találok-e még majd valamit, vagy nem, illetve nem tudunk célzottan elővenni adott dolgot.

A következő absztrakciós színt a korai .NET verziókban az ICollection. Ez az interfész – amellett, hogy nagyon ide nem illően foglalkozik a párhuzamos programozás során felmerülő szinkronizációs problémákkal – bevezeti a Count property-t. Egy ICollection tehát annyival egészíti ki a fent említett lyukas oldalú dobozt, hogy fel van címkézve egy számmal. Ez nem túl sok plusz, főleg, hogy a kollekció vagy gyűjtemény intuitíven valami olyasmit jelent, amit lehet bővíteni, vagy belőle elvenni. No nem baj, majd hátha a következő absztrakciós szint.

Csakhogy a korai .NET verzióban ez a következő szint nem más, mint az IList. Miért gond ez? Azért, mert az IList annak a szellemében készült, ahogy a neve azt sugallja: listáról van szó, azaz sorba vett dolgokról, ami által a dolgok között definiált egy rendezési reláció is – akár értelmes, akár véletlenszerű rendezésről van szó. Hirtelen ott találjuk magunkat a tömb általánosított verziójánál, anélkül, hogy lett volna olyan interfészünk, amivel dolgokat rendezetlenül lehet tárolni. Az IList megengedi elemek hozzáadását és elvételét, ami jó, ugyanakkor rendelkezik egy IndexOf() metódussal is. Azaz ha valakinek kevés az ICollection (mert hozzáadni, elvenni szeretne, nem csak Count-ot viszaadni, meg enumerálni), akkor kénytelen bevállalni az IndexOf()-ot, ezzel együtt egy rendezettséget is.

Nem rendezett kollekciók

Látszik, hogy a System.Collections névtérben található interfészek, osztályok tervezője nem tudott elszakadni az indexekkel használt tömböktől. Pedig régóta ismertek olyan adatszerkezetek, amelyek más módon tárolják az elemeiket. Egy ilyen adatszerkezet a hash tábla. Hash tábla esetén nincs értelme a tárolt adatok között bármiféle rendezésről beszélni. Emiatt nehéz volna megvalósítani az IList interfész IndexOf(), InsertAt() metódusait. Ha régebbi .NET verzió alá szeretett volna egy fejlesztő hash táblán alapuló adatszerkezetet készíteni, gondban volt.

.NET 1 és a hash tábla

A helyzet az, hogy hash táblán alapuló adatszerkezet a .NET korai verziójában is része volt a framework-nek. Hogy oldották meg a fenti problémát? Nem túl elegánsan készítettek egy másik interfészt, az IDictionary-t, amely az IndexOf() és egyéb index függő metódusokat leszámítva duplikálja az IList interfészt. Az IDictionary viszont nem feltétlenül segít általánosabb helyzetekben, mivel van néhány metódusa/property-je, ami csak asszociatív (vagy map vagy szótár) jellegű adatszerkezeteknél használható, és nem biztos, hogy a fejlesztő ilyet szeretne. Ha nekem kell az Add/Remove, akkor .NET 1-nél vagy IList-ezek, és akkor meg kell valósítani az IndexOf()-ot, vagy IDictionary-zek, és akkor kellenek az asszociatív jelleget kiszolgáló property-k, mint a Keys/Values. Harmadik megoldásként bevállalom, hogy az adatszerkezetemet nem lehet a .NET-be szánt általános interfészeken keresztül működtetni (leszámítva az IEnumerable-t).

Kollekciók újragondolva

A .NET 2 bevezette a generikus típusokat, ezzel együtt pedig jöttek a generikus interfészek. Ezt a lehetőséget kihasználták a kollekciók körüli problémák orvosolására, és kicsit átdolgozták az absztrakciós határokat. Az IEnumerable<T> ugyanolyan, mint a nem generikus párja. Az ICollection<T> viszont megkapta azokat a metódusokat, amit korábban a túl tömb orientált gondolkodás miatt az IList-be raktak. Egy kollekció immár azt jelenti, ami: meg tudja mondani hány eleme van (mint régen) és lehet hozzáadni, elvenni elemeket, illetve meg tudja mondani, hogy adott elemet tartalmaz-e. Az IList<T>-ben csak az index specifikus metódusok maradtak.

Miért örülünk?

A cikk elején bemutattam egy kódrészt, amit egy alkalmazásban sorozatban láttam elkövetni. A gondot az okozza, hogy egy listát használnak objektumok tárolására. Ez nyilván a túl tömb orientált gondolkodásból, vagy a .NET 1-ben rögzült rossz reflexekből jön. Amire a fenti programban szükség van, az valamilyen ICollection<int> implementáció, ami a Contains() metódust úgy valósítja meg, hogy ne kelljen végig enumerálni az elemeket, mint ahogy a tömböknél (List-nél) vagy natúr IEnumerable nél kell.

Korábban képbe jött már a hash tábla. Ilyet a .NET 1 is tartalmazott Hashtable néven, később a generikus párját átnevezték Dictionary<K,V>-re, ami névvel egyet tudok érteni. A hash tábla ugyanis általánosabb adatszerkezet, és nem feltétlenül csak asszociatív jelleggel lehet használni.

Halmaz kollekció

A .NET 3.5-tel jött egy új kollekció osztály, amelynek a célja, hogy objektumok egy csoportját halmazként használhassul. Ez az osztály a HashSet<T>. A HashSet<T> az ICollection<T> interfészt is megvalósítja (és így az IEnumerable<T>-t is), tehát lehet hozzáadni, elvenni elemeket, illetve meg tudja mondani, hogy tartalmaz-e adott elemet (Contains() metódus). A halmazokkal szemben feltett leggyakrabb kérdést egyébként pont a Contains() metódus valósítja meg (“b eleme H halmaznak”), emiatt a HashSet<T> implementációja olyan, hogy ezt a kérdést nagyon hatékonyan meg tudja válaszolni, aki ismeri a hast tábla működését, tudja is, hogy miért.

Mit nyertünk?

Ott tartunk tehát, hogy elviekben, ha a cikk elején látható program az ISO kompatibilis stuff-ok ID-it nem listaként, hanem halmazként kezelné, akkor a leválogatás gyorsabban menne. Mennyivel? Ez nyilván nagyon függ az elemszámtól. Kevés elemnél (néhányszor tíz) valószínű nem jelentős a különbség, esetleg a lista még gyorsabb is, mivel nem kell hash számításokkal bajlódni. Ezres mérettartományban viszont már jelentős lehet a különbség, ahogy az alábbi program eredménye mutatja:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace LinqLinSearch
{
    public class Stuff
    {
        public int Id { get; set; }
    } // class Stuff

    public class StuffRepository
    {
        private List<Stuff> stuffs = new List<Stuff>();

        public StuffRepository()
        {
        } // StuffRepository()

        public StuffRepository(IEnumerable<Stuff> stuffs)
        {
            this.stuffs.AddRange(stuffs);
        } // StuffRepository()

        public void Add(Stuff stuff)
        {
            this.stuffs.Add(stuff);
        } // Add()        

//!!!!! public static readonly HashSet<int> IsoCompatibleStuffIds = GenerateIsoCompatibleStuffIds();
        public static readonly List<int> IsoCompatibleStuffIds = GenerateIsoCompatibleStuffIds();

//!!!!! private static HashSet<int> GenerateIsoCompatibleStuffIds()
        private static List<int> GenerateIsoCompatibleStuffIds()
        {
            var rnd = new Random();
//!!!!!     var result = new HashSet<int>();
            var result = new List<int>();

            for (int i = 0; i < 1000; i++)
            {
                result.Add(rnd.Next(100000));
            } // for i

            return result;
        } // GetIsoCompatibleStuffIds()

        public StuffRepository GetIsoCompatibleStuffs()
        {
            var isoCompatibleIds = IsoCompatibleStuffIds;
            var result = new StuffRepository();

            var isoCompatibleStuffs =
                    from s in this.stuffs
                    where isoCompatibleIds.Contains(s.Id)
                    select s;

            return new StuffRepository(isoCompatibleStuffs);
        } // GetIsoCompatibleStuffs()
    } // class StuffRepository

    class Program
    {
        static void Main(string[] args)
        {
            var rnd = new Random();
            var repository = new StuffRepository();

            for (int i = 0; i < 10000; i++)
            {
                repository.Add(
                    new Stuff
                    {
                        Id = rnd.Next(100000)
                    });
            } // for i

            var sw = Stopwatch.StartNew();

            for (int i = 0; i < 100; i++)
            {
                var result = repository.GetIsoCompatibleStuffs();
            } // for i

            Console.WriteLine(sw.ElapsedMilliseconds);
        } // Main()
    } // class Program
} // namespace LinqLinSearch

A tesztet futtatva a lista kb 7300ms alatt végez, míg a halmaz 77ms alatt, tehát a különbség már százszoros. Ahogy az elemek számát növeljük, a különbség annál erőteljesebb.

Na de hogy jön ide a LINQ?

Aki figyelmes, észrevehette, hogy bár a példaprogram tartalmaz LINQ kifejezést, maga Contains() hívás ott nem a LINQ dolga, hanem a HashSet/List valósítja meg. A LINQ-val az a probléma, hogy a hozzá adott, és Enumerable osztály által extension metódusként megvalósított metódushalmaz mindegyike IEnumerable<T> paraméteren dolgozik:

public static class Enumerable
{
    // Methods
    public static TSource Aggregate<TSource>(this IEnumerable<TSource> source, ...);
    public static bool All<TSource>(this IEnumerable<TSource> source, ...);
    public static bool Any<TSource>(this IEnumerable<TSource> source);
    public static bool Any<TSource>(this IEnumerable<TSource> source, ...);
    ...
    public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value);
    public static int Count<TSource>(this IEnumerable<TSource> source);
    ...
}

Az, hogy az Enumerable osztály statikus függvényei IEnumerable<T>-t használnak, egyrészt jó, mert így nagyon általánosak. Bármint képesek működni, ami az egyszerű IEnumerable<T> interfészt megvalósítja. Másrészt, egy IEnumerable<T> interfész segítségével az Enumerable.Contains() implementációnak nincs más választása, mint végigiterálni az elemeken, hogy megnézze, megtalálható-e a keresett elem, és visszajutottunk a listák problémájához. Így hiába használunk esetleg HashSet<T>-et, ha azt IEnumerable<T> paraméterű metódusnak adjuk át, ami pedig használja a LINQ extension metódusait, akkor az belassul:

private IEnumerable<Stuff> GetIsoCompatibleStuffs(IEnumerable<int> isoCompatibleIds)
{
    return  from s in this.stuffs
            where isoCompatibleIds.Contains(s.Id)
            select s;
} // GetIsoCompatibleStuffs()

A fenti függvényt hiába hívjuk HashSet-tel, a kód csak az Enumerable.Contains()-t hívja, ami pedig csak az enumerátort tudja végighajtani a kereséshez. Vagy nem?

Nesze neked nagykönyv!

Egy szépen megírt kód jól absztrahált interfészeken keresztül dolgozik, és nem használ futásidejű típusinformációkat, főleg nem if-ekben, switch-ekben. Na, hallott már valaki ilyet? Én igen, és adott esetben egyet tudok ezzel érteni. Vannak azonban olyan helyzetek, amikor a típus ismeretében jelentős optimalizációt lehet végrehajtani, ezért megérheti ráellenőrizni a típusra, és aszerint elágaztatni a kódot. Igen, igen, most azt kockáztatom, hogy éjszaka elvisznek a design pattern zombik, és valami S.O.L.I.D. vagy más buzzword tetkót égetnek a homlokomba, hogy tudjak mind gondolkodni reggel a tükörben. Szerencsére a Microsoftnál nem ennyire finnyásak:

public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value)
{
    ICollection<TSource> is2 = source as ICollection<TSource>;
    if (is2 != null)
    {
        return is2.Contains(value);
    }
    return source.Contains<TSource>(value, null);
}

Mit látunk? Ez az Enumerable.Contains() kódja. Első lépésben megnézi, hogy az IEnumerable<T> paraméter véletlenül nem-e ICollection<T>. Miért jó ez? Mert az ICollection<T> rendelkezik Contains() metódussal, ami az adott implementáció natív megoldása. Ha ezt sikerül meghívni, a natív Contains() várhatólag gyorsabban képes végrehajtani a műveletet, mint amit az elemek végigenumerálásával el lehet érni. Ez lehetővé teszi, hogy akkor is kihasználjuk például a HashSet<T> előnyeit, amikor azt egy IEnumerabe<T> típusú paraméteren keresztül kell átadnunk.

Konklúzió

A programozók nagyon megszokták a tömbök, illetve annak dinamikus megvalósításának, a List<T> osztálynak a használatát. Ez sokszor nem okoz gondot, lehetnek viszont esetek, amikor más jellegű adatszerkezetek hatékonyabbnak bizonyulnak. A fejlettebb adatszerkezetek képességei a LINQ által hozott, IEnumerable<T> interfészhez készített metódusokban sem veszik el, mivel a LINQ implementációja ahol érdekes lehet, megpróbálja a paramétert magasabb rendű interfészen keresztül használni.

A fentiek miatt nagyobb elemszám esetén érdemes az adatokat egy HashSet<T>-be tölteni:

IEnumerable<int> temp = ...;
var isoCompatibleStuffIds = new HashSet(temp);
var result = GetIsoCompatibleStuffs(isoCompatibleStuffIds);

...

private IEnumerable<Stuff> GetIsoCompatibleStuffs(IEnumerable<int> isoCompatibleIds)
{
    return  from s in this.stuffs
            where isoCompatibleIds.Contains(s.Id)   // Most már gyors lesz
            select s;
} // GetIsoCompatibleStuffs()
  1. #1 by Ádám on 2011. September 8. - 18:20

    Nagyon jó cikk! Hasznos volt elolvasnom! Köszi!

  2. #2 by Tóth Viktor on 2011. September 8. - 18:54

    Köszönöm🙂

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

%d bloggers like this: