Jak sortować n^2 elementy w 2n RAM

Czy ktoś może mi powiedzieć, jak sortować n^2 elementów za pomocą 2n ilość pamięci RAM. Jednym z możliwych sposobów jest podział na n tablic o rozmiarze n każdy. A następnie wykonaj sortowanie scalające wewnątrz n elementów, a następnie w końcu zachowaj wielkość n sterty na n tablicach. Jednakże oznaczałoby to, że za każdym razem, gdy jeden element zostanie umieszczony, robię odczyt dysku i za każdym razem, gdy elementy są kompletne, robię zapis na dysku. Jakieś lepsze sugestie? Dzięki.Jak sortować n^2 elementy w 2n RAM

Źródło

2010-11-22 user515974

Innym sposobem na wyrażenie pytania jest "Jak sortować n elementów w pamięci RAM O (log (n))". – erikkallen

Czy to nie powinno być O (sqrt (n))? –

Knuth ma cały rozdział na ten temat w * Sztuka programowania komputerowego * Tom 3. –

To niemożliwe. Potrzebujesz tylko pamięci n^2 dla samych elementów.

Jeśli nie policzycie tego oczywistego zużycia pamięci, polecam jeden z algorytmów sortowania miejscowego, takich jak heapsort. Zajmie to O (1) dodatkową przestrzeń.

Jeśli szukasz zewnętrznego algorytmu sortowania, w którym pamięć zewnętrzna nie jest liczona, ale tylko wewnętrzna, zalecam korzystanie z bottom-up mergesort. Możesz to wykorzystać, by zużywać tyle pamięci wewnętrznej, ile chcesz; zużywać około 2n pamięci, zawsze czytać n/2 elementy z każdego częściowo posortowanego zestawu i łączyć je w inną tablicę n elementów; następnie zapisz wynik z powrotem na dysk (najlepiej w osobnym pliku).

Źródło

2010-11-22 15:34:25

Nie ma potrzeby ładowania wszystkich danych na początku. –

Ale musisz je gdzieś przechowywać. Nawet na dysku nadal pobierają O (n^2) bajty pamięci. –

OP, mówi, że ma O (n) 'RAM', gdzie powiedział, że nie ma przestrzeni O (n^2)? jego sugestia rozwiązania problemu mówi dokładnie, że ma on przestrzeń zewnętrzną. –

Jeśli zdarzy ci się, że w pobliżu znajduje się implementacja kolejki priorytetowej niepamięci pamięci podręcznej, możesz jej użyć do osiągnięcia optymalnego czasu pracy pod względem transferu pamięci na każdym poziomie hierarchii dysku i pamięci (patrz http://courses.csail.mit.edu/6.897/spring05/lec/lec23.pdf).

W przeciwnym razie, jeśli chcesz po prostu napisać prosty kod od zera, oparta na dyskach implementacja mergesort powinna działać dobrze. Zasadniczo możesz sortować zakres tablicy, najpierw rekurencyjnie sortując połówki "lewą" i "prawą", a następnie scalając je za pomocą pamięci 2n, aby buforować rekursywnie posortowane pod-array z dysku. Dla prostej implementacji nie jest to możliwe, więc będziesz musiał przechowywać dwie kopie tablicy na dysku i przesuwać ją w obie strony.

Źródło

2010-11-22 21:06:08 jonderry

Trzymaj się, jeśli masz n^2 elementy, jak zamierzasz dokonać ostatecznego scalenia w 2n pamięci? –

Buforujesz numery z dysku. Masz dwie listy na dysku, które chcesz scalić, więc załaduj n z każdego do pamięci i scal je, zapisując wyniki scalenia na dysk. Kiedy skończy się jeden z buforów, przeładujesz go. Z technicznego punktu widzenia powinieneś również buforować podczas zapisu na dysk, więc może być konieczne odłożenie pamięci O (n) także dla bufora wyjściowego. – jonderry

Jak sortować n^2 elementy w 2n RAM

Odpowiedz

Powiązane problemy