Moda

Wstęp

Moda jest to wartość ze zbioru, która najczęściej występuje. Takich elementów może być więcej niż jeden i wtedy wszystkie takie wartości nazywa się dominantami. W tym artykule zostanie wyjaśnione jak zaimplementować algorytm do wyszukiwania dominant.

Algorytm

W celu znalezienia dominanty należy policzyć ile razy występuje, który element, a następnie sprawdzić, które pary element×liczba wystąpień ma największą liczbę wystąpień. Podczas formułowania odpowiedzi należy pamiętać, że może być kilka dominant tj. elementów, które występują najczęściej.

Przykład

Weźmy przykładowo zbiór {1, 3, 5, 2, 4, 3, 1, 5, 5}. Dla podanego zbioru liczb utwórzmy tablicę, gdzie dla każdej wartości policzymy ile razy występuje. Dane zostały zebrane w tabelce:

Z tabelki wyraźnie wynika, że najczęściej występuje wartość 5, a więc jest to dominanta tego zbioru. Jednak gdyby w zbiorze nie istniała wartość 5 to dominantami byłyby wartości 1 oraz 3.

Implementacja

Strategia

Do przechowywania par wartość oraz ilość wystąpień warto napisać własną strukturę, albo skorzystać z dwuelementowych krotek. Wszystkie takie pary powinny być odkładane na specjalną listę. Elementy na niej umieszczone powinny zostać posortowane w trakcie wstawiania - dzięki temu do wyszukania czy dana wartość została już znaleziona wystarczy logn kroków, a nie n. Jest to możliwe dzięki wykorzystaniu wyszukiwaniu binarnemu.

Na koniec pozostaje przeanalizować utworzoną listę tak, aby można było określić, które wartości są dominantami, a które nie. W tym celu zostanie utworzona pusta lista, a maksymalna ilość wystąpień ustawiona na 0. Nastepnie przeszukując po kolei pary jeśli liczba wystąpień jest taka sama jak aktualne maksimum to wartość należy dopisać, a jeśli większa to lista jest czyszczona, maksimum ustawiane na ilość wystapień danej wartości, a następnie dopisywana na listę jest aktualna wartość.

Złożoność

Złożoność pamięciowa jest liniowa O(n), a złożoność czasowa to O(n·logn). Wynika to z faktu, że dla każdego z n elementów wykonujemy wyszukiwanie binarne o złożności O(logn), a następnie wykonujemy przejście po całej tablicy o maksymalnej długości n jeśli każda wartosć występuje raz, więc O(n·logn + n) = O(n·logn).

Strategia

Przykładowo dla zbioru {1, 3, 2, 3, 2, 3, 1} zostaną otrzymane następujące pary:

Z kolei wyszukiwanie dominant odbędzie się w następujący sposób:

Na podstawie uzyskanego wyniku można stwierdzić, że istnieje tylko jedna dominanta tj. 3.

Kod źródłowy

Szukanie dominanty

Poniższa funkcja szukajDominanty() dla podanej tablicy dane zwraca listę dominant.

1. vector<int> szukajDominanty(vector<int> dane) {
2.   vector<Para> lista;
3.   lista.push_back(utworzPare(dane[0]));
4.   for (int i = 1; i < dane.size(); i++) {
5.     int poz = wyszukaj(lista, dane[i]);
6.     if (poz < lista.size() && lista[poz].wartosc == dane[i]) {
7.       lista[poz].ilosc++;
8.     } else {
9.       lista.insert(lista.begin() + poz, utworzPare(dane[i]));
10.     }
11.   }
12.   int max = 0;
13.   vector<int> wynik;
14.   for (int i = 0; i < lista.size(); i++) {
15.     if (lista[i].ilosc > max) {
16.       wynik.clear();
17.       max = lista[i].ilosc;
18.     }
19.     if (lista[i].ilosc == max)
20.       wynik.push_back(lista[i].wartosc);
21.   }
22.   lista.clear();
23.   return wynik;
24. }

(2.) Przygotuj nową listę, a następnie (3.) umieść na liście pierwszy element z listy wejściowej. Następnie (4.) dla każdego elementu: (5.) znajdź gdzie powinna znajdować się para wartości odpowiadająca elementowi. (6.) Jeśli na tej pozycji występuja para z szukaną wartością to (7.) zwiększ ilość. (8.) W przeciwnym razie (9.) dodaj nową parę na znalezionej pozycji. Dzięki temu mamy pewność, że lista jest posortowana i można korzystać z wyszukiwania binarnego. Drugi etap polega na (12.) przypisaniu, że najczęstsza wartość wystąpiła zero razy, a (13.) lista wynikowa jest pusta. (14.) Dla każdej pary: (15.) jeśli występuje częściej niż aktualne maksimum to (16.) oczyść listę i (17.) ustal nowe maksimum. Niezależnie od poprzedniego warunku (18.) sprawdź czy ilość wystąpień jest równa maksimum i jeśli tak to (18.) dopisz element na koniec. Po tej procedurze (21.) warto usunąć zbędne pary i (22.) zwrócić wynik.

Wyszukiwanie

Z kolei funkcja wyszukaj() to modyfikacja wyszukiwania binarnego. Nie zwraca ona informacji czy dana wartość wystepuje wśród par, a pozycję na której ta wartość powinna wystąpić. Dokładny opis wyszukiwania binarnego można znaleźć tutaj.

1. int wyszukaj(vector<Para> lista, int szukana) {
2.   int L = 0, P = lista.size() - 1, sr = 0;
3.   while (L <= P) {
4.     sr = (L + P) / 2;
5.     if (lista[sr].wartosc == szukana)
6.       return sr;
7.     if (lista[sr].wartosc > szukana)
8.       P = sr - 1;
9.     else
10.       L = sr + 1;
11.   }
12.   return L;
13. }

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu:

1. int main () {
2.   int n, t;
3.   cout << "Podaj ile liczb wczytac\n n = ";
4.   cin >> n;
5.   vector<int> dane;
6.   while (n--) {
7.     cin >> t;
8.     dane.push_back(t);
9.   }
10.   vector<int> wynik = szukajDominanty(dane);
11.   cout << "Znaleziono: ";
12.   for (int i = 0; i < wynik.size(); i++)
13.     cout << wynik[i] << " ";
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Wyszukiwanie dominanty można też zrealizować poprzez posortowanie danych, a następnie liniowo sprawdzeniu wszystkich elementów i wykrycia grup, które mają największą liczbę elementów. Przykładowo dla tablicy {1, 3, 2, 3, 2, 3, 1} wpierw zostanie posortowana jako {1, 1, 2, 2, 3, 3, 3}, a potem zostaną policzone kolejne grupy elementów o tym samych wartościach. Napisz funkcję szukajDominantaSort(), aby znaleźć dominantę (dominanty). Przetestuj działanie progrmau.

• Kod źródłowy Zadanie 1