Tablice przyspieszające wyszukiwanie elementów

Zastosowania tablic w C - wszystkie wpisy

• Tablice wskaźników na funkcje
• Maszyny stanów na tablicach
• Tablice przyspieszające wyszukiwanie elementów
• Jak korzystać z Lookup Table?

Kolejnym – po Lookup Table – tematem związanym z tablicami, którym się zajmę jest przyspieszenie wyszukiwania elementów. Zwykle nasze możliwości w tym zakresie ograniczają się do podawania indeksu tablicy albo wyszukiwania w pętli. Możemy jednak przyspieszyć te operacje wykorzystując dodatkowe tablice z mapowaniem indeksów, albo skorzystać z hash table.

Przykładowy problem

Ostatnio spotkałem się z problemem obsługi bloków danych z pamięci EEPROM. To jest idealny przypadek do zastosowania techniki, którą chcę dzisiaj omówić. Niestety szczegółów nie mogę zdradzać, dlatego będę operować na bardzo ogólnym przykładzie. Mam nadzieję, że mimo wszystko będzie zrozumiały.

Wyobraźmy sobie taką sytuację. Mamy pewną strukturę danych wykorzystywaną przez dwa moduły w naszym programie. Poszczególne instancje tej struktury są przechowywane w tablicy. Każdy z tych dwóch modułów wewnętrznie wykorzystuje numery ID powiązane z poszczególnymi elementami tablicy. Niestety każdy moduł musi korzystać z innych ID. Naszym zadaniem jest stworzenie procedur dostępu do obiektów w tablicy za pomocą każdego z tych ID.

Mamy więc naszą tablicę obiektów:

struct data
{
   type1_t field1;
   type2_t field2;
   ...
};

struct data data_table[] = 
{
    {... /* initial data 1 */},
    {... /* initial data 2 */},
    ...
};

Najprostsze rozwiązanie

Najprostszym rozwiązaniem byłoby ułożenie danych w tablicy zgodnie z ID jednego modułu i rozszerzenie elementów tablicy o ID drugiego modułu. Wtedy wyszukiwanie obiektu o ID modułu 1 to zwykłe zwrócenie elementu o danym indeksie, a dla modułu 2 musimy przeszukać wszystkie elementy w poszukiwaniu tego o pasującym ID.

struct extended_data
{
    module2_id_t module2_id;
    struct data *data_item;
}

struct extended_data ext_data_table[] = 
{
    {MODULE2_ID_0, &data_table[0]},
    {MODULE2_ID_1, &data_table[1]},
    ...
};

const size_t EXT_DATA_TABLE_SIZE = sizeof(ext_data_table)/sizeof(ext_data_table[0]);

struct data * get_data_from_module1_id(module1_id_t id)
{
    return ext_data_table[id].data_item;
}

struct data * get_data_from_module2_id(module2_id_t id)
{
    struct data * item = NULL;
    uint32_t i;

    for (i = 0; i < EXT_DATA_TABLE_SIZE; i++)
    {
        if (id == ext_data_table[i].module2_id)
        {
            item = ext_data_table[i].data_item;
            break;
        }
    }

    return item;
}

Jednak to rozwiązanie ma kilka wad. Przede wszystkim jeżeli tablica jest duża, wyszukiwanie dla modułu 2 będzie trwało długo. Poza tym takie sztywne powiązanie z ID modułu 1 rodzi pewne problemy z utrzymaniem. Niektóre ID mogą nie być przypisane do żadnego obiektu. Zakres możliwych ID może być dużo większy niż ilość wykorzystywanych obiektów, co może przełożyć się na marnowanie dużej ilości pamięci. Jeszcze większym problemem mogą być duplikacje. Ten sam obiekt może być wykorzystany przez kilka ID. Szczególnym problemem będzie tu ID drugiego modułu. Dodatkowo w przypadku późniejszej zmiany wartości dla danego ID edycja tablicy może być kłopotliwa. W końcu musimy pamiętać też o edycji ID drugiego modułu i o duplikacjach.

Lepsze rozwiązanie

Wszystkie te problemy możemy rozwiązać stosując dodatkowe tablice:

typedef data_table_idx_t size_t;

const data_table_idx_t NO_DATA = 0xFFFFFFFF;

data_table_idx_t module1_id_to_data[] = 
{
    DATA_IDX_FOR_M1_ID0,
    DATA_IDX_FOR_M1_ID1,
    NO_DATA,
    ...
};

data_table_idx_t module2_id_to_data[] = 
{
    DATA_IDX_FOR_M2_ID0,
    DATA_IDX_FOR_M2_ID1,
    NO_DATA,
    ...
};

Nowe tablice są indeksowane za pomocą ID modułu i zwracają ID w tablicy obiektów. Dzięki temu brak obiektu czy duplikacja nie stanowią już żadnego problemu, a czas wyszukiwania obiektu jest minimalny. Co więcej tablice z mapowaniem indeksów do danych na ID konkretnych modułów możemy zamknąć w tych modułach, a data table zamknąć w odrębnym module.

Tablice asocjacyjne, hash table

Docelowe rozwiązanie w powyższym przykładzie polegało na stworzeniu funkcji otrzymującej na wejście jakiś identyfikator (klucz – key, w naszym przypadku był to indeks modułu) i zwracającej wartość (value) powiązaną z tym kluczem (w naszym przypadku struktura). Przez fakt, że musieliśmy obsługiwać dwa rodzaje kluczy, musieliśmy stworzyć Lookup Table mapujące ID modułu na indeks w tablicy obiektów. Jest to przykład implementacji prostej tablicy asocjacyjnej – czyli właśnie typu danych umożliwiającego dostęp do wartości przez podanie unikalnego klucza.

Wszystko fajnie, ale bardzo często nasz klucz to nie jest prosta liczba mogąca bezpośrednio posłużyć jako indeks w tablicy. Co wtedy? Musimy stworzyć funkcję generującą indeks z klucza, tak zwaną funkcję hashującą.
Tablica, której indeks jest obliczany za pomocą funkcji hashującej to hash table. Jej główną zaletą jest szybki czas dostępu do danych. Jednak największą wydajność ma jeżeli duża część indeksów w tablicy jest pustych.

Funkcje hashujące i kolizje

Różne funkcje mogą działać na różnych kluczach – na liczbach, stringach, czy dowolnych ciągach bajtów. Zwykle składają się z prostych operacji bitowych takich jak xory, czy przesunięcia. Przez to trwają dużo krócej niż przeszukiwanie całej tablicy w pętli. Poza tym czas wykonania jest deterministyczny, a nie zależny od pozycji poszukiwanego pola w tablicy. Wybór funkcji hashującej to ważny aspekt wpływający na wydajność aplikacji. Musimy przede wszystkim zapewnić, żeby funkcja nie była zbyt skomplikowana i żeby rozkład zwracanych indeksów dla spodziewanych danych wyjściowych był równomierny na przestrzeni całego zakresu dozwolonych wartości. Dzięki temu minimalizujemy prawdopodobieństwo kolizji.

Kolizja następuje, gdy hash wyliczony dla danego klucza jest taki sam jak dla innego klucza, który został użyty wcześniej. W związku z tym, że liczba wszystkich unikalnych kluczy jest jest zwykle dużo większa niż ilość dostępnych indeksów – kolizje są nieuniknione. Musimy więc wybrać odpowiednią politykę obsługi kolizji. Czasem możemy ją po prostu zignorować i nadpisać indeks, zwykle jednak musimy albo zachować wszystkie wartości pod danym indeksem, albo obliczyć nowy indeks. To właśnie kolizje powodują, że im bardziej wypełniona tablica, tym spada wydajność. Zarówno sposób obsługi kolizji, jak i wybór funkcji hashującej to szerokie tematy i przed implementacją polecam zapoznać się z literaturą. Dobry wstęp do hash table w C można znaleźć w tym tutorialu na GitHubie.

Zastosowania

Tablice o dostępie indeksowym, w tym hash table są szeroko wykorzystywane w komunikacji. Tablice routingu, tablice MAC, parametry połączenia TCP to wszystko idealni kandydaci do implementacji za pomocą hash table. Ale tak naprawdę każda tablica po której iterujemy, aby wyszukać jakiś element jest kandydatem do wykorzystania tej techniki. Musimy tylko sprawdzić, czy potrzebujemy zwiększyć performance i czy możemy sobie pozwolić na dodatkowe zużycie pamięci.

Podsumowanie

Podobnie jak w przypadku Lookup Table, tablice indeksowane zwiększają szybkość wykonywania programu kosztem zużycia pamięci. Czasem wszystkie wykorzystywane w tym celu tablice, albo przynajmniej te z mapowaniem indeksów jak w prezentowanym przykładzie, możemy zapisać w pamięci stałej. Najlepiej takie tablice generować automatycznie za pomocą jakiś skryptów. Jednak w rozwiązaniach takich jak komunikacja zwykle jednak tablica musi być w RAMie. Podczas komunikacji nie znamy zwykle innych węzłów, dane mogą się zmieniać, a nawet jeśli nie to kombinacji możliwych kluczy jest za dużo, żeby dla każdego przechowywać wartość.

Zastosowania tablic w C - Nawigacja