Operacja modulo

Jak możemy zastosować operację modulo?

Zastosowanie operacji modulo

 

Wiele czynności wykonywanych podczas użytkowania systemu procesowania szkód przepięciowych i elektronicznych lub zdarzeń automatycznie w nim realizowanych powoduje utworzenie zadań dla konsultantów Mentaxu. Najprostszym przykładem jest pojawienie się w systemie nowej szkody: wtedy zadaniem konsultanta jest rozpoczęcie całego procesu jej likwidacji, zmiana statusów, przekazywanie przedmiotu do naprawy, kontakt z serwisem oraz towarzystwem ubezpieczeniowym. Na każdym etapie mogą być tworzone i przydzielane kolejne zadania, związane z wymogiem wykonania określonych czynności przez konsultanta. Z technicznego punktu widzenia ciekawy jest sposób, na podstawie którego te zadania są przydzielane. Co decyduje o tym, że dane zadanie trafi do tego, a nie innego konsultanta? 

 

Koszyki zadań

 

Każde zadanie ma swój typ, a każdy typ zadania określa koszyk, w jakim znajdują się zadania tego typu. Na przykład typem zadania jest wspomniane „Utworzenie szkody”. Innym typem jest np. „Dodana faktura” – typ zadania związany z faktem, że serwis dodał fakturę elektroniczną, którą konsultant musi zweryfikować. W zależności od typu zadania na podstawie różnych kryteriów przewidziane są 3 główne sposoby przydzielania zadania konsultantom:

  1. Przydzielenie ręczne. Na początku zadanie nie jest nikomu przydzielane – konsultanci sami mogą je przydzielić: sobie samemu lub innemu konsultantowi (jeśli mają do tego uprawnienia). 
  2. Przydzielenie automatyczne. Najczęściej wtedy zadanie jest przydzielane przez system w momencie utworzenia zadania. W systemie funkcjonują dwa główne algorytmy automatycznego przydzielania: „Automat kolejkowy” – z uwzględnieniem częstotliwości przydzielania oraz „Kolejka cykliczna” – bez uwzględniania częstotliwości przydzielania. 
  3. Przydzielenie niestandardowe – przydzielenie automatyczne, ale realizowane według bardziej skomplikowanego, dedykowanego algorytmu (tak dzieje się np. z zadaniami związanymi z wiadomościami od serwisu). 

 

Algorytmy przydzielania

 

Przyjrzyjmy się sposobowi nr 2, czyli algorytmom przydzielania automatycznego. Każdy konsultant, osobno w każdym koszyku, na którym działa, ma przypisaną wartość częstotliwości przydzielania. Określana jest ona w tym celu, aby regulować obłożenie konsultantów zadaniami, uwzględniając także ich specjalizację. Jeżeli zatem konsultant ma w danej chwili zbyt dużo zadań z danego koszyka w stosunku do liczby zadań z innego koszyka lub w porównaniu z innymi konsultantami – to sygnał, że należy mu tę częstotliwość zmniejszyć. Wydawałoby się, że zgodnie z nazwą tego parametru, im wyższa częstotliwość przydzielania przypisana konsultantowi, tym częściej będzie miał przydzielane kolejne zadania, jednak jak za chwilę zobaczymy, jest odwrotnie. Jak to wygląda w szczegółach?

 

Automat kolejkowy

 

Prześledźmy kolejne kroki podstawowego algorytmu automatycznego przydzielania, jakim jest „Automat kolejkowy”. Pierwszym z nich jest sprawdzenie, czy w danym koszyku istnieje przynajmniej 1 aktywny konsultant. Jeśli tak nie jest, zadanie nie zostanie przydzielone nikomu – wtedy można je przydzielić tylko ręcznie. 

 

Jeśli natomiast istnieją aktywni konsultanci w tym koszyku, trzeba teraz spośród nich pobrać tych, którzy mają częstotliwość przydzielania odpowiadającą wartości aktualnej kolejki. Kolejkę najłatwiej zrozumieć zatem poprzez wyjaśnienie, czym jest częstotliwość przydzielania. Częstotliwość przydzielania jest to liczba, która odpowiada na pytanie: „co którą kolejkę należy włączyć danego konsultanta w proces przydzielania zadania?”. A więc jeśli konsultant ma przypisaną częstotliwość przydzielania równą 1, to będzie uwzględniany w każdej kolejce, jeśli natomiast wartość ta będzie wynosiła 4, to konsultant będzie brany pod uwagę w co czwartej kolejce, a jeśli 6 – w co szóstej i tak dalej. A więc, wbrew  temu, co sugerowałaby nazwa, im wyższa częstotliwość przydzielania, tym rzadziej konsultant będzie miał przydzielane zadania. Dana kolejka „mieści” w sobie tych konsultantów, którzy mają częstotliwość przydzielania taką, że wartość kolejki stanowi jej wielokrotność. 

 

Kolejka będzie zatem liczbą całkowitą przypisaną do koszyka, która będzie zwiększana za każdym razem, gdy wszyscy konsultanci mający częstotliwość przydzielania odpowiadającą danej kolejce będą już mieli przydzielone zadania w tej kolejce. Spójrzmy na przykład. Załóżmy, że mamy 6 konsultantów wraz z przypisanymi im wartościami częstotliwości przydzielania:

 

Konsultant Częstotliwość przydzielania
Ania 2
Basia 3
Czarek 6
Damian 1
Ewelina 3
Franek 3

 

 

Gdy zostanie utworzone zadanie, muszą zostać pobrani ci konsultanci, których częstotliwość przydzielania dzieli wartość kolejki całkowicie, czyli bez reszty (co jest tożsame z tym, że kolejka stanowi wielokrotność częstotliwości przydzielania). Na przykład jeśli kolejka wynosiłaby 8, to pobralibyśmy tych konsultantów, których częstotliwość przydzielania wynosi 1, 2, 4 lub 8. Każda z tych liczb dzieli 8 bez reszty. 

 

Operacja modulo

 

Tutaj właśnie wkracza do akcji operacja modulo, której wynikiem jest reszta z dzielenia. Często oznacza się ją jako mod (np. 8 mod 2 = 0), ale w języku PHP znakiem tego działania matematycznego jest procent: %.

 

Na przykład:

8 % 1 = 0, bo 8:1 = 8, a reszta = 0

8 % 2 = 0, bo 8:2 = 4, a reszta = 0 

8 % 3 = 2, bo 8:3 = 2, a reszta = 2 (8 = 2 • 3 + 2)

8 % 4 = 0, bo 8:4 = 0, a reszta = 0

8 % 5 = 3, bo 8:5 = 1, a reszta = 3 (8 = 1 • 5 + 3)

 

Jeśli natomiast dzielnik jest wyższy niż dzielna (pierwszy element dzielenia), to wynikiem modulo jest dzielna, na przykład:

 

2 % 7 = 2, bo 2:7 = 0, a reszta = 2

3 % 7 = 3, bo 3:7 = 0, a reszta = 3

4 % 7 = 4, bo 4:7 = 0, a reszta = 4

 

Najbardziej powszechnym użyciem arytmetyki modularnej – bo tak nazywa się system matematyczny bazujący na operacji modulo – jest zegar. Liczymy sekundy i minuty „do 60”, a godziny „do 24”. Nie ma np. godziny 25 albo 28 – po przekroczeniu granicy 24, wskazówka odlicza „od nowa” godzinę 1, 2, itd. 

 

Kroki algorytmu

 

Na początku całej historii przydzielania kolejka wynosiła 1. Wtedy mieliśmy do czynienia właśnie z tą drugą z opisywanych wyżej sytuacji (dzielnik wyższy niż dzielna) i tylko Damian, posiadający częstotliwość równą 1 mógł zostać wzięty pod uwagę w tej kolejce (1 % 1 = 0, dla innych reszta z dzielenia przez wyższą liczbę niż 1 wyniosła 1). Ponieważ nie ma żadnych „konkurentów”, to z góry zakładamy, że tylko do niego może trafić to zadanie i tak też się dzieje. Wtedy zwiększamy kolejkę o 1.

 

Natomiast analizując następne przypadki, możemy się już domyślić, że np. dla kolejki nr 3 tylko ci konsultanci, którzy mają częstotliwość 3 będą brani pod uwagę (3 jest liczbą pierwszą). Ciekawa sytuacja będzie miała miejsce w kolejce 12, kiedy to wszyscy konsultanci zostaną pobrani, ponieważ częstotliwości wszystkich z nich dzielą 12 bez reszty. Kto w takiej sytuacji dostanie to zadanie? 

 

Otóż gdy liczba pobranych konsultantów jest większa od 1, o przydzieleniu decyduje miejsce w kolejce, którą to wartość konsultanci mają przypisaną podobnie jak częstotliwość. Podczas procesu przydzielania pobierane jest ostatnie zadanie z aktualnej kolejki (każde zadanie ma zapisaną informację o kolejce, w jakiej zostało przydzielone) i miejsce w kolejce konsultanta, któremu zostało ono przydzielone. Następnie znajdowany jest ten konsultant, który ma miejsce w kolejce wyższe o 1 od niego (oczywiście wyjątkowe sytuacje, kiedy np. w danej kolejce jeszcze nikt nie miał przydzielonego zadania, są odpowiednio obsłużone). To on właśnie dostanie to zadanie do realizacji.

 

Jeśli natomiast okaże się, że pobrana w ten sposób lista konsultantów jest pusta (dla każdego reszta z dzielenia jest różna od 0), to kolejka jest zwiększana o 1 – aż do skutku. Ten rekurencyjny algorytm nigdy się nie zapętli w nieskończoność, ponieważ na samym początku sprawdziliśmy, że istnieją konsultanci aktywni w tym koszyku – pozostaje „poczekać”, aż natrafimy wreszcie na kogoś, kto ma częstotliwość odpowiadającą danej kolejce. 

 

Cały algorytm bazuje więc na dość prostej operacji modulo i to stanowi o jej przydatności dla tego typu zastosowań. Zawsze wtedy, gdy chcemy jakieś dane przefiltrować i wykonać pewne operacje cyklicznie – tj. regularnie dla powtarzających się, podobnych pod pewnym względem elementów, niezależnie od liczby kolejno przeprowadzanych tego typu operacji, najprawdopodobniej posłużenie się tym działaniem okaże się najlepszym rozwiązaniem. 

 

Choć nie jest ono używane w drugim algorytmie automatycznego przydzielania, jakim jest „Kolejka cykliczna”, gdyż tutaj decyduje tylko miejsce w kolejce (tak jakby wszyscy mieli częstotliwość przydzielania równą 1). 

 

Operację tę możemy również zastosować wtedy, gdy chcemy mieć pewność, że nigdy nie uzyskamy wartości liczbowej wyższej niż $max. Reszta z dzielenia nigdy nie będzie równa ani większa niż dzielnik, a zatem jeśli mamy jakąś zmienną iteracyjną $i i na jej podstawie chcemy pobrać jakiś element z zakresu ograniczonego maksymalną wartością $max, to możemy skorzystać z zapisu:

 

$y = $i % $max;

 

Na przykład dla $max = 18 najwyższa wartość $y, jaką możemy uzyskać to 17. 

 

Struktury, na których stosujemy operację modulo, to przede wszystkim kolejki cykliczne (w matematyce zwane też pierścieniami, gdyż rzeczywiście przypominają pierścień – gdy przekroczymy wartość maksymalną, przechodzimy do początku). 

 

Innym, ciekawym, choć raczej teoretycznym, przykładem zastosowania może być odwzorowanie pewnej struktury danych (np. tablicy) na tę samą strukturę, ale „przesuniętą o wektor”, tzn. każdemu elementowi tej tablicy chcemy przypisać jakiś inny element tej tablicy, ale nigdy nie chcemy wyjść poza jej zakres (traktujemy ją jak kolejkę cykliczną).  

 

Na przykład mając tablicę:

4, 5, 6, 7, 8, 9

 

chcemy ją „przesunąć o wektor” wynoszący 4, czyli otrzymać tablicę:

6, 7, 8, 9, 4, 5

 

Wtedy na podstawie takiego odwzorowania liczbie 5 z pierwszej tablicy przypiszemy liczbę 7. Jak to wykonać w języku PHP?

 

Można napisać taką metodę:

 

Przy założeniu, że parametr $data zawsze będzie zawierał kolejne liczby całkowite, funkcja zawsze zwróci element z podanej tablicy – taki sam, jeżeli „wektor” (parametr $shift) = 0 lub wartość „przesuniętą” o ten wektor. 

 

Sposobność do takiego zastosowania zasad arytmetyki modularnej może się nadarzyć na przykład, gdy z jakichś powodów będziemy zmuszeni do operowania „w locie” na gotowej liście elementów, bez możliwości zapisu danych i pobierania ich z bazy. 

 

Autor: Kamil Polikowski

 


Opublikowano:

Mentax na Facebook'u