Wirtualizacja danych w C#

Oszukać rzeczywistość

Każdy, kto choć raz zetknął się z dużym systemem, zetknął się również z dużą ilością danych. W takich okolicznościach dość naturalnie pojawia się pytanie o to, czy można te dane jakoś podzielić. Jest mnóstwo technik i różnie się one sprawdzają. Tym razem zajmę się jedną z nich - to technika zwana wirtualizacją danych. Na czym ten mechanizm polega?

Mechanizm jest próbą oszukania otoczenia i ukrycia przed tym otoczeniem rzeczywistej implementacji. Zaraz, zaraz - a czy nie o to chodzi w programowaniu obiektowym i enkapsulacji? Usprawiedliwiłem już próbę oszustwa więc czas na więcej szczegółów.

Wiemy, że wiele kolekcji implementuje jeden wspólny interejs - to interfejs IEnumerable. Oznacza to, że elementy mogą być wyliczane, ale tylko w określonej implementacją kolejności. To dość prosty interfejs ale też mało przyjemny w obsłudze. Nieco większym interfejsem jest ICollection, którego nazwa już coś sugeruje. Tak prawdę mówiąc ma on tylko jedną właściwość, która jest przydatna - Count, resztę właściwości można na tym etapie spokojnie zignorować. Pójdźmy jeszcze dalej - do interfejsu IList, bo ten interfejs już coś ma. Przede wszystkim tablicowy, indeksowany dostęp do poszczególnych elementów. To nam będzie potrzebne. To tutaj będą się działy rzeczy magiczne. Użytkownik niech sobie myśli, że ma wielką listę z dostępem swobodnym - w rzeczywistości elementy będą doczytywane dopiero wtedy, gdy użytkownik jawnie ich zażąda poprzez indeksowanie. Ten właśnie mechanizm trzeba zaimplementować.

Plan wirtualizacji danych

Aby nasza klasa zachowywała się podobnie do zwykłej listy, najpowszechniej wykorzystywanej kolekcji, należy zaimplementować interfejs IList oraz, pośrednio, interfejsy IEnumerable oraz ICollection. Stwórzmy więc klasę VirtualList<T>, która będzie implementowała metody i właściwości IList:

public abstract class VirtualList<T> : IList
{
// Implementacja
}

Napisałem wcześniej, że element będzie doczytywany dopiero w momencie odwołania do niego. Jest to lekka przesada i pewien skrót myślowy. Nie ma sensu pobierać, na przykład z bazy, po jednym rekordzie (przy okazji odsyłam też do wpisu Stronicowanie w SQL Server). Znacznie lepszym rozwiązaniem jest pobieranie danych w paczkach, po kilkadziesiąt rekordówWszystko oczywiście zależy od rodzaju danych, szybkości ich pobierania, prawdowpodobieństwa, że użytkownik będzie chciał zobaczyć dane na kolejnych stronach.. Dane te będą przechowywane w rekordzie strony: Page:

// Obiekt reprezentujący stronę na liście wirtualnej
// Jest zwykłą listą - nie będzie przeszkadzał w zrozumieniu sedna sprawy.
public class Page<T> : List<T>
{
}

Klasa bardzo prosta, bo chciałem zwrócić uwagę na zupełnie inne elementy.

Podstawowe zadania klasy z wirtualnymi stronami danych

Zanim przedstawię szczegóły implementacyjne IList, IEnumerable oraz ICollection przedstawię cały plan działania w kilku punktach:

Zależy nam na dostępie swobodnym, więc musimy znać rozmiar całej struktury. Potrzebna nam będzie metoda do pobierania rozmiaru całej kolekcji.
Jeżeli ktoś odwoła się do naszej kolekcji, a my nie mamy dla niego danych, należy te dane pobrać. Potrzebna będzie zatem metoda do pobierania wybranej strony danych.
Lista będzie wykorzystywana przez interfejs użytkownika. Aby stworzyć nagłówek tabeli trzeba pobrać nagłówki kolumn. Nagłówki będą pobierane tylko raz - potem już tylko dane.

Pozostałe właściwości będą się pojawiały tylko dla wygody posługiwania się listą lub w celu implementacji zaplanowanych funkcjonalności. Przyjrzyjmy się w takim razie wstępnemu projektowi klasy:

public abstract class VirtualList<T> : IList
{
  // Rozmiar strony.
  public int PageSize { get; private set; }

  // Pobiera tablicę nazw kolumn. Nazwy pobierane są tylko raz
  // poprzez wirtualną metodę GetCaptions().
  private string[] columns = null;
  public string[] Columns
  {
    get
    {
      if (columns == null)
      {
        columns = GetCaptions();
      }
      return columns;
    }
  }

  // Liczba rekordów na liście, -1 oznacza stan niezainicjalizowany
  // Liczba pobierana jest tylko raz poprzez wywołanie ICollection.Count
  private int rowCount = -1;

  // Przechowuje listę wczytanych juz stron.
  private Page<T>[] Pages { get; set; }

  // Konstruktory dla wygody.
  public VirtualList()
  {
    PageSize = 20;
  }

  public VirtualList(int pageSize)
  {
    this.PageSize = pageSize;
  }

  // Pobiera nazwy nagłówków kolumn. Domyślnie są to
  // wszystkie publiczbe właściwości.
  public virtual string[] GetCaptions()
  {
    var properties = typeof(T).GetProperties();
    return properties.Select(a => a.Name).ToArray();
  }

  // Pobiera liczbę rekordów w liście.
  public abstract int GetRowCount();

  // Pobiera stronę. Strona pobierana jest, gdy nastąpiło żądanie
  // do jednego z rekordów, który w tej stronie powinien się znajdować.
  public abstract Page<T> GetPage(int pageNumber);

  // [Implementacja IList]

  // [Implementacja ICollection]

  // [Implementacja IEnumerable]
}

Warto zwrócić uwagę na kilka rzeczy:

Właściwość Columns pobiera nagłówki kolumn tylko raz i zapamiętuje je w zmiennej column. Kolumny pobierane są poprzez wywołanie metody GetCaptions.
Metoda wirtualna GetCaptions ma wstępną implementację. Domyślnie nagłówkami kolumn stają się wszystkie publiczne właściwości klasy będącej elementem listy. Metodę można nadpisać.
Lista wirtualna jest tworem bardzo ogólnym. Zupełnie nie znamy sposobu pobierania danych i liczby rekordów. Metody GetPage i GetRowCount są wobec tego abstrakcyjne.

Reszta została wyjaśniona w komentarzach w kodzie.

Implementacja IEnumerable

Czas na implkementację podstawowych interfejsów. Na rozgrzewkę zajmę się interfejsem IEnumerable, bo ma on tylko jedną metodę:

public IEnumerator GetEnumerator()
{
for (int i = 0; i < this.Count; i++)
yield return this[i];
}

Skoro mamy dostęp indeksowany to najłatwiej jest po prostu wykonać pętlę for z instrukcją yield i przejść do implementacji kolejnego interfejsu.

Interfejs ICollection

To juz nieco większy interfejs, ale równie prosty:

public void CopyTo(Array array, int index)
{
    throw new NotImplementedException();
}

// Pobierz liczbę rekordów
public int Count
{
    get
    {
        // Jeżeli wywoływane pierwszy raz, zapamiętaj rozmiar
        // i stwórz kolekcję przechowującą pobrane strony
        if (rowCount == -1)
        {
            rowCount = GetRowCount();
            Pages = new Page<T>[(rowCount + PageSize - 1) / PageSize];
        }
        return rowCount;
    }
}

// Lista nie jest synchronizowana
public bool IsSynchronized
{
    get { return false; }
}

// Obiektem synchronizacji jest sama lista
public object SyncRoot
{
    get { return this; }
}

W całej implementacji interesuje nas przede wszystkim właściwość Count. Służy ona do pobierania rozmiaru listy i jest potrzebna na interfejsie użytkownika do odpowiedniego ustawienia paska przewijania lub uzupełnienia interfejsu o przyciski do przechodzenia pomiędzy stronami. W pokazanym przykładzie założyłem, że rozmiar listy nim może się zmieniać. Brak takiego założenia może mocno skomplikować całe zadanie. Ważne jest, aby gdzieś przydzielić pamięć dla obiektu przechowującego poszczególne strony. Można to oczywiście zrobić już podczas pobierania danych, ale tutaj jest chyba wygodniej.

Pozostałe właściwości zostały nadpisane w sposób mocno minimalistyczny.

Implementacja interfejsu IList

trzeci i ostatni interfejs to IList. Tutaj kluczowym fragmentem jest implementacja indeksera. W zasadzie to nawet dwóch, ale o tym za chwilę. Przyjrzyjmy się przykładowej implementacji:

// Dodaj element
public int Add(object value)
{
    throw new NotImplementedException();
}

// Wyczyść listę
public void Clear()
{
    throw new NotImplementedException();
}

// Czy zawiera element
public bool Contains(object value)
{
    throw new NotImplementedException();
}

// Znajdź indeks wskazanego elementu.
// Metoda często wywoływana przez interfejs użytkownika,
// aby zaznaczyć wybrany element.
public int IndexOf(object value)
{
    return 0;
}

// Wstaw nowy element
public void Insert(int index, object value)
{
    throw new NotImplementedException();
}

// Czy lista ma stały rozmiar.
public bool IsFixedSize
{
    get { return true; }
}

// Czy lista jest tylko do odczytu.
public bool IsReadOnly
{
    get { return true; }
}

// Usuń element
public void Remove(object value)
{
    throw new NotImplementedException();
}

// Usuń element pod wskazanym indeksem.
public void RemoveAt(int index)
{
    throw new NotImplementedException();
}

// Pobierz element znajdujęcy się pod wskazanym indeksem
// Implementacja interfejsu IList
object IList.this[int index]
{
    get
    {
        int pageNumber = index / PageSize;
        if (Pages[pageNumber] != null)
            return Pages[pageNumber][index % PageSize];
        else
        {
            var newPage = GetPage(pageNumber);
            Pages[pageNumber] = newPage;
            return newPage[index % PageSize];
        }
    }
    set
    {
        throw new NotImplementedException();
    }
}

// Silnie typowany indekser do pobierania elementów listy.
// Metoda nie ma nic wspólnego z implementacją interfejsu,
// ale pozwala uzyskać rekord właściwego typu.
// Implementacja przykrywa domyślny, nietypowany indekser.
public T this[int index]
{
    get
    {
        // Odwołaj się do nietypowanego indeksera.
        return (T)(this as IList)[index];
    }
}

Przyjrzyjmy się najpierw indekserowi IList.this. Jak on działa? Na podstawie przekazanego indeksu wylicza stronę, w której powinien się ten rekord znajdować. Jeżeli strona jest, pobierany jest z niej poszukiwany rekord. Jeżeli strony nie ma, wywoływana jest abstrakcyjna metoda pobierająca odpowiednią stronę. Samo pobieranie strony definiowane jest poza obszarem ogólnej klasy VirtualList<T>. Pobrana strona jest zapamiętywana w liście pobranych stron. Sam rekord także może być już z tej strony pobrany i zwrócony wywołującemu. To implementacja IList.

Klasa VirtualList<T> przystosowana jest do obsługi rekordów każdego typu. Trochę głupio byłoby zwracać obiekt, skoro mamy jawnie podany typ. To dlatego dopisałem drugi indekser, publiczny, który będzie wywoływany zamiast domyślnego, zwracającego typ object. Upiekłem dwie pieczenie na jednym ogniu: implementacja ma swoją metodę, a publicznie widoczny jest indekser udoskonalony.

Pozostałe implementacje nie wnoszą niczego nowego. Nie oznacza to jednak, że nie warto z nich skorzystać. Implementacja kolejnych metod jeszcze bardziej wzbogaci naszą wirtualną listę.

Lista jest juz gotowa do użycia.

Przykładowa implementacja

Aby pokazać listę w działaniu należy nadpisać dwie abstrakcyjne metody klasy VirtualList<T>, ewentualnie jeszcze jedną, wirtualną metodę do pobierania nazw kolumn. Pokażę, jak nadpisać wszystkie trzy. Klasa dalej będzie bardzo ogólna, bo pod postacią rekordów będą się pojawiać tablice obiektów. Przyjrzyjmy się przykładowej implementacji pokazanej poniżej:

public class ArrayVirtualList : VirtualList<object[]>
{
    public override string[] GetCaptions()
    {
        return new string[] { "Kolumna 1", "Kolumna 2", "Kolumna 3", "Kolumna 4" };
    }

    public override int GetRowCount()
    {
        return 1000;
    }

    public override Page<object[]> GetPage(int pageNumber)
    {
        Debug.WriteLine("Pobieranie strony {0}", pageNumber);
        var newPage = new Page<object[]>();
        var newPageSize = Math.Min(this.Count - pageNumber * PageSize, PageSize);
        for (int row = 0; row < newPageSize; row++)
        {
            var newRow = new object[Columns.Length];
            for (int i = 0; i < Columns.Length; i++)
            {
                newRow[i] = Guid.NewGuid();
            }
            newPage.Add(newRow);
        }
        return newPage;
    }
}

Implementacja jest bardzo prosta. Jako nagłówki tabeli zwracam stałą tablicę z czterema wartościami, zwracając liczbę rekordów zwracam stałą wartość 1000. Trochę więcej dzieje się w metodzie pobierającej stronę z danymi. Po pierwsze, wypisuję stosowny komunikat - wszystko po to, aby pokazać sposób działania wirtualnej listy. Po drugie, wyliczam rozmiar nowej strony. Rozmiar strony jest znany, ale ostatnia ze stron może nie być w całości zapełniona. Po trzecie, trzeba stworzyć nową stronę. Uznałem, że w celach demonstracyjnych zapełnię ją generowanymi na żywo wartościami typu Guid.

Na koniec wypadałoby jeszcze pokazać, jak zachowuje się taka lista z konkretnym klientem.

WPF, wirtualizacja interfejsu i wirtualizacja danych

Do celów demonstracyjnych wybrałem WPF, bo jest on domyślnie przystosowany do wirtualizacji. Przystosowany od strony interfejsu użytkownika. Do tego wystarczy podłączyć wirtualizację danych, którą właśnie zaimplementowaliśmy. Przyjrzyjmy się przykładowemu widokowi:

Przejdźmy teraz do kodu tego okna:

public partial class MainWindow : Window
{
    ArrayVirtualList virtualList = new ArrayVirtualList();

    public MainWindow()
    {
        InitializeComponent();
        PopulateColumns();
        lvItems.DataContext = virtualList;
    }

    private void PopulateColumns()
    {
        for (int i = 0; i < virtualList.Columns.Length; i++)
        {
            lvItems.Columns.Add(new DataGridTextColumn()
            {
                Header = virtualList.Columns[i],
                Binding = new Binding(string.Format(".[{0}]", i)) { Mode = BindingMode.OneTime }
            });
        }
    }
}

Kod jest bajecznie prosty. Tworzona jest nowa, nasza wirtualna lista, a na jej podstawie tworzone są nagłówki tabeli. Wszystko to odbywa się w metodzie PopulateColumns. Tam też odbywa się wiązanie poszczególnych kolumn tabeli z odpowiednimi indeksami rekordów w wirtualnej liście. Na koniec cała wirtualna lista staje się źródłem wiązania. Po uruchomieniu aplikacji otrzymamy okno podobne do pokazanego poniżej:

Wirtualizacja interfejsu WPF połączona z wirtualizacją danych — Rys. 1 Przykład pełnej wirtualizacji kontrolki WPF.

Zaraz po uruchomieniu, gdy rzucimy okiem na okno Output w Visual Studio, będziemy mogli odnaleźć następujący komunikat:

Pobieranie strony 0

Gdy teraz spróbujemy się pobawić suwakiem pionowym, w oknie Output będą się pojawiały kolejne komunikaty informujące nas o pobieraniu na żądanie kolejnych stron.

Podsumowanie

Wirtualizacja danych nie jest zadaniem trywialnym, ale raz i dobrze zrobiona może być wielokrotnie wykorzystywana. Doświadczenie jakie daje użytkownikom końcowym jest nie do przecenienia. Praktyka pokazuje, że użytkownik i tak przegląda tylko pierwszą stronę (któż z nas zagląda na kolejne podstrony w wyszukiwarce?). W takim przypadku oszczędzamy również na transferze, liczbie rekordów, które muszą być z bazy odczytane. Jeżeli kiedyś pojawi się problem dużej ilości danych lub długiego czasu pobierania się, warto pomysleć o pokazanym mechanizmie wirtualizacji. Gdyby wyjaśnienie było niejasne lub pojawiły się jakieś dodatkowe pytania, zachęcam do skorzystania z opcji komentowania.

Pobierz kod aplikacji do wirtualizacji zaprezentowanej w artykule - Virtualization.zip.

Kategoria:C#

Paweł Dyl, 2013-12-20

Komentarze:

Cris (2014-08-09 11:34:11)

Dobry wpis ale przydałby się cały kod do pobrania.

Cris (2014-08-09 13:32:54)

Czy wczytane kolejno strony są zwalniane z pamięci jeżeli już ich nie widać? jak to jest?
Jakie są jeszcze inne techniki żeby osiągnąć podobny efekt?

Pozdrawiam!

PD (2014-12-11 17:28:03)

Zgodnie z sugestią dodałem pełny kod aplikacji, której dotyczy artykuł. Dziękuję za komentarz.