2008.09_C5 nowoczesna biblioteka kolekcji dla .NET_[Biblioteka Miesiaca].pdf

Biblioteka miesiąca

nowoczesna biblioteka kolekcji dla .NET

Artykuł ten dotyczy C5, czyli nowej biblioteki kolekcji dla .NET stworzonej

na Uniwersytecie IT w Kopenhadze w Danii przez Niels’a Kokholm oraz

Peter’a Sestoft. C5 nie tylko jest użyteczną biblioteką kolekcji ale również

nowym podejściem do wykorzystania kontenerów w .NET.

Dowiesz się:

• Czym jest biblioteka kolekcji C5 i jakie są jej

zastosowania;

• Jak efektywnie użyć kontenerów dostępnych

w ramach tej biblioteki;

• Jakie są wady i zalety C5.

Powinieneś wiedzieć:

• Czytelnik powinien znać podstawy programo-

wania w języku C#;

• Czytelnik powinien posiadać podstawową

wiedzę z zakresu struktur danych i algoryt-

mów.

przez te kolekcje. Co więcej SCG zostały za-

projektowane w celu przyspieszenia operacji

na niewielkich ilościach danych (dbając o sta-

łe współczynniki przy złożoności obliczenio-

we operacji). W C5 zdecydowano się nie dbać

o stałe współczynniki w złożoności obliczenio-

wej dając bardziej bogate właściwości. Niedo-

ciągnięcia SCG miała uzupełnić biblioteka Po-

wer Collections Peter’a Golde z firmy Wintel-

lect. Biblioteka ta wniosła dodatkowe struktu-

ry danych oraz algorytmy, co jest zauważalną

zaletą. Niemniej jednak jej wadą jest sam fakt,

że została ona zbudowana na bazie SCG i tym

samym większość problemów SCG jest nadal

aktualna w PowerCollections. O Power Col-

lections oraz System.Collections.Generic

w dalszej części artykułu.

Biorąc pod uwagę wady i problemy związa-

ne z istniejącymi kolekcjami powstały założe-

nia projektowe biblioteki C5. O założeniach

tych traktuje kolejny rozdział a tymczasem

warto jeszcze wspomnieć o tym, że biblioteka

ta dostępna jest zarówno w postaci binarnej jak

i kodu źródłowego. Biblioteka rozpowszechnia-

na jest na licencji zbliżonej do BSD a to ozna-

cza, że można modyfikować ją w dowolny spo-

sób nawet w celach komercyjnych bez potrze-

by zgłaszania tego autorom pod warunkiem za-

chowania wszystkich nagłówków dotyczących

praw autorskich.

Poziom trudności

nych, kolejek priorytetowych, stosów, zbio-

rów, wielozbiorów czy słowników. Dodatko-

wo kolekcje, które są generyczne (ang. gene-

ric ), pozwalają na bezpieczeństwo typu i pa-

rametryzacje poszczególnych implementacji

klas (unikami rzutowania z i na typ object jak

w .NET 1.1). Niniejszy artykuł dotyczyć bę-

dzie jednej z takich kolekcji napisanej całko-

wicie w C# i dostępnej dla wszystkich języ-

ków .NET od wersji 2.0 oraz Mono od 1.2.

Jest to C5, której nazwa pochodzi (najpraw-

dopodobniej, bo sami autorzy nie są pewni)

od Copenhagen Comprehensive Collection Clas-

ses for C# , mimo że, wbrew nazwie, do C# jej

użycie się nie ogranicza.

Po tym krótkim wstępie opisującym kon-

cepcję biblioteki kolekcji nasuwa się na myśl

następujące stwierdzenie – przecież dla każ-

dego języka czy framework’u mamy dostępne

gotowe biblioteki kolekcji. Po co więc tworzyć

nowe? Jest kilka takich bibliotek dla .NET, z

których najważniejszymi (poza C5) są Win-

tellect Power Collections oraz dostępne wraz

z BCL ( Base Class Libraries ) kolekcje z prze-

strzeni nazw System.Collections.Generic .

Wadami SCG, jak dalej nazywać będę System.

Collections.Generic , jest m.in. ograniczona

ilość struktur danych. Co więcej niektóre kla-

sy mają podobną funkcjonalność a nie są do-

stępne za pomocą wspólnego interfejsu, np.

listy połączone a tablice. Dodatkowo autorzy

C5 zarzucają SCG, że brak spójnych interfej-

sów powoduje wydłużenie czasu nauki kolek-

cji oraz naukę interfejsu poszczególnych klas a

nie ogólnych interfejsów implementowanych

(wersja 1.0 została opublikowana

na początku 2006 a 1.1 w lutym

2008) jest ona wykorzystywana w przemyśle

gier komputerowych, sektorze bankowym, in-

stytucjach finansowych oraz nawet w US Na-

val Research. Autorzy projektując i implemen-

tując bibliotekę wykorzystali bagaż doświad-

czeń i obserwacji wywodzących się jeszcze z ję-

zyka Smalltalk, Java oraz obecnych kolekcji w

.NET. Co w połączeniu ze wsparciem ze strony

Microsoft Research przyczyniło się do powsta-

nia sporo ponad 25000 linii kodu implemen-

tujących bardzo zaawansowaną bibliotekę, jaką

jest C5, wspartą równie obszerną ilością testów

jednostkowych.

Czym jest biblioteka kolekcji oraz jakie

jest jej przeznaczenie nie trzeba nikomu spe-

cjalnie wyjaśniać. Biblioteka taka dostarcza

struktury oraz metody ułatwiające manipu-

lowanie kolekcjami danych. Musi być na ty-

le ogólna by mogła być użyta w wielu dziedzi-

nach oraz na tyle szczegółowa, aby była wydaj-

na i pozwalała na efektywne tworzenie aplika-

cji niezależnie od tego, czy stosujemy bibliote-

kę kolekcji w grach komputerowych, bazach

danych, kompilatorach czy podczas tworze-

niu aplikacji WWW. Większość bibliotek po-

siada implementacje wektorów, list połączo-

Założenia projektowe biblioteki

Zanim poznamy szczegóły biblioteki, jak jej

używać oraz jak jest zbudowana, przyjrzyjmy

się podstawowym założeniom projektowym i

implementacyjnym C5. Założenia te są jedno-

cześnie charakterystyką tej biblioteki. A to dla-

tego ponieważ wszystkie podstawowe postula-

ty postawione w 2004 roku, kiedy to biblioteka

zaczęła się dynamicznie rozwijać, zostały zre-

alizowane. Rozdział ten jednocześnie stanowi

opis cech biblioteki i właściwości.

Jednym z podstawowych założeń projekto-

wych było, oczywiście, wsparcie dla najczę-

09/2008

M imo swojego niewielkiego wieku

C5 – nowoczesna biblioteka kolekcji dla .NET

ściej używanych kolekcji, czyli m.in. list, ko-

lejek priorytetowych, zbiorów, wielozbiorów

(ang. multiset lub bag ) czy słowników. Kolek-

cje uwzględniają wzorce wykorzystywane w

.NET (np. enumeracje z wykorzystaniem

foreach w C#). Dodatkowo kolekcje poza

iteratorami wspierają wyjątki (dziedziczenie

z klasy System.Exception ) oraz, co jest jedną

z ich cech charakterystycznych, posiadają za-

implementowane zdarzenia! Zakodowane są

również bardzo przydatne (a nieco trudne i

drobiazgowe do implementacji) właściwości

jak enumeracja kolekcji w odwrotnej kolejno-

ści czy bardzo przydatna cecha zwana upda-

teable view , o której nieco później w dalszej

części artykułu. Kolejną i bardzo ważną ce-

chą jest programowanie bazujące na interfej-

sie, a nie implementacji. Innymi słowy biblio-

teka zaprojektowana jest z wykorzystaniem

jednej z dwóch głównych zasad projektowych

przedstawionej w klasycznej już pracy Design

Patterns: Elements of Reusable Object-Oriented

Software autorstwa Bandy Czworga. Zasada

ta to w oryginale program to an interface, not

an implementation . Innymi słowy autorzy bi-

blioteki odseparowali właściwą implementa-

cję kolekcji od implementowanych przez nie

interfejsów. Interfejsy ułożone są w logiczną

strukturę dziedziczenia na dole której znaj-

dują się konkretne kolekcje. Każdy z inter-

fejsów (np. IList<T> czy ICollection<T> )

ma minimalny niezbędny zestaw właściwo-

ści i metod. Dzięki temu osiągnięto to, że

za pomocą tego samego interfejsu możemy

korzystać z wielu zupełnie inaczej zaimple-

mentowanych kolekcji. Dla przykładu za po-

mocą IList<T> możemy korzystać zarów-

no z tablicy (listy opartej o tablicę) jak i li-

sty połączonej, czyli odpowiednio z kolekcji

ArrayList<T> oraz LinkedList<T> . Ostatnią

z ważniejszych cech było udokumentowanie

złożoności obliczeniowej operacji wszystkich

kolekcji. Dokumentacja ta dostępna jest na

stronie projektu.

Pisząc o założeniach implementacyjnych

Peter Sestoft i Niels Kokholm zdecydowali

się użyć najlepszych możliwie struktur da-

nych i algorytmów. Wybór ten oznacza, że

C5 niekoniecznie korzysta z łatwych do za-

implementowania algorytmów – wręcz prze-

ciwnie. Źródła projektu są dostępne, więc za-

praszam do ciekawej lektury. Na samym po-

czątku postanowiono również, że najważniej-

sza jest wydajność kolekcji w ujęciu asympto-

tycznym oraz bogate właściwości kolekcji. In-

nymi słowy algorytmy nie są zoptymalizo-

wane pod kątem małej ilości elementów. W

porównaniu do kolekcji z System.Collecti

ons.Generic C5 może wypaść nieco wolniej

przy niewielkiej ilości elementów, lecz szyb-

ciej w przypadku olbrzymiej ich ilości. Nie-

mniej jednak nie zapomniano o wydajnej im-

plementacji i profilowano użycie struktur

w porównaniu do obiektów w algorytmach.

Oczywiście całość została napisana tylko w

kodzie zarządzanym bez ani jednego bloku

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

��

�

Rysunek 1. Diagram hierarchii interfejsów kolekcji C5

www.sdjournal.org

Biblioteka miesiąca

unsafe . Ostatnim z założeń implementa-

cyjnych jest odcięcie się od istniejących im-

plementacji kolekcji i zaimplementowanie

wszystkiego od zera . Oznacza to, że C5 nie

jest rozszerzeniem kolekcji z System.Colle

ctions.Generic . Piszę o tym, ponieważ in-

na biblioteka kolekcji czyli Wintellect .NET

Power Collections jest swego rodzaju rozsze-

rzeniem System.Collections.Generic w

konwencji istniejących już w tej przestrzeni

nazw kolekcji .NET, co do wielu zastosowań

może być ograniczeniem.

Budowa indeksu

dla pliku tekstowego – przykład

Przyjrzyjmy się bardzo prostej aplikacji za-

mieszczonej na Listingu 1. Zadaniem apli-

kacji jest dla zadanego pliku (w tym przy-

padku file.txt ) stworzyć indeks. Indeks ten

ma przedstawiać posortowaną listę wyra-

zów oraz numery linii, w jakich one wystę-

pują. Funkcja CreateIndex tworzy indeks

natomiast funkcja PrintIndex wyświetla in-

deks na konsoli. Elementem głównym jest

obiekt index typu TreeDictionary<string,

TreeSet<uint>> . Jak widać, wyrazy są

kluczami identyfikującymi zbiór nume-

rów linii (typ TreeSet<uint> ). Użycie

TreeDictionary<K,V> pozwala nam wyeli-

minować duplikaty słów w prosty sposób.

Dla każdego słowa zapisujemy obiekt kolek-

cji przechowującej numery linii ( uint ). Apli-

kacja najpierw tworzy obiekt index , następ-

nie korzystając z funkcji BCL otwieramy plik

i czytając linia po linii dzielimy go na słowa.

Następnie każde słowo sprawdzamy, czy jest

już w naszym indeksie czy jeszcze nie. Je-

Listing 1. Program budujący indeks pliku

using System ;

using SCG = System . Collections . Generic ;

using C5 ;

using System . Text . RegularExpressions ;

using System . IO ;

TreeSet < uint >());

index [ word ] . Add ( lineNumber );

}

namespace SDJ

{

class IndexProgram

{

static TreeDictionary < string , TreeSet < uint >> index =

null ;

}

static void PrintIndex ()

{

foreach ( string word in index . Keys )

{

Console . Write ( "{0}: " , word );

// Uwaga: obsluga bledow celowo pominieta

static void Main ( string [] args )

{

CreateIndex ( "ile.txt" );

PrintIndex ();

PrintIndex2 ();

}

static void CreateIndex ( string ileName )

{

index = new TreeDictionary < string ,

TreeSet < uint >>();

foreach ( uint lineNumber in index [ word ])

Console . Write ( "{0} " , lineNumber );

Console . WriteLine ();

}

static void PrintIndex2 ()

{

Act < KeyValuePair < string , TreeSet < uint >>> act =

new Act < KeyValuePair < string , TreeSet < uint >

>>( PrintKVP );

index . Apply ( act );

}

// Wyrazenie regularne nie uwzgledniajace polskich

// znakow diakrytycznych

Regex sepRegex = new Regex ( "[^a-zA-Z0-9]+" );

using ( TextReader reader = new

StreamReader ( ileName ))

{

uint lineNumber = 0 ;

static void PrintKVP ( KeyValuePair < string ,

TreeSet < uint >> kvp )

string line ;

while ( ( line = reader . ReadLine ()) != null )

{

lineNumber ++;

string [] words = sepRegex . Split ( line );

{

Console . Write ( "{0}: " , kvp . Key );

kvp . Value . Apply ( new Act < uint >( delegate ( uint

number ) { Console . Write ( "{0} " , number );

} ));

Console . WriteLine ();

}

foreach ( string word in words )

if ( word . Length > 0 )

{

if (! index . Contains ( word ))

index . Add ( word , new

}

09/2008

C5 – nowoczesna biblioteka kolekcji dla .NET

żeli nie to dodajemy nową parę <string,

TreeSet<uint>> . Jak możemy wyświetlić

tak stworzony indeks? Otóż napisałem dwie

funkcje ( PrintIndex oraz PrintIndex2 ).

Jedna korzysta z foreach a druga z metody

Apply interfejsu ICollectionValue . O inter-

fejsach kolekcji i słowników dalej w artyku-

le. Natomiast metoda void Apply(Act<T>

act) pobiera jako argument delegata przyj-

mującego argument typu T czyli kolejno

KeyValuePair<string, TreeSet<uint>>

oraz uint . Metoda ta wykonuje kod delega-

ta dla każdego elementu kolekcji. Dzięki te-

mu, że jest ona dostępna w interfejsie już

ICollectionValue (czyli wysoko w hierar-

chii dziedziczenia) to implementowana jest

przez wszystkie kolekcje C5. Stanowi ona

bardzo wygodny sposób na polimorficzne

manipulowanie elementami kolekcji. Efekt

działania programu podobny będzie do Li-

stingu 2.

��

Listing 2. Wynik działania programu z

Listingu 1 (fragment)

��

a : 2 5

an : 2

anagram : 1 2 3 4

and : 1 3 4 5

before : 4

belong : 2

check : 4

class : 2 3 4

classes : 1

create : 5

dictionary : 2

...

��

� ��

��

Rysunek 3. Interfejs ICollection

Power Collections

Biblioteka Power Collections jest projektem open source mającym na celu stworzenie biblioteki

generycznych kolekcji dla .NET. Podstawowym założeniem projektu było rozszerzenie klas z .NET

BCL ( Base Class Libraries ) w przeciwieństwie do tworzenia własnych rozwiązań od początku (jak

w przypadku C5). Biblioteka ta została stworzona przez irmę Wintellect i obecnie do pobrania

jest w portalu http://www.codeplex.com . Zawiera kolekcje i słowniki:

• Set ;

• Bag ;

• MultiDictionary ;

• OrderedDictionary ;

• OrderedMultiDictionary ;

• OrderedSet ;

• OrderedBag ;

• Dequeue ;

•

��

PriorityQueue .

Rysunek 2. Interfejs ICollectionValue. Jeden z

podstawowych interfejsów C5

Więcej o Power Collections na stronie http://www.codeplex.com/PowerCollections , gdzie dostępna

również jest dokumentacja.

www.sdjournal.org

Biblioteka miesiąca

Przegląd interfejsów kolekcji

Interfejs jest to definicja operacji, które są im-

plementowane przez daną klasę. Z racji, że jed-

nym z podstawowych założeń projektowych

C5 jest programowanie na bazie interfejsu, in-

terfejsy i ich zrozumienie jest bardzo ważnym

elementem poznawania biblioteki. Rysunek 1

przedstawia hierarchię dziedziczenia. Z szesna-

stu prezentowanych interfejsów czternaście po-

chodzi z C5 natomiast dwa ( IEnumerable<T>

oraz IShowable ) są interfejsami z .NET Frame-

work. Na Rysunku widać zależności pomiędzy

interfejsami. Poniżej opisałem wybrane inter-

fejsy prezentując ich cechy charakterystyczne.

IEnumarable<T> na samej górze Rysunku

1 jest interfejsem kolekcji o nieznanej wielko-

ści i niewielu specyficznych właściwościach.

Jest to interfejs pochodzący z SCG. Ważnym

członkiem interfejsu jest GetEnumerator() ,

która to metoda zwraca obiekt klasy SCG. IE-

numerator<T> pozwalający na iterowanie po

elementach kolekcji za pomocą słowa kluczo-

wego foreach (w C#). Warto zauważyć, że

każda z kolekcji implementuje ten interfejs

i dlatego też w każdej z kolekcji możliwe jest

użycie foreach .

ICollectionValue<T> z biblioteki C5 jest

jednym z ważniejszych interfejsów dziedzi-

czących bezpośrednio po interfejsach z .NET

Framework. ICollectionValue<T> jest ko-

lekcją o znanej wielkości lecz niepozwala-

jącą na zmianę elementów w kolekcji. Roz-

szerza IEnumerable<T> o metody CopyTo()

oraz ToArray() , które kopiują elementy ko-

lekcji do istniejącej lub nowej tablicy. Kolejny-

mi nowymi członkami interfejsu są właściwo-

ści Count oraz IsEmpty . Metody i właściwo-

ści ICollectionValue<T> są widoczne na Ry-

sunku 2.

Interfejs ICollection<T> jest implemento-

wany przez wiele kolekcji C5. ICollection<T>

implementuje interfejs SCG.ICollection<T>

oraz C5.IExtensible<T> . Kolekcja taka jest

rozszerzalna (interfejs C5.IExtensible<T> ),

czyli pozwala na dodawanie, usuwanie ele-

mentów i grup elementów, pozwala na

sprawdzanie przynależności elementu do

kolekcji oraz inne metody charakterystycz-

ne dla większości kolekcji. Listing 3 pre-

zentuje proste użycie kolekcji implemen-

tującej C5.ICollection<T> w postaci kla-

sy C5.ArrayList<T> (oraz zakomentowanej

C5.LinkedList<T> ).

Na tym krótkim Listingu widzimy uży-

cie zdarzeń, właściwości ActiveEvents z

C5.ICollectionValue<T> oraz Apply z te-

go samego interfejsu. Dzięki metodzie Apply

oraz delegatowi Act<T> możemy w prosty spo-

sób wyświetlić zawartość kolekcji na konsolę.

Diagram interfejsu jest prezentowany na Ry-

sunku 3.

Kolejnym godnym uwagi interfejsem z bi-

blioteki C5 jest IStack<T> . Jest to ukierunko-

Listing 3. ICollection

using System ;

using SCG = System . Collections . Generic ;

using C5 ;

namespace CollectionApplication

{

class ICollectionProgram

{

static ICollection < string > collection = null ;

static void Main ( string [] args )

{

collection = new ArrayList < string >();

//collection = new LinkedList<string>();

collection . ItemsAdded += new ItemsAddedHandler < string >( list_ItemsAdded );

collection . ItemsRemoved += new ItemsRemovedHandler < string >( list_

ItemsRemoved );

EventTypeEnum events = collection . ActiveEvents ;

// if ( events ...

��

� ��

��

collection . Add ( "jeden" );

collection . Add ( "dwa" );

collection . AddAll ( new string [] { "trzy" , "cztery" , "piec" } );

��

collection . Remove ( "trzy" );

��

collection . Apply ( new Act < string >( Console . WriteLine ));

}

static void list_ItemsRemoved ( object sender , ItemCountEventArgs < string >

eventArgs )

��

� ��

��

{

// obsluga zdarzenia

}

��

static void list_ItemsAdded ( object sender , ItemCountEventArgs < string >

eventArgs )

��

{

// obsluga zdarzenia

}

��

Rysunek 4. Interfejs IStack

09/2008

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: