Autor artykułu: mgr Jerzy Wałaszek, wersja1.0
©2011 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
|
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2011 mgr
Jerzy Wałaszek
|
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.
| 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.. |
mv – wartość najczęściej powtarzającego się
elementu.
mc – liczba powtórzeń wartości mv w tablicy T.
| 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. |
| 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 |
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ć.
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.
| 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.. |
mv – wartość najczęściej powtarzającego się
elementu.
mc – liczba powtórzeń wartości mv w tablicy T.
| 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. |
| 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:
-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
| 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.. |
mv – wartość najczęściej powtarzającego się
elementu.
mc – liczba powtórzeń wartości mv w tablicy T.
| Tmin | – | wartość minimalna w T |
| Tmax | – | wartość maksymalna w T |
| i | – | indeks. i ∈C |
| C | – | tablica liczników |
| m | – | ilość licznikó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 |
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