Notatnik techniczny

Zadanie rekrutacyjne #4

Znajdź liczbę, której nie ma

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 = {0,1,2,2,2,2,3,2,1,0}
    Poprawny wynik: 4
  • Dane = {1,2,6,7}
    Poprawny wynik: 0
  • Dane = {0,1,1,2,7}
    Poprawny wynik: 3

Rozwiązanie przez sortowanie

Algorytm

  • Sortujemy całą tablicę.
  • Iterujemy po elementach, zliczając powtórzenia, aż znajdziemy brakujący element.
  • 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

  • Modyfikujemy tablicę danych.
  • Gdybyśmy chcieli uniknąć modyfikacji wejściowej tablicy, musimy zrobić jej kopię, za co zapłacimy złożonością obliczeniową M(n).

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

Nie alokujemy żadnej pamięci ponad samą tablicę danych, tak więc 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

W poprzednim rozwiązaniu sortowanie decydowało o ostatecznej złożoności obliczeniowej. Tym razem poprawimy czas działania algorytmu, płacąc cenę w postaci dodatkowej alokacji 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ą nie ustawioną.

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.
  • Złożoność pamięciowa jest teoretycznie stała, jednak bardzo wysoka.

Rozwiązanie z std::set

Algorytm

Zamiast alokować ogromny obszar pamięci, alokujemy 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ć, że jeśli nasz element ma 4 bajty, to po wstawieniu go do std::set będzie zajmować min. 12 bajtów (często 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. Dokładna analiza spotrzebowania na pamięć

Rozwiązanie z std::unordered_set

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ą za to przyśpieszenie jest uboższy interfejs, m.in. brak metod: lower_bound, upper_bound.

Algorytm

Algorytm jest identyczny jak w poprzednim przykładzie. Korzystamy jedynie z innego kontenera.

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. Jeśli chcemy włożyć do kontenera całą liczbę, to 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.

Ponieważ wywiązała się dyskusja odnośnie klas std::set i std::unordered_set, opublikowałem wpis Dokładna analiza spotrzebowania na pamięć