Sortuj plik 1 TB na komputerze z 1 GB pamięci RAM

Question

To pytanie wydaje się proste, ale nie jestem w stanie zrozumieć prawdziwej pracy za nim. Wiem, że ludzie powiedzą, rozbić się na kawałki o wielkości 512 Meg i sortować je tak, jak przy użyciu Merge Sort przy użyciu funkcji Map reduction.

Więc tutaj jest rzeczywista pytanie mam:

Przypuśćmy złamać pliku do 512 Megs fragmencie, a następnie wysłać do różnych maszyn przyjmujących je posortować. załóżmy, że te maszyny używają Sortowania Połączeń. Teraz mówię, miałem 2000 maszyn każdego sortowane 2000, 512 mega kawałka. Teraz, kiedy je scalam, jak to działa? Czy rozmiar znowu się nie zwiększy? Na przykład połączenie dwóch 512 megabajtów sprawi, że 1024Megs będzie wielkości mojego RAMu, więc jak by to działało? Żadna maszyna nie może połączyć kawałka o wielkości większej niż 512 megaków z inną porcją, ponieważ wtedy rozmiar przekracza 1 GB.

Jak na końcu scalania będę mógł kiedykolwiek połączyć dwa porcje o masie 0,5 TB z innym kawałkiem o masie 0,5 TB? Czy koncepcja pamięci wirtualnej wchodzi tutaj w grę?

Jestem tutaj, aby wyjaśnić moje podstawy i mam nadzieję, że zadaję to bardzo ważne pytanie (poprawnie) poprawnie. Kto powinien zrobić to scalenie (po sortowaniu)? Moja maszyna lub kilka z tych 2000 maszyn?

Answer 1

Oto teoretyczny sposób działania. Załóżmy, że masz 2000 plików o pojemności 512 MB, gotowe do utworzenia jednego pliku o pojemności 1 TB.

Jeśli po prostu przejrzysz każdy plik, znajdź, który z nich ma najniższą PIERWSZĄ wartość, przenieś to do pliku docelowego i powtórz, a otrzymasz wszystko w kolejności. Zużycie pamięci RAM powinno być niewielkie, ponieważ nigdy nie będziesz musiał otwierać więcej niż jednej linii naraz.

Oczywiście powinieneś być w stanie to zoptymalizować - zachowaj pierwszy wiersz każdego pliku w pamięci RAM, a ty powinieneś być nieco szybszy.

Answer 2

Wersja krótka, jak scalić jest tak:

1) Aby utworzyć tabelę z jednym gniazdem dla każdej maszyny, którą łączą z.

2) Pytasz każdą maszynę o najniższy wpis, który mają, jeszcze ci nie dał.

3) Usuwasz wpis o najniższej wartości ze swojego stołu, wypisujesz go i prosisz maszynę o ponowne napełnienie wolnego z najniższym wpisem, który jeszcze ci nie dał, pozostawiając puste miejsce, jeśli maszyna nie ma wpisów .

4) Powtarzasz krok 3, dopóki tabela nie będzie pusta.

Umożliwia to połączenie z N komputerów przechowujących tylko N wpisów na raz. Oczywiście można ją z łatwością optymalizować, aby przechowywać wpisy M z każdej maszyny. W takim przypadku musisz przechowywać wpisy N * M, a gdy slot jest pusty, poproś maszynę o wpisanie M, aby ją ponownie napełnić.

Answer 3

Wielką zaletą sortowania scalonego jest to, że nie potrzebujesz dostępu losowego; dostęp sekwencyjny zrobi. To sprawia, że ​​jest to idealne rozwiązanie, gdy zbiór danych nie mieści się w pamięci.

Pojedyncze przejście do scalania wymaga 2 (lub więcej) wejść i generuje jedno wyjście. Po prostu łączycie wejścia w wyjścia, aż pozostanie tylko jeden plik.

Answer 4

Teraz mówię, miałem 2000 maszyn każdego sortowanego 2000, 512 megs kawałka.Teraz po ich scaleniu, jak to działa? Czy rozmiar ponownie nie powiększy się o ? Na przykład połączenie dwóch 512 megabajtów sprawi, że 1024Megs będzie wielkości mojego RAM-u, więc jak by to działało? Żadna maszyna nie może połączyć fragmentu o wielkości większej niż 512 MB z inną porcją, ponieważ , a następnie o wielkości> 1 GB.

To nie działa jak praktyczna implementacja mergesortu. Fajną rzeczą w mergesort (i powiązanych algorytmach sortowania) jest to, że nie musisz mieć całego zbioru danych w pamięci, aby działał. Podczas łączenia wystarczy wczytać do pamięci tylko niewielką część pliku na raz, która zostanie wkrótce opublikowana.

Innymi słowy, nie potrzebujesz bezpośredniego dostępu do mergesort. Gdyby nie ta ładna nieruchomość, byłoby niemożliwe sort the data on tape drives z dostępną technologią. Napędy taśmowe nie są oczywiście nośnikami o dostępie swobodnym, a pamięć RAM była wówczas mierzona w kilobajtach.

Answer 5

Ten problem może być zredukowany do prostszego problemu . Ten problem został zaprojektowany, aby zmusić Cię do podejścia. Oto ona:

• Odbierz porcje = ~ 1 GB, posortuj je jako oddzielne posortowane pliki.
• W systemie plików kończy się 1000 plików posortowanych 1 GB.

• Teraz jest to po prostu problem łączenia k-sortowanych tablic w nową tablicę.

  Łączenie tablic sortowanych K wymaga zachowania minimalnej sterty (Kolejka priorytetowa) z elementami k na raz.

tj k = 1000 (pliki) w naszym przypadku. (1GB pamięci RAM może przechowywać 1000 numerów)

Dlatego należy zachować elementy wyskakujące z kolejki priorytetowej i zapisać na dysku.

Będziesz mieć nowy plik, posortowany w rozmiarze 1 TB.

Patrz: http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Aktualizacja

PS: można wykonać na jednej maszynie z 1 GB pamięci RAM z lepszej struktury danych

Merge można zrobić w czasie krótszym niż O (N) space z kolejką priorytetową tj. O (K) space czyli sedno problemu.