Częstotliwość wyrazów z uporządkowaniem w złożoności O (n)

11

Podczas wywiadu na stanowisko programisty Java zapytano mnie:

Napisz funkcję, która przyjmuje dwa parametry:

  1. ciąg znaków reprezentujący dokument tekstowy i
  2. liczba całkowita podająca liczbę elementów do zwrócenia.

Zaimplementuj funkcję tak, aby zwracała listę ciągów uporządkowanych według częstotliwości słów, najczęściej występujących jako pierwsze słowo. Twoje rozwiązanie powinno działać w czasie gdzie to liczba znaków w dokumencie.O(n)n

Oto, na co odpowiedziałem (w pseudokodzie), nie jest to czas a raczej czas powodu tego rodzaju. Nie mogę wymyślić, jak to zrobić czas. O(n)O(nlogn)O(n)

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

Czy ktoś wie lub może ktoś mi podpowiedzieć?

użytkownik2712937
źródło
1
Użyj tabeli skrótów.
Yuval Filmus
Korzystanie z tablicy skrótów nie rozwiązuje problemu. Ponadto hashtable to starsza wersja Java.
user2712937
Tabele skrótów są zwykle sposobem na zmniejszenie złożoności z do . Nawet jeśli są to starsze wersje Java, cokolwiek to znaczy. Nie sprawdziłem tego konkretnego przypadku, więc możesz mieć rację. O(nlogn)O(n)
Yuval Filmus
@YuvalFilmus. Dzięki, ale tabela skrótów jest prawie taka sama jak mapa skrótów, której już używam (główna różnica między strukturą danych 2 to synchronizacja, która nie ma tutaj zastosowania). Mój log (n) pochodzi z sortowania wartości na mapie mieszającej.
user2712937
3
Nawiasem mówiąc, ta strona koncentruje się na pojęciach i algorytmach, a nie na kodzie. Dlatego zwykle prosimy o usunięcie kodu Java i podanie pojęciowego opisu twojego podejścia (w razie potrzeby wraz ze zwięzłym pseudokodem wysokiego poziomu). Ponadto na tej stronie istotne jest pytanie, jakich struktur danych i algorytmów użyć; konkretny interfejs API języka Java jest nie na temat dla tej witryny (ale możesz o to zapytać na StackOverflow) i podobnie, czy Hashtablestarsza wersja Java jest naprawdę nieistotna dla celów tej witryny.
DW

Odpowiedzi:

10

Proponuję wariant liczenia dystrybucji:

  1. Przeczytaj tekst i wstaw wszystkie napotkane słowa do trie , zachowując w każdym węźle liczbę, jak często występowało słowo reprezentowane przez ten węzeł. Dodatkowo śledź najwyższą liczbę słów do powiedzenia maxWordCound. -O(n)
  2. Zainicjuj tablicę rozmiarów maxWordCount. Typ wpisu to listy ciągów. -O(n), ponieważ liczba nie może być wyższa.
  3. Przejdź przez trie i dla każdego węzła dodaj odpowiedni ciąg do wpisu tablicy wskazanego przez liczbę. -O(n), ponieważ całkowita długość ciągów jest ograniczona przez n.
  4. Przejdź przez tablicę w kolejności malejącej i wyślij żądaną liczbę łańcuchów. -O(n), ponieważ jest to związane zarówno z wielkością, jak i ilością danych w tablicy.

Prawdopodobnie możesz zastąpić trie innymi strukturami danych w pierwszej fazie.

FrankW
źródło
+1, chociaż nie jestem tego pewien. Jest to O (n), ponieważ liczba słów do zwrócenia jest ograniczona przez n, liczbę znaków, ale czy o to pyta pytanie? Czy wynik niezależny od liczby zwracanych słów?
Nikos M.
@NikosM. To jest ;nto ogólna najgorsza górna granica liczby zwracanych słów, niepotrzebne założenia.
Raphael
@Raphael, tak, poprawne, myślę o tym, ponieważ zostało zadane w wywiadzie, możliwe sztuczki w pytaniu ..
Nikos M.
Zastanawiam się, czy istnieje efektywny przestrzennie algorytm liniowego czasu.
saadtaame
3
@ saadtaame, tak, to interesujące pytanie. Może warto opublikować osobno jako osobne pytanie. To nie tylko oszczędność miejsca; rozwiązanie trie jest również intensywnie wskaźnikowe, co może spowolnić w praktyce (biorąc pod uwagę, jak hierarchia pamięci działa na prawdziwych maszynach). „Wydajność” różni się od najgorszego przypadku. Nie jest niczym niezwykłym w przypadku czyszczeniaO(nlgn) algorytm czasowy pokonujący wskaźnik intensywnie O(n)algorytm czasowy, więc to pytanie wydaje się już wykluczać niektóre potencjalne algorytmy, które mogą być lepszym wyborem w praktyce.
DW
3

Zliczanie liczby wystąpień to O (n), więc sztuczka polega na znalezieniu tylko największej liczby wystąpień.

Kupa jest powszechnym sposobem agregacji najwyższych wartości k, chociaż można użyć innych metod (patrz https://en.wikipedia.org/wiki/Partial_sorting ).

Zakładając, że k jest drugim parametrem powyżej i że jest stałą w opisie problemu (wydaje się, że tak):

  1. Zbuduj zestaw słów z liczbą wystąpień w każdym węźle.
  2. Zainicjuj stertę wielkości k.
  3. Przejdź przez trie i min-sondę / włóż każdą parę (liść, liczba wystąpień) do sterty o najwyższym k.
  4. Wypisuj górne k liści i się liczy (jest to w rzeczywistości rodzaj bólu, ponieważ potrzebujesz wskaźników nadrzędnych, aby mapować każdy liść z powrotem na słowo).

Ponieważ rozmiar sterty jest stały, operacje sterty są O (1), więc krok 3 to O (n).

Stertę można również utrzymywać dynamicznie podczas budowania trie.

KWillets
źródło
2

Twój algorytm nie działa nawet w czasie O(nlogn); wstawianieΘ(n) rzeczy w hashtable kosztują czas Ω(n2)) już (najgorszy przypadek).


To, co następuje, jest złe ; Na razie zostawiam go tutaj w celach ilustracyjnych.

Poniższy algorytm działa w najgorszym przypadku O(n) (zakładając alfabet Σ o stałym rozmiarze), n liczba znaków w tekście.

  1. Skonstruuj drzewo sufiksów tekstu, np. Za pomocą algorytmu Ukkonen .

    Jeśli konstrukcja jeszcze tego nie robi, dodaj liczbę dostępnych liści do każdego (wewnętrznego) węzła.

  2. Przejdź przez drzewo od korzenia i odetnij wszystkie gałęzie na pierwszej (białej) przestrzeni.

  3. Przejdź przez drzewo i posortuj listę dzieci każdego węzła według liczby liści.

  4. Wydajność drzewa (liście od lewej do prawej) jest teraz listą wszystkich słów posortowanych według częstotliwości.

Jeśli chodzi o środowisko wykonawcze:

  1. Algorytm Ukkonena (w ulepszonej formie) działa w czasie O(n); utrzymywanie liczby liści nie zwiększaΘ-koszt algorytmu.
  2. Musimy przejść jeden węzeł na znak każdego słowa występującego w tekście. Ponieważ są co najwyżejn różne pary słów i znaków, które odwiedzamy co najwyżej n węzły
  3. Odwiedzamy co najwyżej n węzły (por. 2) i spędzać czas O(|Σ|log|Σ|)=O(1) na węzeł.
  4. Możemy uzyskać wydajność (która oczywiście ma rozmiar O(n)) przez proste przejście w czasie O(n) (por. 2).

Bardziej precyzyjne granice można uzyskać przez parametryzowanie środowiska wykonawczego liczbą różnych słów; jeśli jest ich mało, drzewo jest małe po 2.

Raphael
źródło
Algorytm jest niepoprawny (nie sortuje). Nie jestem już pewien, czy czas liniowy jest w ogóle możliwy.
Raphael
1

Użyj tabeli skrótów (np. HashMap), Aby zebrać wszystkie słowa i ich częstotliwości. Następnie użyj sortowania zliczającego, aby posortować słowa w kolejności malejącej częstotliwości. Ponieważ wszystkie częstotliwości są liczbami całkowitymi w zakresie1 ..n, sortowanie według liczenia trwa O(n)czas. Całkowity oczekiwany czas działania wynosiO(n), co jest więcej niż prawdopodobne dla wszystkich praktycznych celów (chyba że ankieter wspomniał o czymś, co zostało pominięte w twoim pytaniu). Pamiętaj, aby wspomnieć, że jest to oczekiwany czas działania, a nie najgorszy czas działania.

To może nie być odpowiedź, której nauczyciel szukałby w klasie algorytmów, ponieważ jest to oczekiwane O(n) czas pracy zamiast O(n)najgorszy czas działania. Jeśli chcesz zdobyć dodatkowe punkty w pytaniu na rozmowę kwalifikacyjną, możesz od czasu do czasu wspomnieć odręcznie, że oczywiście jest to oczekiwany czas trwania, ale można to również zrobić wO(n) najgorszy czas działania, zastępując tabelę skrótów bardziej wyrafinowaną strukturą danych - i chętnie opracujesz sposób wyboru algorytmów w takiej sytuacji.

Lub, jeśli chcesz zagrać nieco bezpieczniej, zanim udzielisz odpowiedzi, najpierw zapytaj: „czy zależy Ci na różnicy między oczekiwanymi O(n) czas pracy i najgorszy przypadek O(n)czas trwania? ”. Następnie odpowiednio dostosuj swoją odpowiedź. Przygotuj się na to, by osoba przeprowadzająca wywiad zapytała cię, jak wybierzesz w praktyce. (Jeśli tak, zdobądź punkty!

DW
źródło
Przechowywanie Θ(n) rzeczy w hashtable bierze Ω(n2))czas już w najgorszym przypadku.
Raphael
Nie mogę wypowiadać się za ankieterami, ale waham się wykorzystać ich niechlujstwa jako usprawiedliwienie dla tego samego. Ponadto, ta strona dotyczy nauki (jak sam skomentowałeś powyżej), a nie ręcznych machań „jak zarabiać wcześniej” sztuczki programistyczne.
Raphael
Tak długo, jak to zrozumienie jest jawne, nic mi nie jest. Widziałem tu zbyt wiele pytań, które były oparte na zamieszaniu, ponieważ niektóre ukryte „zrozumienie” promowało złe idee.
Raphael
0

Rozwiązanie oparte na haszcie

Nie jestem pewien, dlaczego hashtable sprawia, że ​​złożoność Ω(n2)) gdyby nto liczba znaków (nie słów).

Jeśli wykonujesz iterację po każdym znaku w dokumencie i podczas iteracji, oblicz kod skrótu tego słowa, przejdziesz npostacie. Oznacza to, że zaraz po napotkaniu litery zaczyna się słowo, więc zacznij obliczać skrót aż do końca słowa (istnieją specjalne przypadki interpunkcji, ale nie mają one wpływu na złożoność). Dla każdego słowa, po obliczeniu skrótu, dodaj je do tablicy skrótów. Ma to na celu uniknięcie dwukrotnego przejścia do każdego słowa, tzn. Najpierw iterację dokumentu w celu znalezienia słów, a następnie wstawienie ich do tablicy haszującej, chociaż w takim przypadku złożoność może być równieżΩ(n).

Zderzenia w tablicy hashującej z pewnością stanowią problem, a w zależności od tego, jak duży był oryginalny hashtable i jak dobry jest algorytm hashujący, można zbliżyć się do O(1) do wstawiania i liczenia, a tym samym O(n)dla algorytmu, choć kosztem pamięci. Nadal jednak nie potrafię docenić, jak najgorszy przypadek można stwierdzićO(n2)) gdyby n to liczba znaków.

Zakłada się, że algorytm mieszający jest liniowy w czasie w stosunku do liczby znaków.

Rozwiązanie oparte na sortowaniu Radix

Alternatywnie, zakładając, że angielski, ponieważ długość słów jest dobrze znana, zamiast tego utworzę siatkę i zastosuję sortowanie radix, które jest O(kN.) gdzie k będzie maksymalną długością słowa w języku angielskim, oraz N.to łączna liczba słów. Danyn to liczba znaków w dokumencie, oraz k jest stałą, asymptotycznie to kwoty O(n).

Teraz policz częstotliwość każdego słowa. Ponieważ słowa są posortowane, będziemy porównywać każde słowo z poprzednim słowem, aby sprawdzić, czy jest to to samo, czy inne. Jeśli jest taki sam, usuwamy słowo i dodajemy liczbę do poprzedniego. Jeśli jest inny, po prostu policz 1 i przejdź dalej. To wymaga2)n porównania gdzie n to liczba znaków, a zatem O(n) w złożoności jako całości.

Kilka najdłuższych słów w języku angielskim jest absurdalnie długie , ale potem można ograniczyć długość słowa do rozsądnej liczby (np. 30 lub mniejszej) i obciąć słowa, przyjmując margines błędu, który może z tym wynikać.

Omer Iqbal
źródło
(1) Ponieważ w większości tekstów maksymalna długość słów jest ograniczona stałą, liczba słów wynosi Θ(n)także. (2) W zależności od funkcji skrótu obliczanie skrótu w locie podczas czytania słowa może być niemożliwe. (3) W najgorszym przypadku wszystkie słowa mają skrót do tego samego miejsca w tabeli, co powoduje wstawianie i wyszukiwanieΘ(n).
FrankW,
Cześć FrankW. (2) Twierdzę, że możemy wybrać funkcję (tj. Kroczący skrót), którą możemy obliczyć w locie. Nawet jeśli nie, ogólna złożoność nie zmienia się, dopóki hashowanie jest czasem liniowym, ponieważ byłoby czytanie i hashowanieO(n+n)operacje. (3) Oczywiście, ale to zależy od wyboru algorytmu ponownie. Istnieje wiele algorytmów, które działają znacznie lepiej, jeśli słowa są różne. Dla tego samego słowa wystarczy zwiększyć liczbę pojedynczych wpisów. Analogicznie, kiedy muszę wybrać algorytm sortowania, najgorszy przypadek może byćO(n2))ale zazwyczaj wybieram lepiej :-)
Omer Iqbal,
(3) Bez względu na wybraną funkcję skrótu, mogę wymyślić dane wejściowe, w których ta funkcja ulega pogorszeniu. A wybranie funkcji skrótu po znajomości danych wejściowych zwykle nie jest opcją. (I pamiętaj, że komentarz, do którego prawdopodobnie
zwracałeś się,
Dlaczego do tego prowadzi tablica skrótów? O(n2))w najgorszym przypadku złożoność? Jest tak, ponieważ w zasadzie najgorszy czas działania tablicy mieszającej jest bardzo zły. W praktyce wydaje się, że ten najgorszy przypadek prawie nigdy się nie wydarzy (szczególnie jeśli poprawnie wybierzesz funkcję skrótu, z randomizacją i innymi technikami), a nawet możesz udowodnić twierdzenia, aby uzasadnić, dlaczego tak jest, ale jeśli chodzi o asymptotyczną złożoność , praktyczne względy tego typu prawdopodobnie wychodzą z okna (a przynajmniej taki argument można usłyszeć).
DW
Zwykłe wstawki tabel skrótów są O(n2))ponieważ kolizja wymaga umieszczenia przedmiotu w innym miejscu. W tym przypadku nie musimy wstawiać duplikatów. 1) Powtarza się to samo słowo: wtedy liczba jest większa, z pewnością tak będzieO(1)plus czas mieszania. 2) Różne słowa to samo hash: tutaj pojawia się pytanie, jak dobry / zły jest hash i czy rozmiar stołu jest po prostu zbyt mały. Zgadzam się, że toΩ(1), ale w zależności od wyborów stwierdziłem również, że „można podejść bliskoO(1) do wstawiania i liczenia ”. Moglibyśmy przedyskutować, jaki rozmiar tabeli i funkcje mogą nas zbliżyć O(1).
Omer Iqbal,