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

Przykładowe rozwiązania

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

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

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

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

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

Algorytm

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

Kod

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

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ż na wykopie wywiązała się dyskusja odnośnie klas std::set i std::unordered_set, opublikowałem wpis Dokładna analiza spotrzebowania na pamięć

 

2 thoughts on “Zadanie rekrutacyjne #4

  1. wtf. std::minmax_element. Iterujesz raz, złożoność pamięciowa O(1), obliczeniowa O(n) gdzie jest to jednokrotne przejście po pamięci. Dodatkowo nie rozwala to cache’u.

    1. Cofam, moje rozwiązanie zupełnie pomija możliwość znalezienia najmniejszej liczby w środku.

Dodaj komentarz

Twój adres email nie zostanie opublikowany.