dotNETportal.cz

V minulém postu jsem nastínil, že zmiňovaná implementace funkce RemoveIf má jeden problém. Tento problém se týkal výkonnosti u větších seznamů.

 using System;
 using System.Collections.Generic;
 using System.Linq;
 
 namespace SmartmaniaHra
 {
     public static class ExtensionMethods
     {
         public static void RemoveIf<T>(this List<T> list, Func<T, bool> predicate)
         {
             for (int i = 0; i < list.Count; i++)
                 if (predicate(list[i]))
                     list.RemoveAt(i--);
         }
     }
 }
 

Na tomto místě by bylo vhodné připomenout, jak se třída List chová uvnitř. Pro ukládání prvků se uvnitř používá obyčejné pole (standardní velikost je 4, pokud v konstruktoru toho seznamu neřeknete jinak).

Seznam si pamatuje, kolik prvků už má obsazených, a v případě, že se vnitřní pole zaplní, vytvoří se nové pole, které je dvakrát větší, a prvky z původního pole se překopírují do toho nového. Staré pole se pak zahodí a Garbage Collector se o něj časem postará.

V případě, že nepřidáváte metodou Add, která přidává vždy na konec, ale metodou Insert, kde si můžete říci, kam prvek chcete umístit, musí se část prvků za cílovým místem posunout. Seznam totiž zachovává pořadí prvků. Pokud byste tedy přidávali na začátek seznamu, budou se vždy muset odsunout všechny prvky o 1 doprava, aby se na začátku vytvořilo volné místo.

Mazání funguje stejně jako přidávání, akorát s tím rozdílem, že seznam funguje jako peklo – co schvátí, to už nenavrátí. I kdybyste vymazali vše, seznam si pořád bude držet stejně velké pole, protože předpokládá, že jej časem budete znovu dále plnit.

Nejefektivnější je pochopitelně mazání z konce seznamu – pokud byste mazali ze začátku nebo z prostředka, budou se opět muset některé prvky posunout doleva, aby v seznamu nevznikly díry. A tím jsme se dostali k problému, který naše ukázka kódu má.

V nejhorším případě totiž budou v seznamu všechny prvky vyhovovat zadané podmínce predicate. Funkce RemoveIf tak, jak je napsaná, bude odmazávat prvky ze začátku, a každé takové odmazání bude muset projít celý seznam a posunout ho. Udělá se tak mnoho zbytečných operací.

Je jasné, že některé prvky posunout musíme, co je ale posunout rovnou na jejich finální pozici? Jak to udělat ukazuje následující obrázek – červené prvky nevyhovují podmínce, zelené ano.

Algoritmus může vypadat takto – i je pozice v seznamu, j je počet zelených prvků, které jsme už zpracovali. V případě, že narazíme na červený prvek, nic neděláme a jdeme dál. V případě, že narazíme na zelený, uložíme jej na pozici j a j zvětšíme o 1. Jakmile dojdeme na konec, smažeme všechny prvky větší než j, protože je už nepotřebujeme. Protože bude vždy i menší nebo rovno j, nikdy si nepřepíšeme prvek, který jsme ještě nezpracovali (maximálně uděláme zbytečné přiřazení).

Kód pak může vypadat nějak takto:

 public static void RemoveIf<T>(this List<T> list, Func<T, bool> predicate)
 {
     // sestrkat prvky, které mají zůstat, k sobě
     int j = 0;      // počet zpracovaných prvků, které mají zůstat = finální pozice aktuálního prvku
     for (int i = 0; i < list.Count; i++)    // projít seznam
     {
         if (!predicate(list[i]))        // pokud má prvek v seznamu zůstat...
         {
             list[j] = list[i];      // přesunout ho na finální pozici (j) a posunout j
             j++;
         }
     }
 
     // vymazat všechny prvky větší než j 
     while (list.Count > j)
     {
         list.RemoveAt(list.Count - 1);  // mazat prvky odzadu (aby se neposouvalo)
     }
 }
 

Poslední prvky bychom měli mazat odzadu, aby se opět nemuselo nic posouvat.