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

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ą.