Rozwiązanie jest możliwe tylko ze względu na różnicę między 1 megabajtem a 1 milionem bajtów. Istnieje około 2 do potęgi 8093729.5 różnych sposobów wyboru 1 miliona 8-cyfrowych liczb z dozwolonymi duplikatami i zamówienia nieistotnego, więc maszyna z zaledwie 1 milionem bajtów RAM nie ma wystarczającej liczby stanów, aby reprezentować wszystkie możliwości. Ale 1M (mniej 2k dla TCP / IP) to 1022 * 1024 * 8 = 8372224 bitów, więc rozwiązanie jest możliwe.
Część 1, wstępne rozwiązanie
To podejście wymaga nieco więcej niż 1 mln, dopracuję je, aby pasowało do 1 mln później.
Będę przechowywać zwięzłą posortowaną listę liczb z zakresu od 0 do 99999999 jako sekwencję list podrzędnych liczb 7-bitowych. Pierwsza lista zawiera numery od 0 do 127, druga lista zawiera liczby od 128 do 255, itd. 100000000/128 to dokładnie 781250, więc 781250 takie listy będą potrzebne.
Każda podlista składa się z 2-bitowego nagłówka podlisty, po którym następuje treść podlisty. Ciało podlisty zajmuje 7 bitów na wpis podlisty. Wszystkie listy podrzędne są łączone razem, a format umożliwia określenie, gdzie kończy się jedna lista, a zaczyna druga. Całkowita pamięć potrzebna do wypełnienia listy wynosi 2 * 781250 + 7 * 1000000 = 8562500 bitów, co stanowi około 1.021 megabajtów.
4 możliwe wartości nagłówka listy podrzędnej to:
00 Pusta podlista, nic nie wynika.
01 Singleton, na liście podrzędnej jest tylko jeden wpis i zawiera go kolejnych 7 bitów.
10 Podlista zawiera co najmniej 2 różne liczby. Wpisy są przechowywane w kolejności malejącej, z tym wyjątkiem, że ostatni wpis jest mniejszy lub równy pierwszemu. Pozwala to zidentyfikować koniec podlisty. Na przykład liczby 2,4,6 byłyby przechowywane jako (4,6,2). Liczby 2,2,3,4,4 będą przechowywane jako (2,3,4,4,2).
11 Podlista zawiera 2 lub więcej powtórzeń jednego numeru. Kolejne 7 bitów podaje liczbę. Następnie przychodzi zero lub więcej 7-bitowych wpisów o wartości 1, a następnie 7-bitowych wpisów o wartości 0. Długość treści listy podrzędnej określa liczbę powtórzeń. Na przykład liczby 12,12 byłyby przechowywane jako (12,0), liczby 12,12,12 byłyby przechowywane jako (12,1,0), 12,12,12,12 to (12,1 , 1,0) i tak dalej.
Zaczynam od pustej listy, czytam kilka liczb i przechowuję je jako 32-bitowe liczby całkowite, sortuję nowe liczby na miejscu (prawdopodobnie za pomocą heapsortu), a następnie łączę je w nową zwartą listę posortowaną. Powtarzaj tę czynność, aż nie będzie już więcej liczb do odczytania, a następnie ponownie przejrzyj listę kompaktową, aby wygenerować wynik.
Poniższy wiersz przedstawia pamięć tuż przed rozpoczęciem operacji scalania listy. „O” to region przechowujący posortowane 32-bitowe liczby całkowite. „X” to region zawierający starą listę kompaktową. Znaki „=” to pomieszczenie rozszerzeń dla listy kompaktowej, 7 bitów na każdą liczbę całkowitą w „O”. „Z” to inne losowe koszty ogólne.
ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX
Procedura scalania rozpoczyna się od skrajnego lewego „O” i skrajnego lewego „X” i zaczyna pisać od skrajnego lewego „=”. Wskaźnik zapisu nie łapie wskaźnika odczytu listy kompaktowej, dopóki wszystkie nowe liczby całkowite nie zostaną scalone, ponieważ oba wskaźniki przesuwają 2 bity dla każdej podlisty i 7 bitów dla każdego wpisu na starej liście zwartej, a jest wystarczająco dużo miejsca dla 7-bitowe wpisy dla nowych numerów.
Część 2, wbijając go w 1M
Aby wycisnąć powyższe rozwiązanie do 1M, muszę uczynić format listy kompaktowej nieco bardziej kompaktowym. Pozbędę się jednego z typów listy podrzędnej, aby były tylko 3 różne możliwe wartości nagłówka listy podrzędnej. Następnie mogę użyć „00”, „01” i „1” jako wartości nagłówka listy podrzędnej i zapisać kilka bitów. Rodzaje podlisty to:
Pusta lista, nic nie wynika.
B Singleton, na liście podrzędnej jest tylko jeden wpis i zawiera go kolejnych 7 bitów.
C Podlista zawiera co najmniej 2 różne liczby. Wpisy są przechowywane w kolejności malejącej, z tym wyjątkiem, że ostatni wpis jest mniejszy lub równy pierwszemu. Pozwala to zidentyfikować koniec podlisty. Na przykład liczby 2,4,6 byłyby przechowywane jako (4,6,2). Liczby 2,2,3,4,4 będą przechowywane jako (2,3,4,4,2).
D Podlista składa się z 2 lub więcej powtórzeń jednego numeru.
Moje 3 nagłówki podlisty to „A”, „B” i „C”, więc potrzebuję sposobu na reprezentowanie podlist typu D.
Załóżmy, że mam nagłówek podlisty typu C, a po nim 3 wpisy, takie jak „C [17] [101] [58]”. Nie może to być częścią prawidłowej podlisty typu C, jak opisano powyżej, ponieważ trzeci wpis jest mniejszy niż drugi, ale większy niż pierwszy. Mogę użyć tego typu konstruktu do przedstawienia podlisty typu D. Krótko mówiąc, gdziekolwiek mam „C {00 ?????} {1 ??????} {01 ?????}” to niemożliwa podlista typu C. Użyję tego do przedstawienia podlisty składającej się z 3 lub więcej powtórzeń jednego numeru. Pierwsze dwa 7-bitowe słowa kodują liczbę (bity „N” poniżej), po których następuje zero lub więcej słów {0100001}, a następnie słowo {0100000}.
For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.
To tylko pozostawia listy, które zawierają dokładnie 2 powtórzenia jednego numeru. Przedstawię te z innym niemożliwym wzorcem listy typu C: „C {0 ??????} {11 ?????} {10 ?????}”. Jest dużo miejsca na 7 bitów liczby w pierwszych 2 słowach, ale ten wzór jest dłuższy niż podlista, którą reprezentuje, co sprawia, że sprawy są nieco bardziej złożone. Pięć znaków zapytania na końcu można uznać za nie stanowiących części wzorca, więc mam: „C {0NNNNNN} {11N ????}} 10” jako mój wzorzec, a liczbę do powtórzenia zapisano w „N „s. To o 2 bity za długo.
Będę musiał pożyczyć 2 bity i spłacić je z 4 nieużywanych bitów w tym wzorze. Podczas czytania, po napotkaniu „C {0NNNNNN} {11N00AB} 10”, wypisz 2 wystąpienia liczby w „N”, nadpisz „10” na końcu bitami A i B i przewiń wskaźnik odczytu o 2 bitów Odczyty niszczące są odpowiednie dla tego algorytmu, ponieważ każda zwarta lista jest przeprowadzana tylko raz.
Pisząc podlistę z 2 powtórzeniami pojedynczej liczby, napisz „C {0NNNNNN} 11N00” i ustaw licznik pożyczonych bitów na 2. Przy każdym zapisie, w którym licznik pożyczonych bitów jest różny od zera, jest zmniejszany dla każdego zapisanego bitu i „10” jest zapisywane, gdy licznik osiągnie zero. Tak więc kolejne 2 zapisane bity trafią do gniazd A i B, a następnie „10” zostanie upuszczone na koniec.
Z 3 wartościami nagłówków listy podrzędnej reprezentowanymi przez „00”, „01” i „1”, mogę przypisać „1” do najpopularniejszego typu listy. Potrzebuję małej tabeli, aby zmapować wartości nagłówka listy podrzędnej na typy listy podlisty, i potrzebuję licznika wystąpień dla każdego typu listy podlisty, aby wiedzieć, jakie jest najlepsze mapowanie nagłówka listy podrzędnej.
Najgorszy przypadek minimalnej reprezentacji w pełni zaludnionej listy zwartej występuje, gdy wszystkie typy podlisty są równie popularne. W takim przypadku zapisuję 1 bit na każde 3 nagłówki listy podrzędnej, więc rozmiar listy wynosi 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083.3 bitów. Zaokrąglanie w górę do 32-bitowej granicy słów, czyli 8302112 bitów lub 1037764 bajtów.
1M minus 2k dla stanu TCP / IP i buforów wynosi 1022 * 1024 = 1046528 bajtów, pozostawiając mi 8764 bajtów do zabawy.
Ale co z procesem zmiany mapowania nagłówków sublist? Na poniższej mapie pamięci „Z” to losowy narzut, „=” to wolne miejsce, „X” to zwarta lista.
ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Zacznij czytać od lewej „X” i zacznij pisać od lewej „=” i pracuj w prawo. Po zakończeniu lista kompaktowa będzie nieco krótsza i znajdzie się na niewłaściwym końcu pamięci:
ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======
Więc będę musiał przesunąć go w prawo:
ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
W procesie zmiany mapowania nagłówków do 1/3 nagłówków listy podrzędnej zmieni się z 1-bitowej na 2-bitową. W najgorszym przypadku będą one znajdować się na początku listy, więc zanim zacznę, będę potrzebować co najmniej 781250/3 bitów wolnego miejsca, co zabierze mnie z powrotem do wymagań dotyczących pamięci poprzedniej wersji listy kompaktowej: (
Aby obejść ten problem, podzielę 781250 podlist na 10 grup podlist po 78125 podlist. Każda grupa ma własne niezależne mapowanie nagłówka listy podrzędnej. Używając liter od A do J dla grup:
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
Każda grupa listy podrzędnej kurczy się lub pozostaje taka sama podczas zmiany mapowania nagłówka listy podrzędnej:
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======
ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
Najgorszy przypadek tymczasowego rozszerzenia grupy listy podrzędnej podczas zmiany mapowania wynosi 78125/3 = 26042 bitów, poniżej 4k. Jeśli pozwolę 4k plus 1037764 bajtów na w pełni wypełnioną listę kompaktową, to pozostawi mi 8764 - 4096 = 4668 bajtów dla „Z” na mapie pamięci.
To powinno wystarczyć dla 10 tabel odwzorowania nagłówków podlisty, 30 wystąpień nagłówka podlisty i pozostałych kilku liczników, wskaźników i małych buforów, których potrzebuję, i przestrzeni, której użyłem bez zauważenia, na przykład przestrzeni stosu dla adresów zwrotnych wywołań funkcji i zmienne lokalne.
Część 3, ile czasu zajmie uruchomienie?
W przypadku pustej listy kompaktowej 1-bitowy nagłówek listy zostanie użyty do pustej listy podrzędnej, a początkowy rozmiar listy będzie wynosił 781250 bitów. W najgorszym przypadku lista powiększa się o 8 bitów na każdą dodaną liczbę, więc 32 + 8 = 40 bitów wolnego miejsca jest potrzebnych do umieszczenia każdej z 32-bitowych liczb na górze bufora listy, a następnie posortowania i scalenia. W najgorszym przypadku zmiana mapowania nagłówka listy podrzędnej powoduje użycie miejsca 2 * 781250 + 7 * wpisów - 781250/3 bitów.
Przy polityce zmiany mapowania nagłówka listy podrzędnej po co piątym scaleniu, gdy na liście znajduje się co najmniej 800 000 liczb, najgorszy przypadek wymagałby w sumie około 30 mln czynności związanych z czytaniem i pisaniem list.
Źródło:
http://nick.cleaton.net/ramsortsol.html