Układanka o strukturze danych

Question

Napotkałem to pytanie puzzle [related to data structure] w konkursie kodowania.

Istnieje planeta drzew (prawdziwe drzewa, a nie struktura danych drzewa !!). Ma miliardy, a nawet tryliony drzew. Król nakazuje znaleźć medianę wieku (w latach i liczbach całkowitych) wszystkich drzew, używając na przykład datowania węgla. (Method does not matter.) Uwaga: Mediana jest "średnią liczbą" w posortowanej liście liczb.

Ograniczenia:
1. Najstarsze drzewo jest znany 2000 lat.
Mają jedną maszynę, która może przechowywać liczby całkowite w zakresie od -infinity do + nieskończoności.
3. Ale liczba takich liczb całkowitych, które mogą być przechowywane w pamięci na raz, wynosi 1 milion.

, więc po zapisaniu 1 miliona liczb całkowitych do zapisania następnego należy usunąć już zapisany.
Więc jakoś muszą śledzić medianę, kiedy liczą wieki drzew.
Jak mogą to zrobić?

Moje podejście
Zastosowanie wariant zewnętrznej rodzaju sortowania wieków w kawałkach & zapisać je w pliku.
Zastosuj k-way merging [dla porcji].
Problem z powyższym podejściem polega na tym, że potrzebuje on dwóch skanów pliku.

mogę myśleć innym podejściu który wykorzystuje informacje The oldest tree is known to be 2000 years old.
nie możemy wziąć count array [as range of ages of tree is fixed]?

Chcę wiedzieć, czy istnieje lepsze podejście?
Czy istnieje dowolny sposób, w którym nie trzeba przechowywać dane w pliku? [where only main memory is sufficient?]

Answer 1

Można to zrobić poprzez przechowywanie zaledwie 2001 całkowitymi. Utwórz tablicę różnych możliwych grup wiekowych

ages[2001] // [0..2000] 

kiedy można liczyć na drzewie

ages[thisAge]++ 

Wtedy obliczanie mediany jest trywialne. Wygląda na to, że trafiłeś w to rozwiązanie w drugim podejściu, o którym wspomniałeś, ale potem mówisz, że Chciałbym wiedzieć, czy istnieje lepsze podejście?

Czy istnieje dowolny sposób, w którym nie trzeba przechowywać dane w plik? [Gdzie tylko główną pamięć jest wystarczająca?]

Nie undertstand dlaczego pytasz czy tam istnieje jakakolwiek metoda, w której pamięć główna jest wystarczająca. Czy tablica liczb całkowitych 2001 nie pasuje do pamięci głównej?

Korzystając z powyższego podejścia, można wypełnić tablicę zliczeń, a następnie obliczyć medianę, powtarzając liczbę, zachowując sumę całkowitą. Kiedy twoja suma osiąga połowę całkowitej liczby drzew, masz medianę. Wymaga to zliczenia jednego przejścia przez wszystkie drzewa oraz przejścia przez część tablicy liczników o numerze < = 2001. Więc to jest O (n). Zamiast tego można śledzić medianę z tą tablicą, ale nie poprawiłoby to rozwiązania.

Answer 2

Zalecane podejście (tablica z 2001 roku) to O (n), z jedną szybką operacją na drzewo, więc jest to optymalne.

Cóż, prawie optymalna. W pewnym momencie liczenia liczba pozostałych drzew będzie niewystarczająca do zmiany wyniku. Na przykład, jeśli policzę połowę + 1 drzew, a wszystkie mają dokładnie 100 lat, to mam odpowiedź: 100 lat.

Ale jeśli drzewa są dobrze rozrzucone z wiekiem, liczba wymaganych drzew będzie zbliżona do liczby całkowitej.