Wyszukiwanie dominanty zbioru

Problem wyszukiwania najczęstszej wartości (ang. searching for the most frequent value), czyli tzw. dominanty zbioru, możemy rozwiązać na kilka różnych sposobów. Pierwszym, najprostszym podejściem jest metoda bezpośrednia - naiwna:

 

Przeglądamy kolejne elementy zbioru i zliczamy liczbę wystąpień ich wartości w zbiorze. Można to robić tak - zapamiętujemy i-ty element i ustawiamy licznik jego wystąpień na 0. Następnie przeglądamy cały zbiór i, jeśli trafimy na element o takiej samej wartości, to licznik zwiększamy o 1. Po wykonaniu tej operacji porównujemy zawartość licznika z tymczasową maksymalną liczbą wystąpień (na początku algorytmu jest ona ustawiana na 0). Jeśli stan licznika jest większy, to zapamiętujemy go w tymczasowej maksymalnej liczbie wystąpień oraz zapamiętujemy wyszukiwaną wartość elementu. Gdy przeglądniemy w ten sposób i zliczymy wystąpienia wartości wszystkich elementów w zbiorze T, to otrzymamy element powtarzający się najczęściej oraz ilość tych powtórzeń.

Klasa złożoności obliczeniowej tak zdefiniowanego algorytmu jest równa O(n2). Jeśli elementów jest niewiele (do około 5000) i szybkość działania nie gra istotnej roli, to rozwiązanie naiwne jest do przyjęcia.

 

Algorytm znajdowania najczęstszej wartości - wersja 1

Wejście
n  –  liczba elementów w tablicy T, n  ∈N
T  – tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n  - 1..
Wyjście:

mv  – wartość najczęściej powtarzającego się elementu.
mc  – liczba powtórzeń wartości mv  w tablicy T.

Zmienne pomocnicze
i, j  –  przebiega przez kolejne indeksy elementów T. i,j  ∈C
c  – licznik wystąpień wartości elementu, c  ∈C
v  – wartość elementu, której liczbę wystąpień w T  zliczamy.
Lista kroków:
K01: mc  ← 0 ; zerujemy maksymalną liczbę wystąpień
K02: Dla i  = 0,1,...,n-1: wykonuj K03...K06 ; przeglądanie rozpoczynamy od pierwszego elementu tablicy
K03:     v  ← T[i] ; zapamiętujemy poszukiwaną wartość elementu
K04:     c  ← 0 ; zerujemy jej licznik wystąpień
K05:     Dla j  = 0,1,..., n-1; wykonuj:
        Jeśli
T[j] = v, to c  ← c  + 1
; zliczamy wystąpienia w
K06:     Jeśli c  > mc, to
       
mc  ← c
        mv
  ← v
; sprawdzamy, czy w jest tymczasowo najczęstsze
; jeśli tak, zapamiętujemy liczbę wystąpień
; oraz wartość w
K07: Zakończ  

 

Przykładowe dane dla programu

Pierwsza liczba określa liczbę n  elementów w zbiorze. Następne n  liczb to elementy zbioru.

510
-463 -926 603 -901 826 879 376 -264 -189 10 -582 447 -664 547 702
453 -401 -398 10 -907 177 256 105 429 -63 995 -437 638 10 16
-16 320 40 141 -523 -284 138 405 17 -318 257 543 -651 -378 -278
9 27 -805 962 10 390 387 382 -210 32 -64 128 10 150 200
-4 12 32 530 -35 125 450 41 316 -301 -15 246 -849 -844 -165
27 -959 14 21 8 876 539 948 -662 5 13 32 254 577 888
-452 715 10 81 -725 359 361 381 -263 793 -144 -412 137 -119 -76
496 -189 467 149 -377 714 -273 443 490 -81 976 255 180 71 703
-620 161 978 -849 678 964 935 -188 602 -63 659 111 182 245 712
31 9 -8 603 178 -832 -743 -916 -341 87 65 -646 -707 830 612
-63 877 495 149 -290 2 698 166 -227 -400 -476 941 786 129 71
919 820 502 -28 481 943 815 -70 415 413 -484 1 329 250 78
915 -466 401 641 -802 543 10 -766 934 10 -786 10 951 768 886
231 762 74 -269 -508 10 134 -328 371 937 531 -756 470 -464 -488
-926 25 502 261 -339 115 67 -962 10 68 -882 863 -996 -791 924
742 -13 370 448 183 10 -147 41 -546 768 318 120 -522 466 628
756 968 58 358 -592 421 638 -978 980 988 444 -85 118 831 48
-858 -754 281 344 210 703 -84 -885 844 685 148 389 927 84 956
103 -310 -782 175 614 523 496 -897 10 399 924 -896 539 328 995
685 -336 548 961 15 175 982 -120 300 100 583 228 -588 672 950
-68 232 659 587 -909 967 218 -608 -838 779 343 -873 980 478 572
950 -944 395 754 10 994 26 -689 399 342 3 4 5 982 730
985 780 160 -816 933 628 433 -414 845 -646 322 450 716 849 619
-669 -855 278 173 687 471 304 460 377 -424 10 7 -20 130 721
883 654 47 145 224 771 927 10 579 38 361 773 661 -662 155
335 -9 159 283 -49 971 963 -318 913 431 811 266 -374 861 284
-232 672 564 -888 932 484 973 226 143 344 962 110 444 532 646
-16 3 29 14 83 -874 871 401 -381 473 -538 908 58 760 20
969 120 160 40 -584 -176 598 110 358 443 822 403 10 -46 199
-643 -614 574 5 8 13 4 -8 3 143 703 7 -242 50 61
34 487 526 290 818 219 968 710 -894 510 180 -447 708 -226 -296
-782 314 932 211 169 67 824 10 90 508 138 350 -824 799 882
-713 -212 335 -223 990 -735 502 743 -363 434 -484 10 -782 166 512
565 -654 934 364 397 168 4 5 6 603 524 183 303 10 399

 

Podany powyżej algorytm jest bardzo prymitywny i wykonuje wiele niepotrzebnych działań. Postarajmy się je wyeliminować.

  1. Ze zbioru bierzemy KAŻDY element T[i] i zliczamy wystąpienia jego wartości dla CAŁEGO zbioru T. W ten sposób najczęstsza wartość mv  zostanie zliczona mc2 razy. Zatem pierwsze ulepszenie będzie polegało na tym, iż pobrany element w  zbioru zliczamy tylko wtedy, gdy jest on różny od mv. Wynika z tego, iż na początku pracy algorytmu do mv  musimy wpisać wartość różną od T[0] (dlaczego?).
  2. Każdy element T[i] zliczamy w całym zbiorze. Tymczasem, jeśli wartość i-tego elementu wystąpiła wcześniej w zbiorze, to jest już zliczona. Jeśli nie wystąpiła wcześniej, to nie ma sensu jej tam szukać, nieprawdaż? W obu przypadkach wystarczy, jeśli zliczanie rozpoczniemy od pozycji i  + 1 do końca zbioru. Elementy zliczone po prostu zliczymy ponownie, lecz w mniejszym zakresie. Elementy nowe zliczymy poprawnie, od miejsca ich pierwszego wystąpienia.
  3. Jeśli w trakcie działania algorytmu w mc  mamy chwilową maksymalną liczbę wystąpień pewnej wartości mv, to zliczanie nowych elementów możemy przerwać po osiągnięciu pozycji n  - mc. Jeśli nowy element występuje na tej lub dalszej pozycji w zbiorze T, to liczba wystąpień jego wartości nie będzie już większa od mc, gdyż braknie takich elementów.

Oczywiście, powyższe ulepszenia nie zmienią klasy złożoności obliczeniowej – otrzymamy jedynie nieco szybszy algorytm klasy O(n2), który bardziej efektywnie rozwiązuje nasz problem.

 

Algorytm znajdowania najczęstszej wartości – wersja 2

Wejście
n      liczba elementów w tablicy T, n  ∈N
T  – tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n  - 1..
Wyjście:

mv  – wartość najczęściej powtarzającego się elementu.
mc – liczba powtórzeń wartości mv w tablicy T.

Zmienne pomocnicze
i, j  –  przebiega przez kolejne indeksy elementów T. i,j  ∈C
c  – licznik wystąpień wartości elementu, c  ∈C
v  – wartość elementu, której liczbę wystąpień w T  zliczamy.
Lista kroków:
K01: mc  ← 0 ; zerujemy maksymalną liczbę wystąpień
K02: mv T[0] - 1 ; zapewniamy, iż mv zawiera wartość różną od T[0]
K03: Dla i  = 0,1,...,n-1: wykonuj K04...K08 ; przeglądanie rozpoczynamy od pierwszego elementu tablicy
K04:     Jeśli T[i] = mv, to następny obieg pętli ; elementu najczęstszego nie zliczamy ponownie
K05:     v  ← T[i] ; zapamiętujemy poszukiwaną wartość elementu
K06:     c  ← 1 ; ustawiamy jej licznik wystąpień
K07:     Dla j  = i+1, i+2,..., n-1: wykonuj:
        Jeśli T[j] = v, to c  ← c  + 1
; zliczanie rozpoczynamy od pozycji następnej
K08:     Jeśli c  > mc, to
   
    mc  ← c
        mv
  ← v
; sprawdzamy, czy w jest tymczasowo najczęstsze
; jeśli tak, to zapamiętujemy liczbę wystąpień
; oraz najczęstszą wartość
K09: Zakończ  

 

Aby zmienić klasę złożoności z kwadratowej na liniową, musimy zmienić podejście do problemu. Postąpimy następująco:

 

Utworzymy tablicę liczników. Indeksy elementów tej tablicy będą odpowiadały wartością elementów ze zbioru. Całą tablicę liczników wyzerujemy. Następnie przeglądniemy zbiór i dla każdego napotkanego w nim elementu zwiększamy w tablicy liczników element o indeksie równym wartości tego elementu. Na koniec wyszukamy w tablicy liczników największy licznik, a wartość jego indeksu jest wartością najczęstszego elementu.

 

Algorytm ten się sprawdzi dla elementów całkowitych dodatnich. Jeśli elementy mogą również być ujemne, to należy przeliczać elementy zbioru T na odpowiednie indeksy tablicy liczników. W tym celu będziemy potrzebowali wartości minimalnej i maksymalnej z T, aby odpowiednio utworzyć tablicę liczników.

Tablica liczników ma rozmiar:  Tmax - Tmin + 1

Element o wartości v  ma indeks: v - Tmin

Indeks i  odnosi się do elementu o wartości: i + Tmin.

Przykład:

Tablica T zawiera elementy od -3 do 6. Potrzebujemy 6 + 3 + 1 = 10 liczników dla elementów:

-3  -2  -1   0   1   2   3   4   5   6 → wartości elementów
 0   1   2   3   4   5   6   7   8   9 → indeksy liczników

 

Algorytm znajdowania najczęstszej wartości – wersja 3

Wejście
n      liczba elementów w tablicy T, n  ∈N
T  – tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n  - 1..
Wyjście:

mv  – wartość najczęściej powtarzającego się elementu.
mc – liczba powtórzeń wartości mv w tablicy T.

Zmienne pomocnicze
Tmin   wartość minimalna w T
Tmax   wartość maksymalna w T
i  –  indeks. i  ∈C
C  – tablica liczników
m  – ilość liczników
Lista kroków:
K01: Wyszukaj w T  wartości Tmin  i Tmax  
K02: m  ← Tmax  - Tmin  + 1 ; wyznaczamy liczbę potrzebnych liczników
K03: Utwórz tablicę C  o rozmiarze m  
K04: Wyzeruj tablicę C  
K05: Dla i  = 0,1,...,n-1: wykonuj
    C[T[i] - Tmin] ← C[T[i] - Tmin] + 1
; przeglądamy kolejne elementy zbioru i zwiększamy o 1
; ich liczniki w tablicy C
K06: mc  ← C[0]  
K07: Dla i  = 1,2,...,m-1: wykonuj
    Jeśli C[i] > mc, to
        mc  ← C[i]
        mv  ← i  + Tmin
; wyszukujemy największy licznik
K08: Usuń tablicę C  
K09: Zakończ  

 

Tak zdefiniowany algorytm posiada klasę złożoności obliczeniowej O(n + m), gdzie n oznacza liczbę elementów, a m liczbę ich wartości. Zwróć jednakże uwagę, iż zysk na prędkości został okupiony większym zapotrzebowaniem na pamięć – tablica liczników rezerwuje dodatkowe m lokacji pamięci.

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe