Vyhodnocení hádanky: Odstranění více položek ze seznamu

Tomáš Herceg       3. 11. 2011       C#       6237 zobrazení

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.

Schéma algoritmu

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.

 

hodnocení článku

1 bodů / 1 hlasů       Hodnotit mohou jen registrované uživatelé.

 

Nový příspěvek

 

Diskuse: Vyhodnocení hádanky: Odstranění více položek ze seznamu

Díky, super!

nahlásit spamnahlásit spam 1 / 1 odpovědětodpovědět

Diskuse: Vyhodnocení hádanky: Odstranění více položek ze seznamu

Ahoj Tomáši,

nestačilo by na konci zavolat metodu RemoveRange? Nebo i ta je napsána špatně?

http://msdn.microsoft.com/en-us/library/...

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Ta určitě není napsána špatně, jen jsem chtěl, aby bylo vidět správné použití RemoveAt. A nejsem si jistý, jestli je ve Frameworku na Windows Phone 7, kvůli kterému vlastně tato hádanka vznikla.

nahlásit spamnahlásit spam 0 odpovědětodpovědět
                       
Nadpis:
Antispam: Komu se občas házejí perly?
Příspěvek bude publikován pod identitou   anonym.

Nyní zakládáte pod článkem nové diskusní vlákno.
Pokud chcete reagovat na jiný příspěvek, klikněte na tlačítko "Odpovědět" u některého diskusního příspěvku.

Nyní odpovídáte na příspěvek pod článkem. Nebo chcete raději založit nové vlákno?

 

  • Administrátoři si vyhrazují právo komentáře upravovat či mazat bez udání důvodu.
    Mazány budou zejména komentáře obsahující vulgarity nebo porušující pravidla publikování.
  • Pokud nejste zaregistrováni, Vaše IP adresa bude zveřejněna. Pokud s tímto nesouhlasíte, příspěvek neodesílejte.

přihlásit pomocí externího účtu

přihlásit pomocí jména a hesla

Uživatel:  
Heslo:  

zapomenuté heslo

 

založit nový uživatelský účet

zaregistrujte se

 
zavřít

Nahlásit spam

Opravdu chcete tento příspěvek nahlásit pro porušování pravidel fóra?

Nahlásit Zrušit

Chyba

zavřít

feedback