9 lipca 2016

Zadanie rekrutacyjne #4

Znajdź liczbę, której brakuje.

Mamy tablicę liczb typu uint32_t, twoim zadaniem jest napisanie funkcji, która poda najmniejszą liczbę typu uint32_t, taką że nie występuje ona w zbiorze wejściowym. Wszystkich liczb w tablicy jest nie więcej niż 2^32 – 1. Poszczególne wartości mogą się powtarzać.

Przeprowadź dyskusję złożoności obliczeniowej i pamięciowej rozwiązania.

Szablon funkcji

uint32_t ZnajdzBrakujacaLiczba( uint32_t* tablica, uint32_t N )
{
    ......................
}

Przykładowe wyniki

Dane Wynik
0,1,2,2,2,2,3,2,1,0 4
1,2,6,7 0
0,1,1,2,7 3

Rozwiązanie przez sortowanie

Algorytm:

  • Dokonujemy sortowania całej tablicy.
  • Iterujemy po elementach, zliczając jednocześnie powtórzenia, aż do momentu znalezienia brakującego elementu. Rezultat: Jeśli nie znaleźliśmy brakującego elementu, to kres górny zbioru elementów plus jeden jest naszym brakującym elementem.

Kod

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

uint32_t ZnajdzBrakujacaLiczba( uint32_t* tablica, uint32_t N )
{
    if ( N == 0 ) return 0;

    sort( tablica, tablica+N );
    uint32_t ilosc_duplikatow = 0;

    for(uint32_t i = 0; i < N; ++i ) {
        if (i > 0 && tablica[i] == tablica[i - 1]) {
            ++ilosc_duplikatow;
            continue;
        }

        if (tablica[i] + ilosc_duplikatow != i)
            return i-ilosc_duplikatow;
    }

    uint32_t ostatni_element = tablica[ N - 1 ];
    return ostatni_element + 1;
}

Wady rozwiązania

Podczas dokonywania tego procesu dochodzi do modyfikacji tablicy danych. W celu uniknięcia zmiany wejściowej tablicy, musimy utworzyć jej kopię, co wpłynie, niestety, na złożoność obliczeniową M(n).

Złożoność obliczeniowa i pamięciowa

Nie alokujemy żadnej pamięci ponad samą tablicę danych, zatem złożoność pamięciowa jest jednostkowa.

Sortowanie ma złożoność n*log(n), natomiast iterowanie po posortowanych elementach jest liniowe. O końcowej złożoności decyduje złożoność sortowania. Ostateczna złożoność obliczeniowa to O(n*log(n)).

Rozwiązanie przez zliczanie

Algorytm:

Poprawimy czas działania algorytmu, wpływając jednak na dodatkową alokację pamięci.

  • Inicjujemy tablicę flag (upakowanych w elementy 32 bitowe), taką, że każda dopuszczalna wartość ma swoją flagę. Dla typu 32-bitowego będzie to 2^32 – 1 flag, co wymaga alokacji ok. 0.5GB danych.
  • Dla każdego elementu tablicy wejściowej ustawiamy odpowiedni bit w naszej tablicy flag.
  • Przeglądamy nasze flagi, aż znajdziemy pierwszą nieustawioną.

Kod

uint32_t ZnajdzBrakujacaLiczba2( uint32_t* tablica, uint32_t N )
{
    if ( N == 0 ) return 0;
    const static uint32_t ELEMENTS_TO_ALLOCATE = numeric_limits< uint32_t >::max() / (sizeof(uint32_t) * 8);
    vector<uint32_t> arr(ELEMENTS_TO_ALLOCATE,0);

    for(uint32_t i = 0; i < N; ++i ) {
        const uint32_t item = tablica[i];
        uint32_t arr_pos = item >> 5;
        uint32_t bit_pos = item & 0x1F;
        const uint32_t mask = 1 << bit_pos;
        uint32_t arr_val = arr[arr_pos];
        arr_val = arr_val | mask;
        arr[arr_pos] = arr_val;
    }

    for (uint32_t i = 0; i < ELEMENTS_TO_ALLOCATE; ++i )
    {
        uint32_t block = arr[i];
        for (int bit_pos = 0; bit_pos<32;++bit_pos)
            if (!(block & ( 1 << bit_pos)))
                return i*32 + bit_pos;
    }

    assert (true);
}

Dyskusja wad rozwiązania oraz złożoności obliczeniowej

  • Olbrzymią wadą rozwiązania jest zapotrzebowanie na pamięć 0.5GB bez względu na ilość elementów tablicy wejściowej.
  • Złożoność obliczeniowa jest liniowa. Należy zaznaczyć, że mamy dość wysokie ograniczenie z dołu na alokacje pamięci.
  • Jeśli chodzi o złożoność pamięciową, to jest ona teoretycznie stała, jednak bardzo wysoka.

Rozwiązanie z std::set (opens new window)

Algorytm

Zamiast alokować ogromny obszar pamięci, dokonamy alokacji pamięć wraz z napływem nowych danych. Dodajemy elementy do zbioru, a na koniec sprawdzamy kolejne elementy na okoliczność istnienia w zbiorze.

Kod

using namespace std;
uint32_t ZnajdzBrakujacaLiczba4( uint32_t* tablica, uint32_t N )
{
    if ( N == 0 ) return 0;
    set<uint32_t> liczby;

    for(uint32_t i = 0; i < N; ++i )
        liczby.insert(tablica[i]);

    for(uint32_t i = 0; i < numeric_limits< uint32_t >::max(); ++i )
        if( liczby.find(i) == liczby.end())
            return i;
    return numeric_limits< uint32_t >::max();
}

Dyskusja wad rozwiązania oraz złożoności obliczeniowej

Klasa std::set jest zaimplementowana za pomocą samo-balansującego drzewa binarnego. Wstawianie, usuwanie, sprawdzenie elementu ma złożoność obliczeniową O(n). Wszystkich elementów jest n, więc ostateczna złożoność obliczeniowa wyniesie O(n*log(n)). Teoretycznie zyskamy na złożoności pamięciowej, bo potrzebujemy zablokować tylko n elementów. Należy tu pamiętać, jednak, że jeśli nasz element ma 4 bajty, to po wstawieniu go do std::set będzie zajmować min. 12 bajtów (zwykle więcej) ze względu na implementacje klasy std::set. Jeśli spodziewamy się, że przechowywanych liczb będzie stosunkowo niewiele, mamy tu znaczną oszczędność. Natomiast w najgorszym przypadku, gdy mamy do przetworzenia 2^32-1 elementów, będziemy potrzebować co najmniej 48GB. Taka ilość pamięci wynika z faktu, że przechowujemy w set pełne elementy - czyli 4 bajty - oraz z faktu, że dla każdego elementu musimy pamiętać dwa wskaźniki, czyli 8 bajtów razem. Elementów mamy 4 miliardy, wartość i dwa wskaźniki dla elementu to 12bajtów, co daje 48GB.

Powyższe rozważania zakładają korzystanie z systemu 32-bitowego. W systemie 64 bitowym potrzebujemy 20 bajtów na element, czyli w najgorszym przypadku – 80GB. W praktyce potrzebujemy jeszcze więcej pamięci, alokacje muszą być wyrównane do 8 bajtów, dodatkowa, zależnie od implementacji, klasa std::set dla każdego węzła drzewa będzie potrzebować dodatkowych informacji np. o jego głębokości.

Pod adresem znaleźć można dokładną analizę zapotrzebowania pamięci.

Rozwiązanie z std::unordered_set (opens new window)

Klasa std::unordered_set pozwala na dostęp do elementów w czasie stałym, co jest znacznym przyśpieszeniem w stosunku do klasy std::set. Ceną tego przyspieszenia jest natomiast uboższy interfejs, m.in. brak metod: lower_bound (opens new window), upper_bound (opens new window).

Kod

#include <unordered_set>
using namespace std;

uint32_t ZnajdzBrakujacaLiczba5( uint32_t* tablica, uint32_t N )
{
    if ( N == 0 ) return 0;
    unordered_set<uint32_t> liczby;

    for(uint32_t i = 0; i < N; ++i )
        liczby.insert(tablica[i]);

    for(uint32_t i = 0; i < numeric_limits< uint32_t >::max(); ++i )
        if( liczby.find(i) == liczby.end())
            return i;
    return numeric_limits< uint32_t >::max();
}

Dyskusja wad rozwiązania oraz złożoności obliczeniowej

Złożoność obliczeniowa jest w tym przypadku liniowa. Złożoność pamięciowa również jest liniowa. Pomimo liniowej złożoności pamięciowej dla najgorszego przypadku może to być nieakceptowalne duży koszt. Zadanie stanowi, że liczb w naszym zbiorze jest nie więcej niż 2^32-1 – jest to trochę więcej niż 4 miliardy. Dla najgorszego przypadku mamy:

  • dla systemu 32bit – 16GB,
  • dla systemu 64bit – 32GB.

Rozwiązanie przez podział zakresu

Algorytm

Tym razem próbujemy pójść na kompromis między dwoma poprzednimi rozwiązaniami.

Dzielimy zbiór wartości na dwa równe zakresy i zliczamy ilość elementów w każdym z tych zakresów. Proces powtarzamy rekurencyjnie. Jeśli mamy N możliwych wartości, to głębokość rekurencji nigdy nie przekroczy log(N).

Kod

using namespace std;

uint32_t ZnajdzBrakujacaLiczba_w_zakresie( uint32_t* tablica, uint32_t N, uint32_t start, uint32_t stop )
{
    uint32_t delta = stop - start;
    uint32_t srodek = start + delta / 2;

    uint32_t ilosc_zakres_1 = 0;
    uint32_t ilosc_zakres_2 = 0;


    for(uint32_t i = 0; i < N; ++i ) {
        uint32_t item = tablica[i];
        if (item >= start && item < srodek) ilosc_zakres_1++;
        if (item >= srodek && item < stop) ilosc_zakres_2++;
    }

    if (ilosc_zakres_1==0)
        return start;

    if (ilosc_zakres_1 < srodek-start )
        return ZnajdzBrakujacaLiczba_w_zakresie(tablica, N, start, srodek);

    if (ilosc_zakres_2==0)
        return srodek;

    if (ilosc_zakres_2 < stop-srodek )
        return ZnajdzBrakujacaLiczba_w_zakresie(tablica, N, srodek, stop);

    return numeric_limits< uint32_t >::max();
}

uint32_t ZnajdzBrakujacaLiczba3( uint32_t* tablica, uint32_t N )
{
    if ( N == 0 ) return 0;
    uint32_t zakres_start = 0;
    uint32_t zakres_stop = numeric_limits< uint32_t >::max();
    return ZnajdzBrakujacaLiczba_w_zakresie(tablica, N, zakres_start, zakres_stop);
}

Dyskusja wad rozwiązania oraz złożoności obliczeniowej

Nie alokujemy dynamicznie pamięci, co daje stałe wymagania pamięciowe. Będziemy iterować maksymalnie 32 razy po naszym zbiorze wejściowym, więc mamy liniową złożoność obliczeniową.

Edit

Dodałem sekcje opisujące rozwiązania oparte o std::set oraz std::unordered_set.

W związku z dyskusją, jaka wywiązała się odnośnie klas std::set i std::unordered_set, opublikowałem dedykowany wpis.