Najbardziej efektywny sposób na przechowywanie tysięcy numerów telefonów

To jest pytanie do wywiadu Google:

Do zapisania jest około tysiąca numerów telefonów, z których każdy ma 10 cyfr. Możesz założyć, że pierwsze 5 cyfr każdego z nich jest takie samo w tysiącach liczb. Musisz wykonać następujące operacje: a. Wyszukaj, czy podany numer istnieje. b. Wydrukuj cały numer

Jaki jest najefektywniejszy sposób oszczędzania miejsca?

Odpowiedziałem na tablicę skrótów, a później kodowanie huffmana, ale mój ankieter powiedział, że nie idę w dobrym kierunku. Proszę, pomóż mi tutaj.

Czy użycie sufiksu trie może pomóc?

Idealnie byłoby, gdyby przechowywanie 1000 liczb zajmowało 4 bajty na liczbę, więc w sumie przechowywanie 1000 liczb zajęłoby 4000 bajtów. Ilościowo, chciałbym zredukować pamięć do <4000 bajtów, tak wyjaśnił mi mój ankieter.

Oto ulepszenie odpowiedzi aix . Rozważ użycie trzech „warstw” dla struktury danych: pierwsza jest stałą dla pierwszych pięciu cyfr (17 bitów); więc od tej chwili każdy numer telefonu ma tylko pięć pozostałych cyfr. Te pozostałe pięć cyfr traktujemy jako 17-bitowe binarne liczby całkowite i przechowujemy k z tych bitów jedną metodą, a 17 - k = m inną metodą, określając k na końcu, aby zminimalizować wymaganą przestrzeń.

Najpierw sortujemy numery telefonów (wszystkie zredukowane do 5 cyfr dziesiętnych). Następnie liczymy, ile jest numerów telefonów, dla których liczba binarna składająca się z pierwszych m bitów wynosi 0, dla ilu numerów telefonów pierwsze m bitów to maksymalnie 0 ... 01, dla ilu numerów telefonów pierwsze m bity mają wartość co najwyżej 0 ... 10 itd., aż do liczby numerów telefonów, dla których pierwsze m bitów to 1 ... 11 - ta ostatnia liczba to 1000 (dziesiętnie). Jest 2 ^ m takich zliczeń, a każda z nich to najwyżej 1000. Jeśli pominiemy ostatnią (bo i tak wiemy, że jest to 1000), możemy przechowywać wszystkie te liczby w ciągłym bloku (2 ^ m - 1) * 10 bitów. (10 bitów wystarczy do zapisania liczby mniejszej niż 1024).

Ostatnie k bitów wszystkich (zredukowanych) numerów telefonów jest przechowywanych w sposób ciągły w pamięci; więc jeśli k jest, powiedzmy, 7, to pierwsze 7 bitów tego bloku pamięci (bity od 0 do 6) odpowiada ostatnim 7 bitom pierwszego (zmniejszonego) numeru telefonu, bity od 7 do 13 odpowiadają ostatnim 7 bitom drugiego (zmniejszonego) numeru telefonu itp. Wymaga to 1000 * k bitów, co daje łącznie 17 + (2 ^ (17 - k ) - 1) * 10 + 1000 * k , co daje minimum 11287 dla k daje = 10. Więc możemy przechowywać wszystkie numery telefonów w ceil ( 11287/8) = 1411 bajtów.

Dodatkową przestrzeń można zaoszczędzić, zauważając, że żadna z naszych liczb nie może zaczynać się np. Od np. 1111111 (binarnie), ponieważ najniższa liczba zaczynająca się od tego to 130048, a mamy tylko pięć cyfr dziesiętnych. To pozwala nam zaoszczędzić kilka wpisów z pierwszego bloku pamięci: zamiast 2 ^ m - 1 zliczeń potrzebujemy tylko ceil (99999/2 ^ k ). Oznacza to, że formuła staje się

17 + ceil (99999/2 ^ k ) * 10 + 1000 * k

co zadziwiająco osiąga swoje minimum 10997 zarówno dla k = 9, jak i k = 10, czyli ceil (10997/8) = 1375 bajtów.

Jeśli chcemy wiedzieć, czy dany numer telefonu jest w naszym zestawie, najpierw sprawdzamy, czy pierwsze pięć cyfr binarnych odpowiada pięciu cyfrom, które zapisaliśmy. Następnie podzielimy pozostałe pięć cyfr na jego górne m = 7 bitów (czyli, powiedzmy, m- bitową liczbę M ) i jej dolne k = 10 bitów (liczba K ). Znajdujemy teraz liczbę a [M-1] zredukowanych numerów telefonów, dla których pierwsze m cyfr to co najwyżej M - 1, oraz liczbę a [M] zredukowanych numerów telefonów, dla których pierwsze [M-1] i bity w drugim bloku pamięci, aby sprawdzić, czy znajdziemy m cyfr to co najwyżej M , oba z pierwszego bloku bitów. Teraz sprawdzamy między a [M] tą sekwencję z k K ; w najgorszym przypadku takich sekwencji jest 1000, więc jeśli korzystamy z wyszukiwania binarnego, możemy zakończyć operacjami O (log 1000).

Pseudokod do wydrukowania wszystkich 1000 liczb następuje, gdzie mam dostęp do K ' k -bitowe wejście pierwszego bloku pamięci, jak w [K] i M ” th m wejścia bitowych drugiego bloku pamięci jako b [m]; (obie te operacje wymagałyby kilku bitowych operacji, których zapisywanie jest żmudne). Pierwsze pięć cyfr to liczba c .

i := 0;
for K from 0 to ceil(99999 / 2^k) do
  while i < a[K] do
    print(c * 10^5 + K * 2^k + b[i]);
    i := i + 1;
  end do;
end do;

Może coś pójdzie nie tak z przypadkiem granicznym dla K = ceil (99999/2 ^ k ), ale to dość łatwe do naprawienia.

Wreszcie, z punktu widzenia entropii, nie jest możliwe przechowywanie podzbioru 10 ^ 3 dodatnich liczb całkowitych, z których wszystkie są mniejsze niż 10 ^ 5 w liczbie mniejszej niż ceil (log [2] (dwumian (10 ^ 5, 10 ^ 3)) ) = 8073. Uwzględniając 17, których potrzebujemy na pierwsze 5 cyfr, nadal istnieje luka 10997 - 8090 = 2907 bitów. Ciekawym wyzwaniem jest sprawdzenie, czy istnieją lepsze rozwiązania, w których nadal można stosunkowo skutecznie uzyskać dostęp do numerów!

W dalszej części traktuję liczby jako zmienne całkowite (w przeciwieństwie do łańcuchów):

1. Sortuj liczby.
2. Podziel każdy numer na pięć pierwszych cyfr i pięć ostatnich cyfr.
3. Pierwsze pięć cyfr jest takich samych we wszystkich liczbach, więc zapisz je tylko raz. Będzie to wymagało 17 bitów pamięci.
4. Zapisz pięć ostatnich cyfr każdego numeru osobno. Będzie to wymagało 17 bitów na liczbę.

Podsumowując: pierwsze 17 bitów to wspólny prefiks, kolejne 1000 grup po 17 bitów to pięć ostatnich cyfr każdej liczby przechowywanej w porządku rosnącym.

W sumie patrzymy na 2128 bajtów dla 1000 liczb lub 17,017 bitów na 10-cyfrowy numer telefonu.

Wyszukiwanie to O(log n)(wyszukiwanie binarne), a pełne wyliczenie to O(n).

http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton

Kiedyś miałem wywiad, w którym pytali o struktury danych. Zapomniałem „Array”.

Prawdopodobnie rozważyłbym użycie skompresowanej wersji Trie (prawdopodobnie DAWG jak zasugerował @Misha).

To automagicznie wykorzystałoby fakt, że wszystkie mają wspólny przedrostek.

Wyszukiwanie będzie odbywać się w czasie stałym, a drukowanie w czasie liniowym.

Słyszałem o tym problemie wcześniej (ale bez założenia, że ​​pierwsze 5 cyfr to to samo), a najprostszym sposobem na zrobienie tego było kodowanie ryżu :

1) Ponieważ kolejność nie ma znaczenia, możemy je sortować i zapisywać tylko różnice między kolejnymi wartościami. W naszym przypadku średnie różnice wyniosłyby 100 000/1000 = 100

2) Zakoduj różnice za pomocą kodów Rice (podstawa 128 lub 64) lub nawet kodów Golomba (podstawa 100).

EDYTOWAĆ : Oszacowanie kodowania ryżu z podstawą 128 (nie dlatego, że dałoby to najlepsze wyniki, ale dlatego, że jest łatwiejsze do obliczenia):

Pierwsza wartość zostanie zapisana bez zmian (32 bity).
Pozostałe 999 wartości to różnice (spodziewamy się, że będą małe, średnio 100) będą zawierać:

wartość jednoargumentowa value / 128(zmienna liczba bitów + 1 bit jako terminator)
wartość binarna dla value % 128(7 bitów)

Musimy jakoś oszacować limity (nazwijmy to VBL) dla liczby zmiennych bitów:
dolna granica: uważaj, że mamy szczęście i żadna różnica nie jest większa niż nasza podstawa (w tym przypadku 128). oznaczałoby to dodanie 0 dodatkowych bitów.
wysoki limit: ponieważ wszystkie różnice mniejsze niż podstawa zostaną zakodowane w binarnej części liczby, maksymalna liczba, którą musielibyśmy zakodować w jednostce jednoargumentowej, to 100000/128 = 781,25 (nawet mniej, ponieważ nie oczekujemy, że większość różnic będzie wynosić zero ).

Zatem wynik to 32 + 999 * (1 + 7) + zmienna (0..782) bitów = 1003 + zmienna (0..98) bajtów.

Jest to dobrze znany problem z pereł programowania firmy Bentley.

Rozwiązanie: Usuń pierwsze pięć cyfr z liczb, ponieważ są takie same dla każdego numeru. Następnie użyj operacji bitowych, aby przedstawić pozostałe 9999 możliwych wartości. Będziesz potrzebował tylko 2 ^ 17 bitów do przedstawienia liczb. Każdy bit reprezentuje liczbę. Jeśli bit jest ustawiony, numer znajduje się w książce telefonicznej.

Aby wydrukować wszystkie liczby, po prostu wypisz wszystkie liczby, w których ustawiono bit, połączone z prefiksem. Aby wyszukać podaną liczbę, wykonaj niezbędną arytmetykę bitową, aby sprawdzić bitową reprezentację liczby.

Możesz szukać liczby w O (1), a wydajność przestrzeni jest maksymalna ze względu na reprezentację bitów.

HTH Chris.

Naprawiono pamięć 1073 bajtów na 1000 numerów:

Podstawowym formatem tej metody przechowywania jest przechowywanie pierwszych 5 cyfr, liczby dla każdej grupy i przesunięcia dla każdej liczby w każdej grupie.

Prefiks:
nasz 5-cyfrowy prefiks zajmuje pierwsze 17 bitów .

Grupowanie:
Następnie musimy znaleźć dobre grupowanie liczb. Spróbujmy mieć około 1 numeru na grupę. Ponieważ wiemy, że mamy do przechowania około 1000 numerów, dzielimy 99 999 na około 1000 części. Gdybyśmy wybrali rozmiar grupy na 100, byłoby zmarnowanych bitów, więc wypróbujmy rozmiar grupy 128, który można przedstawić za pomocą 7 bitów. Daje nam to 782 grup do pracy.

Zlicza:
Następnie dla każdej z 782 grup musimy zapisać liczbę wpisów w każdej grupie. Uzyskano by 7-bitową liczbę dla każdej grupy 7*782=5,474 bits, co jest bardzo nieefektywne, ponieważ średnia reprezentowana liczba wynosi około 1 ze względu na sposób, w jaki wybraliśmy nasze grupy.

Tak więc zamiast tego mamy liczby o zmiennej wielkości z początkowymi xjedynkami dla każdej liczby w grupie, po których następuje 0. Tak więc, gdybyśmy mieli liczby w grupie, mielibyśmy x 1'spo nich znak a, 0aby przedstawić liczbę. Na przykład, gdybyśmy mieli 5 liczb w grupie, liczba byłaby reprezentowana przez 111110. Dzięki tej metodzie, jeśli jest 1000 liczb, otrzymujemy 1000 jedynek i 782 0, co daje łącznie 1000 + 782 = 1782 bity dla zliczeń .

Przesunięcie: Na
koniec format każdej liczby będzie po prostu 7-bitowym przesunięciem dla każdej grupy. Na przykład, jeśli 00000 i 00001 są jedynymi liczbami w grupie 0-127, bity dla tej grupy będą 110 0000000 0000001. Zakładając 1000 liczb, będzie 7000 bitów na przesunięcia .

Zatem nasza ostateczna liczba przy założeniu 1000 liczb jest następująca:

17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes

Teraz sprawdźmy, czy nasz wybór rozmiaru grupy poprzez zaokrąglenie do 128 bitów był najlepszym wyborem dla rozmiaru grupy. Wybierając xliczbę bitów do reprezentowania każdej grupy, wzór na rozmiar jest następujący:

Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000

Minimalizowanie tego równania dla liczb całkowitych xdaje x=6, co daje 8580 bitów = 1073 bajty . Tak więc nasze idealne miejsce do przechowywania wygląda następująco:

• Wielkość grupy: 2 ^ 6 = 64
• Liczba grup: 1562

• Całkowita pojemność:

  1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes

Biorąc to pod uwagę jako problem czysto teoretyczny i pozostawiając na boku implementację, najbardziej efektywnym sposobem jest po prostu indeksowanie wszystkich możliwych zestawów 10000 ostatnich cyfr w gigantycznej tabeli indeksującej. Zakładając, że masz dokładnie 1000 liczb, potrzebujesz nieco więcej niż 8000 bitów, aby jednoznacznie zidentyfikować bieżący zestaw. Nie ma możliwości większej kompresji, ponieważ wtedy mielibyśmy dwa zbiory, które są identyfikowane z tym samym stanem.

Problem z tym polega na tym, że każdy z 2 ^ 8000 zestawów w swoim programie musiałby być reprezentowany jako lut, a nawet Google nie byłoby w stanie tego zdalnie.

Lookup to O (1), wypisując całą liczbę O (n). Wstawienie byłoby O (2 ^ 8000), co teoretycznie jest O (1), ale w praktyce jest bezużyteczne.

W wywiadzie udzieliłbym tylko takiej odpowiedzi, gdybym był pewien, że firma szuka kogoś, kto potrafi dużo myśleć nieszablonowo. W przeciwnym razie może to sprawić, że będziesz wyglądać jak teoretyk, który nie martwi się o prawdziwy świat.

EDYCJA : Ok, oto jedna "implementacja".

Kroki do wykonania implementacji:

1. Weź stałą tablicę o rozmiarze 100 000 * (1000 wybierz 100 000) bitów. Tak, zdaję sobie sprawę, że ta tablica będzie potrzebować więcej miejsca niż atomy we wszechświecie o kilka wielkości.
2. Podziel tę dużą tablicę na kawałki po 100 000 każdy.
3. W każdym kawałku przechowuj tablicę bitową dla jednej określonej kombinacji ostatnich pięciu cyfr.

To nie jest program, ale rodzaj metaprogramu, który skonstruuje gigantyczny LUT, którego można teraz użyć w programie. Stałe rzeczy programu zwykle nie są liczone przy obliczaniu wydajności przestrzeni, więc nie przejmujemy się tą tablicą podczas wykonywania naszych ostatecznych obliczeń.

Oto jak używać tej tablicy LUT:

1. Kiedy ktoś daje ci 1000 liczb, osobno przechowujesz pierwsze pięć cyfr.
2. Dowiedz się, które fragmenty Twojej tablicy pasują do tego zestawu.
3. Przechowuj numer zestawu w pojedynczym 8074-bitowym numerze (nazwij to c).

Oznacza to, że do przechowywania potrzebujemy tylko 8091 bitów, które tutaj udowodniliśmy, że są optymalnym kodowaniem. Znalezienie odpowiedniego kawałka wymaga jednak O (100 000 * (100 000 wybierz 1000)), co zgodnie z regułami matematycznymi jest O (1), ale w praktyce zawsze zajmie więcej czasu niż czas wszechświata.

Jednak wyszukiwanie jest proste:

1. pasek pierwszych pięciu cyfr (pozostały numer będzie nazywany n ').
2. sprawdź, czy pasują
3. Oblicz i = c * 100000 + n '
4. Sprawdź, czy bit w i w LUT jest ustawiony na jeden

Wydrukowanie wszystkich liczb jest również proste (i faktycznie przyjmuje O (100000) = O (1), ponieważ zawsze musisz sprawdzić wszystkie bity bieżącego fragmentu, więc przeliczyłem to powyżej).

Nie nazwałbym tego „wdrożeniem” z powodu rażącego lekceważenia ograniczeń (rozmiaru wszechświata i czasu, w którym ten wszechświat żył, albo będzie istniała Ziemia). Jednak w teorii jest to optymalne rozwiązanie. W przypadku mniejszych problemów można to zrobić, a czasami zostanie to zrobione. Na przykład sieci sortowania są przykładem tego sposobu kodowania i mogą być używane jako ostatni krok w algorytmach sortowania rekurencyjnego, aby uzyskać duże przyspieszenie.

Odpowiada to przechowywaniu tysiąca nieujemnych liczb całkowitych, z których każda jest mniejsza niż 100 000. W tym celu możemy użyć czegoś takiego jak kodowanie arytmetyczne.

Ostatecznie liczby zostaną zapisane na posortowanej liście. Zwracam uwagę, że oczekiwana różnica między sąsiednimi liczbami na liście wynosi 100 000/1000 = 100, co można przedstawić za pomocą 7 bitów. Będzie również wiele przypadków, w których potrzeba więcej niż 7 bitów. Prostym sposobem przedstawienia tych mniej powszechnych przypadków jest przyjęcie schematu utf-8, w którym jeden bajt reprezentuje 7-bitową liczbę całkowitą, chyba że ustawiony jest pierwszy bit, w którym to przypadku następny bajt jest odczytywany w celu uzyskania 14-bitowej liczby całkowitej, chyba że jego pierwszy bit jest ustawiany, w którym to przypadku następny bajt jest odczytywany jako reprezentujący 21-bitową liczbę całkowitą.

Zatem co najmniej połowa różnic między kolejnymi liczbami całkowitymi może być reprezentowana przez jeden bajt, a prawie cała reszta wymaga dwóch bajtów. Kilka liczb oddzielonych większymi różnicami niż 16 384 będzie wymagało trzech bajtów, ale nie może ich być więcej niż 61. Przeciętna pamięć będzie wtedy wynosiła około 12 bitów na numer lub nieco mniej lub maksymalnie 1500 bajtów.

Wadą tego podejścia jest to, że sprawdzenie istnienia liczby jest teraz O (n). Jednak nie określono wymogu złożoności czasowej.

Po napisaniu zauważyłem, że ruslik zasugerował już powyższą metodę różnicową, jedyną różnicą jest schemat kodowania. Mój jest prawdopodobnie prostszy, ale mniej wydajny.

Wystarczy szybko zapytać o powód, dla którego nie chcielibyśmy zmienić liczb na podstawową 36. Może to nie zaoszczędzić tak dużo miejsca, ale z pewnością zaoszczędzi czas na wyszukiwaniu, ponieważ będziesz patrzeć na znacznie mniej niż 10 cyfr. Albo podzieliłbym je na pliki w zależności od każdej grupy. więc nazwałbym plik (111) -222.txt, a następnie zapisałbym tylko numery, które pasują do tej grupy, a następnie dałbym je przeszukiwać w kolejności numerycznej w ten sposób, zawsze mogę sprawdzić, czy plik się kończy. zanim przeprowadzę większe wyszukiwanie. lub, aby być poprawnym, uruchomiłbym wyszukiwanie binarne jednego pliku, aby sprawdzić, czy zostanie zamknięty. i jeszcze jedno ogólne przeszukanie zawartości pliku

Dlaczego nie zachować prostoty? Użyj tablicy struktur.

Możemy więc zapisać pierwsze 5 cyfr jako stałą, więc na razie zapomnij o tych.

65535 to najwięcej, które można zapisać w 16-bitowej liczbie, a maksymalna liczba, jaką możemy mieć, to 99999, co pasuje do 17-tego bitu z maksimum 131071.

Używanie 32-bitowych typów danych jest marnotrawstwem, ponieważ potrzebujemy tylko 1 bitu z tych dodatkowych 16-bitów ... dlatego możemy zdefiniować strukturę, która ma wartość logiczną (lub znak) i liczbę 16-bitową.

Zakładając C / C ++

typedef struct _number {

    uint16_t number;
    bool overflow;
}Number;

Ta struktura zajmuje tylko 3 bajty, a potrzebujemy tablicy o wartości 1000, czyli łącznie 3000 bajtów. Zmniejszyliśmy całkowitą przestrzeń o 25%!

Jeśli chodzi o przechowywanie liczb, możemy wykonać prostą matematykę bitową

overflow = (number5digits & 0x10000) >> 4;
number = number5digits & 0x1111;

I odwrotnie

//Something like this should work
number5digits = number | (overflow << 4);

Aby wydrukować je wszystkie, możemy użyć prostej pętli nad tablicą. Pobieranie określonej liczby odbywa się oczywiście w stałym czasie, ponieważ jest to tablica.

for(int i=0;i<1000;i++) cout << const5digits << number5digits << endl;

Aby wyszukać liczbę, potrzebujemy posortowanej tablicy. Więc kiedy liczby są zapisane, posortuj tablicę (osobiście wybrałbym sortowanie przez scalanie, O (nlogn)). Teraz, aby wyszukać, zastosowałbym metodę sortowania przez scalanie. Podziel tablicę i zobacz, w której z nich znajduje się nasza liczba. Następnie wywołaj funkcję tylko na tej tablicy. Rób to rekurencyjnie, dopóki nie uzyskasz dopasowania i nie zwrócisz indeksu, w przeciwnym razie nie istnieje i nie wypisze kodu błędu. To wyszukiwanie byłoby dość szybkie, a najgorszy przypadek jest nadal lepszy niż O (nlogn), ponieważ absolutnie wykona się w krótszym czasie niż sortowanie przez scalanie (za każdym razem powtarzając tylko jedną stronę podziału zamiast obu stron :)), co jest O (nlogn).

Moje rozwiązanie: najlepszy przypadek 7,025 bitów / liczba, najgorszy przypadek 14,193 bitów / liczba, przybliżona średnia 8,551 bitów / liczba. Kodowane strumieniowo, bez losowego dostępu.

Jeszcze przed przeczytaniem odpowiedzi Ruslika od razu pomyślałem o zakodowaniu różnicy między poszczególnymi liczbami, ponieważ będzie ona mała i powinna być stosunkowo spójna, ale rozwiązanie musi też być w stanie uwzględnić najgorszy scenariusz. Mamy przestrzeń 100 000 liczb, które zawierają tylko 1000 liczb. W idealnie jednolitej książce telefonicznej każdy numer byłby większy od poprzedniego o 100:

55555-12 3 45
55555-12 4 45
55555-12 5 45

Gdyby tak było, zakodowanie różnic między liczbami wymagałoby zerowej pamięci, ponieważ jest to znana stała. Niestety, liczby mogą różnić się od idealnych kroków 100. Zakodowałbym różnicę od idealnego przyrostu 100, tak że jeśli dwie sąsiednie liczby różnią się o 103, zakodowałbym liczbę 3, a jeśli dwie sąsiednie liczby różnią się o 92, I zakoduje -8. Nazywam deltę z idealnego przyrostu 100 „ wariancją ”.

Odchylenie może wynosić od -99 (tj. Dwa kolejne numery) do 99000 (cała książka telefoniczna składa się z numerów 00000… 00999 i dodatkowego najdalszego numeru 99999), co stanowi zakres 99100 możliwych wartości.

Będę dążyć przeznaczyć minimalny przechowywanie do zakodowania najczęściej występujące różnice i rozszerzenia pamięci masowej, jeśli napotka większych różnic (jak Protobuf „s varint). Użyję fragmentów siedmiu bitów, sześciu do przechowywania i dodatkowego bitu flagi na końcu, aby wskazać, że ta wariancja jest przechowywana z dodatkową porcją po bieżącej, maksymalnie do trzech fragmentów (co zapewni maksymalnie 3 * 6 = 18 bitów pamięci, czyli 262144 możliwych wartości, więcej niż liczba możliwych wariancji (99100). Każda dodatkowa porcja następująca po podniesionej fladze ma bity o wyższym znaczeniu, więc pierwsza porcja zawsze ma bity 0- 5, opcjonalny drugi fragment ma bity 6-11, a opcjonalny trzeci fragment ma bity 12-17.

Pojedyncza porcja zapewnia sześć bitów pamięci, która może pomieścić 64 wartości. Chciałbym zmapować 64 najmniejsze wariancje, aby zmieściły się w tym pojedynczym fragmencie (tj. Wariancje od -32 do +31), więc użyję kodowania ProtoBuf ZigZag, aż do wariancji od -99 do +98 (ponieważ nie ma potrzeby dla ujemnej wariancji powyżej -99), w którym to momencie przełączę się na zwykłe kodowanie, przesunięte o 98:  

Wariancja | Wartość zakodowana
----------- + ----------------
    0 | 0
   -1 | 1
    1 | 2
   -2 | 3
    2 | 4
   -3 | 5
    3 | 6
   ... | ...
  -31 | 61
   31 | 62
  -32 | 63
----------- | --------------- 6 bitów
   32 | 64
  -33 | 65
   33 | 66
   ... | ...
  -98 | 195
   98 | 196
  -99 | 197
----------- | --------------- Koniec zygzaka
   100 | 198
   101 | 199
   ... | ...
  3996 | 4094
  3997 | 4095
----------- | --------------- 12 bitów
  3998 | 4096
  3999 | 4097
   ... | ...
 262045 | 262143
----------- | --------------- 18 bitów

Kilka przykładów tego, jak wariancje byłyby kodowane jako bity, w tym flaga wskazująca dodatkowy fragment:

Wariancja | Zakodowane bity
----------- + ----------------
     0 | 000000 0
     5 | 001010 0
    -8 | 001111 0
   -32 | 111111 0
    32 | 000000 1 000001 0
   -99 | 000101 1 000011 0
   177 | 010011 1 000100 0
 14444 | 001110 1 100011 1 000011 0

Zatem pierwsze trzy numery przykładowej książki telefonicznej zostaną zakodowane jako strumień bitów w następujący sposób:

BIN 000101001011001000100110010000011001 000110 1 010110 1 00001 0
PH # 55555-12345 55555-12448 55555-12491
POS 1 2 3

W najlepszym przypadku książka telefoniczna jest rozmieszczona w pewnym stopniu równomiernie i nie ma dwóch numerów telefonów, które mają wariancję większą niż 32, więc użyłby 7 bitów na numer plus 32 bity na numer początkowy, co daje łącznie 32 + 7 * 999 = 7025 bitów .
Scenariusz mieszany , w którym wariancja 800 numerów telefonów mieści się w jednym fragmencie (800 * 7 = 5600), 180 numerów mieści się w dwóch częściach (180 * 2 * 7 = 2520), a 19 numerów mieści się w trzech fragmentach (20 * 3 * 7 = 399), plus początkowe 32 bity, daje łącznie 8551 bitów .
W najgorszym przypadku 25 liczb mieści się w trzech fragmentach (25 * 3 * 7 = 525 bitów), a pozostałe 974 liczb mieści się w dwóch fragmentach (974 * 2 * 7 = 13636 bitów) plus 32 bity na pierwszą liczbę w przypadku tabliczki suma14193 bitów .

   Ilość zakodowanych numerów |
 1-chunk | 2-częściowe | 3-częściowe | Całkowita liczba bitów
--------- + ---------- + ---------- + ------------
   999 | 0 | 0 | 7025
   800 | 180 | 19 | 8551
    0 | 974 | 25 | 14193

Widzę cztery dodatkowe optymalizacje, które można wykonać, aby jeszcze bardziej zmniejszyć wymaganą przestrzeń:

1. Trzeci fragment nie potrzebuje pełnych siedmiu bitów, może mieć tylko pięć bitów i bez bitu flagi.
2. Może nastąpić wstępne przekazanie liczb w celu obliczenia najlepszych rozmiarów dla każdego fragmentu. Może dla pewnej książki telefonicznej byłoby optymalne, gdyby pierwszy fragment miał 5 + 1 bitów, drugi 7 + 1, a trzeci 5 + 1. To dodatkowo zmniejszyłoby rozmiar do minimum 6 * 999 + 32 = 6026 bitów, plus dwa zestawy trzech bitów do przechowywania rozmiarów fragmentów 1 i 2 (rozmiar fragmentu 3 to reszta z wymaganych 16 bitów) w sumie 6032 bitów!
3. Ten sam przebieg początkowy może obliczyć lepszy oczekiwany przyrost niż domyślny 100. Może jest książka telefoniczna, która zaczyna się od 55555-50000, a więc ma połowę zakresu liczb, więc oczekiwany przyrost powinien wynosić 50. A może istnieje nieliniowa można zastosować rozkład (być może odchylenie standardowe) i jakiś inny optymalny oczekiwany przyrost. Zmniejszyłoby to typową wariancję i pozwoliłoby na użycie jeszcze mniejszej pierwszej porcji.
4. Dalszą analizę można przeprowadzić w pierwszym przebiegu, aby umożliwić podzielenie książki telefonicznej na partycje, przy czym każda partycja ma własną oczekiwaną optymalizację przyrostu i rozmiaru fragmentu. Pozwoliłoby to na mniejszy rozmiar pierwszego fragmentu dla niektórych wysoce jednorodnych części książki telefonicznej (zmniejszenie liczby zużytych bitów) i większe rozmiary fragmentów dla niejednorodnych części (zmniejszenie liczby bitów marnowanych na flagi kontynuacji).

Prawdziwe pytanie dotyczy przechowywania pięciocyfrowych numerów telefonów.

Sztuczka polega na tym, że do przechowywania zakresu liczb od 0 do 99 999 potrzeba 17 bitów. Ale przechowywanie 17-bitów w konwencjonalnych 8-bajtowych granicach słów jest kłopotliwe. Dlatego pytają, czy można zrobić w mniej niż 4k, nie używając 32-bitowych liczb całkowitych.

Pytanie: czy wszystkie kombinacje liczb są możliwe?

Ze względu na charakter systemu telefonicznego możliwych kombinacji może być mniej niż 65 tys. Zakładam, że tak, ponieważ mówimy o ostatnich pięciu pozycjach w numerze telefonu, a nie o numerze kierunkowym czy prefiksach wymiany.

Pytanie: czy ta lista będzie statyczna, czy będzie musiała obsługiwać aktualizacje?

Jeśli jest statyczny , to kiedy przychodzi czas na zapełnienie bazy danych, policz liczbę cyfr <50 000, a liczbę cyfr> = 50 000. Przydziel dwie tablice o uint16odpowiedniej długości: jedną dla liczb całkowitych poniżej 50 000 i jedną dla wyższego zestawu. Podczas przechowywania liczb całkowitych w wyższej tablicy odejmij 50 000, a podczas odczytywania liczb całkowitych z tej tablicy dodaj 50 000. Teraz zapisałeś 1000 liczb całkowitych w 2000 8-bajtowych słowach.

Tworzenie książki telefonicznej będzie wymagało dwóch przemierzania danych wejściowych, ale wyszukiwanie powinno odbywać się średnio o połowę krócej niż w przypadku jednej tablicy. Gdyby czas wyszukiwania był bardzo ważny, mógłbyś użyć więcej tablic dla mniejszych zakresów, ale myślę, że przy tych rozmiarach ograniczenie wydajności wiązałoby się z wyciąganiem tablic z pamięci, a 2k prawdopodobnie schowałoby się w pamięci podręcznej procesora, jeśli nie zarejestruje miejsca na czymkolwiek, z czego ich używałbyś dni.

Jeśli jest dynamiczna , przydziel jedną tablicę o wielkości około 1000 uint16i dodaj liczby w kolejności posortowanej. Ustaw pierwszy bajt na 50 001, a drugi bajt na odpowiednią wartość null, taką jak NULL lub 65 000. Kiedy przechowujesz numery, przechowuj je w posortowanej kolejności. Jeśli liczba jest mniejsza niż 50 001, zapisz ją przed znacznikiem 50 001. Jeśli liczba wynosi 50 001 lub więcej, zapisz ją po znaczniku 50 001, ale odejmij 50 000 od zapisanej wartości.

Twoja tablica będzie wyglądać mniej więcej tak:

00001 = 00001
12345 = 12345
50001 = reserved
00001 = 50001
12345 = 62345
65000 = end-of-list

Tak więc, kiedy szukasz numeru w książce telefonicznej, przejdziesz przez tablicę i jeśli osiągniesz wartość 50 001, zaczniesz dodawać 50 000 do wartości tablicy.

To sprawia, że ​​wstawki są bardzo drogie, ale wyszukiwanie jest łatwe i nie wydasz więcej niż 2k na przechowywanie.