Wymagania dotyczące pamięci dla wyboru mediany (algorytmy dwuprzebiegowe)

18

W klasycznej pracy Munro i Paterson badają problem ilości pamięci potrzebnej algorytmowi do znalezienia mediany w losowo posortowanej tablicy. W szczególności koncentrują się na następującym modelu:

wejście jest odczytywane od lewej do prawej kilka razy P.

Pokazano, że komórki pamięci są wystarczające, ale odpowiadająca dolna granica jest znana tylko dla P = 1. Nie widziałem żadnego wyniku dla P> 1. Czy ktoś jest świadomy takich dolnych granic? O(n12)P.)

Zauważ, że główna trudność polega na tym, że przy drugim przejściu dane wejściowe nie są już losowo uporządkowane.

ds.algorithms space-bounded data-streams MassimoLauria
źródło

Odpowiedzi:

14

Wypróbuj ten artykuł Chana w najnowszej wersji SODA: http://portal.acm.org/citation.cfm?id=1721842&dl=ACM .

Szybkie wyszukiwanie Google również znalazło następujący artykuł, który wydaje się być odpowiedni, ale go nie przeczytałem: http://portal.acm.org/citation.cfm?id=1374470 .

Warren Schudy
źródło
Dziękuję, druga praca wydaje się udzielać częściowej odpowiedzi na moje pytanie. Takiej odpowiedzi nie ma we wcześniejszych artykułach, o których wiedziałem.
MassimoLauria,
18

Pierwszą kartą, która potwierdziła granice więcej niż 1 przepustki, była moja praca z Jayram i Amitem z SODA'08. Jest też papier, o którym wspomniał Warren, który poprawia granice czystszym dowodem.

Krótko mówiąc, rozumiemy zależność, jeśli dopuścisz stałe przed liczbą przebiegów. Oczywiście, te stałe są w potęgie wykładniczej, więc możesz poprosić o dokładne zrozumienie. Moja główna skarga polega na tym, że model przesyłania strumieniowego w wielu kanałach nie jest tak dobrze zmotywowany.

Bardziej intrygujące pytanie brzmi, czy możemy udowodnić dolną granicę programu rozgałęziającego. Czy to możliwe, że nawet w przypadku algorytmu z ograniczoną przestrzenią, który może uzyskiwać dostęp do pamięci według własnego uznania, najlepszą strategią jest po prostu przesyłanie strumieniowe w wielu kanałach?

Odpowiedź wydaje się twierdząca i mamy częściowy postęp w kierunku jej udowodnienia.

Mihai
źródło
5
Myślę, że strumieniowanie wieloprzebiegowe jest naturalnym modelem w następujących rodzajach eksperymentów: Korzystasz z losowego próbkowania do przeprowadzania testów statystycznych (np. Testów permutacyjnych). Przeprowadzasz miliardy eksperymentów; każdy eksperyment pobiera losowe liczby z PRNG i wytwarza pewne wartości wyjściowe. Następnie chcesz obliczyć mediany, histogramy itp. Tych wartości. Nie masz skutecznego losowego dostępu do strumienia wyjściowego i nie masz pamięci do przechowywania wszystkiego. Możesz jednak ponownie odtworzyć strumień; po prostu zresetuj PRNG z tym samym ziarnem i ponownie uruchom algorytm.
Jukka Suomela
2
Wszyscy możemy się zgodzić, że najlepsze jest posiadanie górnych granic w modelu strumieniowania wieloprzebiegowego i dopasowywanie dolnych granic dla odpowiedniej rodziny programów rozgałęziających.
MassimoLauria