Indexera dina kollektioner i c# för bättre prestanda

När man jobbar med kollektioner i .net och behöver filtrera för att hämta ut bara vissa poster så kan man göra på många sätt.
Ett sätt är att loopa igenom hela kollektionen och kontrollera med if-satser om den aktuella posten motsvarar kriterierna.
Ett annat sätt är att använda linq och sätta upp kriterierna via where-villkoret.

Problemet med båda ovanstående är att prestandan kanske inte alltid är så bra som man önskar sig.
Därför vill jag tipsa om att man kan indexera sina kollektioner för att få bättre prestanda.

Såhär ser de krieria ut som jag vill jobba med mot min kollektion

int sex = 1;
int fromAge = 20;
int toAge = 45;
List<int> cityIds = new List<int>();
cityIds.AddRange(new List<int>{1,3,5,6,7,8,15,26,39,45,30,29,28,31});

Baskollektionen som jag kommer att loopa igenom innehåller 20000 poster. När filtreringen är klar så skall ungefär 1300 poster vara kvar. Antalet varierar eftersom jag skapar de 20000 med slumpmässig data. Dock är testerna körda på exakt samma data eftersom jag först skapar de slumpmässiga posterna och därefter kör alla tester. Tiderna ni ser nedan är snittider efter att jag har kört testen flera gånger.

Först ett kodexempel där vi loopar igenom hela kollektionen och lägger slutligen bara till de poster som matchar det som vi letar efter i found-kollektionen.

for (int i = 0; i < users.Count; i++)
{
    User user = users&#91;i&#93;;
    if (user.Sex == sex)
    {
        if (cityIds.Contains(user.CityId))
        {
            if (user.Age >= fromAge && user.Age < = toAge)
            {
                found.Add(user);
            }
        }
    }
}
&#91;/sourcecode&#93;

Ovanstående kod exekverar på ungefär 18ms på min dator.

Motsvarigheten i linq skulle kunna se ut såhär
&#91;sourcecode lang="csharp"&#93;found = (from u in users where 
    u.Sex == 1 
    && cityIds.Contains(u.CityId) 
    && u.Age >= fromAge 
    && u.Age < = toAge 
select u).ToList();
&#91;/sourcecode&#93;

Exemplet med linq exekverar på ungefär 18ms på min dator. Alltså samma tid som att loopa igenom "manuellt", men som synes kräver linq-varianten betydligt mindre kod.

En viktig detalj är att om man ändrar i vilken ordning man ställer upp where-villkoren så kommer tiden det tar att filtrera posterna att ändras dramatiskt.
Nedanstående exempel där jag bytt plats på när sex och age testas tar nu istället 120ms. Allt beror på hur många rader som filtreras bort vid respektive where-villkor.

&#91;sourcecode lang="csharp"&#93;found = (from u in users where 
    u.Age >= fromAge 
    && u.Age < = toAge 
    && cityIds.Contains(u.CityId)
    && u.Sex == 1
select u).ToList();
&#91;/sourcecode&#93;

Om vi istället indexerar och därmed duplicerar datat mångaldigt så kommer det att ta mer minne, dessutom kommer indexeringen att ta tid. Men om kollektionen förändras ganska sällan så kan man cacha både kollektionen och dess index. Det är främst då indexering av kollektioner blir användbart.

Det vi måste görs först är att skapa index, och för det loopar vi igenom hela vår befintliga kollektion och för varje post så stoppar den aktuella posten i motsvarande index. 
Enkelt förklarat så delas varje del man vill filtrera på upp i varsitt index. Som exempel kan vi ta user.sex där det finns två varianer man eller kvinna. Alla män hamnar i en egen kollektion och alla kvinnor i en egen.

Kod för att skapa index
&#91;sourcecode lang="csharp"&#93;//Skapa en kollektion för att spara användare av olika kön
Dictionary<int, List<int>> sexIndex = new Dictionary<int , List<int>>();

//Eftersom vi vet att det bara finns två kön så kan vi skapa dessa poster direkt. Notera att varje post i kollektionen innehåller en egen kollektion.
//Det är i denna kollektion vi kommer att placera antingen män eller kvinnor.
sexIndex.Add(1, new List<int>());
sexIndex.Add(2, new List<int>());

//Skapa en kollektion för att spara användare från olika städer
Dictionary<int , List<int>> cityIndex = new Dictionary<int , List<int>>();

//Skapa en kollektion för att spara användare med olika åldrar
Dictionary<int , List<int>> ageIndex = new Dictionary<int , List<int>>();

for (int i = 0; i < users.Count; i++)
{
    User user = users&#91;i&#93;;

    //Eftersom vi redan har skapat posterna i sexIndex kan vi direkt lägga till den aktuella posten i kollektionen
    sexIndex&#91;user.Sex&#93;.Add(i);

    //Här skapar vi en kollektion för att placera alla användare i olika städer.
    List<int> cityList;

    //Vi kontrollerar om kollektionen redan har den aktuella staden, om inte så går vi in i if-satsen och skapar den.
    //Om staden redan finns i kollektionen så populeras cityList med de städer som redan finns (out cityList)
    if (!cityIndex.TryGetValue(user.CityId, out cityList))
    {
        //Lägg till den aktuella staden i kollektionen och skapa listan som håller användarna
        cityList = new List<int>();
        cityIndex.Add(user.CityId, cityList);
    }
    cityList.Add(i);


    List<int> ageList;
    if (!ageIndex.TryGetValue(user.Age, out ageList))
    {
        ageList = new List<int>();
        ageIndex.Add(user.Age, ageList);
    }
    ageList.Add(i);

}

Ovanstående indexering tar ungefär 57ms, vilket alltså är väldigt kostsamt. Vi kan redan nu konstatera att indexera kollektioner endast är användbart när man kan ställa flera frågor mot samma index utan att behöva bygga om det.

Notera att indexen ovan inte innehåller referenser till användarobjekten utan istället den aktuella position som de har i kollektionen users. Jag förklarar senare varför.

Nu när användarna är segmenterade i olika listor så kommer vi att vilja slå ihop de listorna som vi söker.
Exempelvis om vi vill hämta endast de som är 40-41 år så kommer listan med alla 40-åringar slås ihop med listan med alla 41-åringar.

När det är klart behöver vi ta resultatet från ålderslistan, stadslistan och könslistan och skapa en ny lista med de poster som finns i samtliga tre listor.

För att slå ihop två listor använder vi UnionWith. Exempel på det är om lista A innehåller {a,b,c} och lista B innehåller {a,d} så kommer lista C (a.UnionWith(b)) att innehålla {a,b,c,d}.
När man vill skapa en lista som innehåller endast de poster som finns i båda listorna så använder vi IntersectWith. Exempel på det är om lista A innehåller {a,b,c} och lista B innehåller {a,b,d,e} så kommer lista C (a.IntersectWith(b)) att innehålla {a,b}.

Nedan visar jag ett kodexempel på hur det faktiskt ser ut i kod.
//Här skapas kollektionen som skall innehålla posterna
HashSet index = new HashSet();

//Skapa en ny kollektion och slå ihop listorna med användarna från alla städer som vi söker
HashSet citySearchIndex = new HashSet();
foreach (int cityId in cityIds)
{
if (cityIndex.ContainsKey(cityId))
citySearchIndex.UnionWith(cityIndex[cityId]);
}

//Skapa en ny kollektion och slå ihop listorna med användarna från alla åldrar som vi söker
HashSet ageSearchIndex = new HashSet();
for (int i = fromAge; i < = toAge; i++) { if (ageIndex.ContainsKey(i)) ageSearchIndex.UnionWith(ageIndex[i]); } //Slå ihop den tomma listan med användarna med det kön vi söker index.UnionWith(sexIndex[sex]); //Bygg om index så att den endast innehåller de användarna som finns i både index-kollektionen och citySearchIndex-kollektionen index.IntersectWith(citySearchIndex); //Bygg om index så att den endast innehåller de användarna som finns i både index-kollektionen och ageSearchIndex-kollektionen. index.IntersectWith(ageSearchIndex); //Loopa igenom vår kollektion som innehåller positionen på de användare vi söker och placera i en ny kollektion men denna gång då den innehåller de riktiga användarobjekten. foreach (int i in index) { found.Add(users[i]); } [/sourcecode] Anledningen till att vi går omvägen med att använda position (integer) istället för att direkt köra Union/Intersect mot kollektioner av User-objektet (vilket är fullt möjligt) är att det är flera gånger snabbare att använda en enkel datatyp, som i vårt fall integer, istället för ett helt objekt. Detta beror på att HashSet (som namnet antyder) hashar objekten som sparas i kollektionen och det tar mer tid ju mer data som skall hashas. Ovanstående sökning tar 3ms. Detta betyder alltså att det redan efter 4 sökningar mot indexet är ett snabbare alternativ, trots den tunga initialkostnaden på 57ms för att skapa indexet. Värt att notera är att tekniken även fungerar bra när få poster returneras. Som exempel testade jag att hämta ut omkring 1-10 poster från samma datamängd på 20000. Resultatet blev att loopen/linq gör det på ungefär 2,6ms. Sökningen via index går på ungefär 0,3ms. Det går att förbättra sökningen med hjälp av index ytterligare. Om vi bryter ut följande kod [sourcecode lang="csharp"]HashSet ageSearchIndex = new HashSet();
for (int i = fromAge; i < = toAge; i++) { if (ageIndex.ContainsKey(i)) ageSearchIndex.UnionWith(ageIndex[i]); } [/sourcecode] Så kan denna skrivas om så att den cachar innehåller i ageSearchIndex efter loopen. Samt innan den går in i loopen kontroller i cachen om den färdiga listan redan finns att hämta. Här är kodexempel på hur det kan se ut där listan cachas i 60 minuter. Notera dock att om kollektionen users byggs om så måste denna cachen uppdateras. Samma sak går givetvis att göra med citySearchIndex. [sourcecode lang="csharp"]string ageCacheKey = "ageSearchIndex_" + fromAge + "-" + toAge; HashSet ageSearchIndex = (HashSet)Cache[ageCacheKey];
if (ageSearchIndex == null)
{
ageSearchIndex = new HashSet();
for (int i = fromAge; i <= toAge; i++) { if (ageIndex.ContainsKey(i)) ageSearchIndex.UnionWith(ageIndex[i]); } Cache.Add(ageCacheKey, ageSearchIndex, null, DateTime.Now.AddMinutes(60), System.Web.Caching.Cache.NoSlidingExpiration, System.Web.Caching.CacheItemPriority.Default, null); }[/sourcecode]

1 kommentar

  1. […] vid 21:51 · Arkiverad under .net, Prestanda När jag satt och förberedde mitt inlägg om indexera dina kollektioner i c# för bättre prestanda så provade jag med flera versioner av .net, bland annat 2.0, 3.5 och 4.0 beta 1. Jag märke då […]

RSS feed for comments on this post

Kommentarer inaktiverade.

%d bloggare gillar detta: