Istnieje duży plik słów, który dynamicznie się zmienia. Nieustannie dodajemy do niego kilka słów. Jak śledzisz 10 najpopularniejszych słów w każdej chwili?Wywiad z amazonkiem
Znalazłem to pytanie na blogu, ale nie mogłem zrozumieć odpowiedzi. Odpowiedź jest następująca: tabela mieszania + min-kupa
Rozumiem, dlaczego część hashtable, ale nie część min, może ktoś mi pomóc?
Jeśli jest to top 10 trending words, należy użyć max-heap wraz z hash-table.
Kiedy nowy wyraz jest dodawany do pliku następnie:
Create nowy element x z x.key=word i x.count=1.Addx z hash-table. O(1).Addx z max-heap. O(lgn).Kiedy istniejący wyraz jest dodawany do pliku następnie:
Findx w hash-table. O(1).Updatex.count na x.count++.Gdy istnieje potrzeba, aby pobrać top 10 trending words następnie:
Extract 10 razy od max-heap. 10*O(lgn)=O(10*lgn)=O(lgn).Jak widać, wszystkie potrzebne operacje są wykonywane w co najwyżej O(lgn).
chcesz użyć sterty min: gdy istniejące słowo, które nie znajduje się w pierwszej dziesiątce, staje się top 10, usunięcie min byłoby stałym czasem. – aw626
"Zaktualizuj x.count do x.count ++ w maks. Stosie" - czy nie powinno to być "O (n)"? Najpierw musisz znaleźć 'x' w' max-heap', ale nie wiesz, gdzie on jest.Kiedy go znajdziesz, inkrementacja i bulgotanie to operacja 'O (lgn)'. –
@ B-Con: Ponieważ 'max-heap' i' hash-table' wskazują na ten sam element 'x', wtedy nie ma potrzeby, aby znaleźć go ponownie w tabeli mieszania. Naprawię to, dzięki. –
Jeśli chcesz zachować tylko 10 najlepszych, użycie maksymalnej sterty to przesada. Utrzymanie 10 pozycji w posortowanej tablicy będzie prostsze i szybsze.
Do sortowania wystarczy użyć sortowania wstawiania zaczynając od dolnej części tablicy. Będziesz musiał sprawdzić, czy kandydat jest już w pierwszej dziesiątce, aktualizując swoją pozycję, jeśli jest to wymagane.
jeśli nie zatrzymasz pozostałych wpisów, żadna nowa pozycja nigdy nie dotrze do pierwszej dziesiątki. –
@KarolyHorvath: oczywiście nadal potrzebujesz tabeli mieszającej, aby policzyć liczbę trafień na wejście. Chodzi mi o to, że używanie min-sterty do zarządzania 10 najlepszymi wpisami jest przesadzone. Prosta posortowana tablica lepiej by działała, a implementacja byłaby również znacznie prostsza. W rzeczywistości, dla przyrostowo aktualizowanego top-N (i jeśli nie masz masywnych powiązań) posortowana tablica zawsze będzie działała lepiej niż min-kupa. – salva
Zazwyczaj potrzebujesz min-sterty, aby śledzić najwyższe N odpowiedzi, ponieważ na każdym etapie masz odpowiedź kandydata i chcesz wiedzieć, czy jest lepsza niż najgorsza odpowiedź w min-kupce - jeśli jest , usuń najgorszą odpowiedź górnego N z min-sterty i wstaw kandydata. Posiadanie intuicyjnego maks. Sterty bardzo ułatwia znalezienie najlepszej odpowiedzi, ale decydując o tym, czy przyjąć nową odpowiedź, nie jest to tym, czego potrzebujesz. (Pamiętajcie tylko, że po wyodrębnieniu najlepszych N odpowiedzi na końcu, wyjdą najgorsze z tych N po raz pierwszy). – mcdowella