Microsoft Immutable Collections

Kolekcje z System.Collections.Generic są wszystkim dobrze znane. Czasami jednak zachodzi potrzeba skorzystania z typów immutable.  Ogólnie o tych obiektach pisałem tutaj.  Szczególnie w środowisku wielowątkowym są one przydatne. Jak można przeczytać we wspomnianym poście, obiekty takie nigdy nie mogą zostać zmienione a modyfikowanie stanu polega na tworzeniu nowej instancji.

Ktoś mógłby zasugerować, że mamy w końcu ReadOnlyCollection. Niestety, interfejs uniemożliwia modyfikacje tej kolekcji wyłącznie jego użytkownikowi. Załóżmy, że mamy metodę:

private void DoSomething (IReadOnlyCollection<int> list) { }

Co prawda w DoSomething nie możemy zmodyfikować danych i interfejs jasno o tym mówi, ale nic nie stoi na przeszkodzie, aby ktoś z zewnątrz dokonywał zmian na kolekcji. Jeśli byłoby to kolekcja immutable, mielibyśmy pewność, że nikt jej w międzyczasie (np. z osobnego wątku) nie zmodyfikuje.

Aby zacząć zabawę, musimy najpierw zainstalować zewnętrzny pakiet:

image

 

Do dyspozycji będziemy mieli wiele typów:

– ImmutableStack<T>

– ImmutableQueue<T>

– ImmutableList<T>

– ImmutableHashSet<T>

– ImmutableSortedSet<T>

– ImmutableDictionary<K, V>

– ImmutableSortedDictionary<K, V>

Wszystkie one znajdują się w System.Collections.Immutable;. Sprawdźmy, jak działa najpopularniejsza z nich, ImmutableList.

Jeśli spróbujemy obiekt zainicjalizować w standardowy sposób, zakończy to się błędem:

ImmutableList<int> immutableList = new ImmutableList<int ();

Po prostu, konstruktor jest prywatny. Dlaczego? Obiekty niezmienne inicjalizuje się w następujący sposób:

ImmutableList<int> immutableList = ImmutableList<int>.Empty;

Może wydawać to się dziwne, ale jaki jest sens inicjalizowania pustego obiektu, jeśli żadna operacja na nim nie zostanie wykonana? Wszystkie operacje typu Add, Remove tworzą zawsze nową kopię. Zatem ten pierwszy, bazowy może być wspólny bo nie ma to znaczenia, a zaoszczędzi pamięć.

Napiszmy kawałek kodu, aby przekonać się, że zawsze nowa instancja jest zwracana:

ImmutableList<int> immutableList = ImmutableList<int>.Empty; ImmutableList<int> list1= immutableList.Add(1); ImmutableList<int> list2 = list1.Add(12); Debug.Assert(immutableList.Count==0); Debug.Assert(list1.Count == 1); Debug.Assert(list2.Count == 2);

Z tego wynika, że jeśli chcemy dodać serie wartości, wtedy osobne wywołania Add nie są najlepszym wyborem, ponieważ spowodują relokacje zasobów. Innymi słowy, poniższy kod jest bardzo brzydki:

ImmutableList<int> immutableList = ImmutableList<int>.Empty; immutableList=immutableList.Add(1); immutableList=immutableList.Add(2); immutableList=immutableList.Add(3);

Z tego względu, dużo lepiej jest:

ImmutableList<int> immutableList = ImmutableList<int>.Empty; immutableList.AddRange(new []{1,2,3,4});

Alternatywą również jest użycie Fluent API:

ImmutableList<int> immutableList = ImmutableList<int>.Empty; immutableList.Add(3).Add(1).Add(5);

O tym jednak, więcej w następnym wpisie. Planuje również zrobić test wydajności między różnymi kolekcjami, aby pokazać kiedy nie należy stosować przedstawionych kolekcji.

4 thoughts on “Microsoft Immutable Collections”

  1. Czym ten ostatni przykład różni się od pierwszego – złego? Przecież tak na logikę to w
    immutableList.Add(3).Add(1).Add(5)
    wywołujemy to samo Add co w pierwszym przykładzie, więc mamy ten sam problem z realokacją pamięci, bo za każdym razem tworzymy nową, tymczasową listę.

  2. Add nie realokuje wszystkich węzłów, a jedynie dodaje jeden so już istniejącej listy. Bardzo tania operacja wykorzystywana w językach takich jak Haskell czy F#.

  3. Czy to oznacza, że w wersji z użyciem Fluent API mamy do czynienia z wykonywaniem operacji ‘od prawej do lewej’ bądź z sytuacją, gdy Add(x).Add(y) ma pierwszeństwo nad ImmutableList.Add(x) przez co zapis Add().Add().Add() generuje nam tablicę, a API samo generuje AddRange()?

    Jeśli nie, to nie jestem w stanie sobie wyobrazić w jaki sposób

    immutableList.Add(3).Add(1).Add(5)

    różni się od

    immutableList=immutableList.Add(3);
    immutableList=immutableList.Add(1);
    immutableList=immutableList.Add(5);

    Pozdr,

  4. Wywolania chyba niczym nie roznia sie, aczkolwiek sama operacja dodawania jest zoptymalizowana. Postaram sie o tym wiecej napisac wkrotce.

Leave a Reply

Your email address will not be published.