Witaj Gościu Zaloguj się lub zarejestruj się.
Zaloguj

Losowanie niepowtarzalnych elementów w PHP - metoda właściwa

Losowanie niepowtarzalnych elementów w PHP - metoda właściwa

Wielokrotnie podczas wykonywania skryptów w języku PHP mamy do czynienia z losowaniem liczb, wyrazów czy innych elementów. Wiele programistów próbuje wymyślić koło na nowo.

Nie byłoby w tym nic złego, gdyby nie fakt, że to prowadzi do bardzo małej wydajności przy aplikacjach. Im większa liczba elementów tym gorzej. Jak napisać skrypt, który losuje niepowtarzalne elementy i jest jednocześnie wydajny?

Metoda większości programistów

Aż trudno uwierzyć jak wiele programistów bez chwili zastanowienia bierze się do pisania skryptów losujących niepowtarzalnych elementów bez najmniejszego namysłu. To niestety szczera prawda, ale jeszcze większe zło wykonują Ci, którzy piszą blogi lub udostępniają swoje skrypty publice. Przykładów jest bardzo wiele - wystarczy poszukać i znaleźć mnóstwo skryptów, które wyglądają w następujący sposób (losowane są liczby, jednak nie ma problemu aby losowane były wyrazy, obiekty czy cokolwiek innego):

Powyższy skrypt wykonuje swoje zadanie. Losuje 50 różnych liczb z zakresu od 0 do 100. Wynikiem jego działania jest tablica wylosowane_elementy, w której znajdują się wylosowane liczby. Robi to dobrze, jednak maksymalnie niewydajnie


Lepsze rozwiązanie

Lepsze, żeby nie powiedzieć jedynie słuszne. Za pomocą poniższych, dużo mniej zajmujących a jednocześnie czytelniejszych linijek wygenerujemy taką samą tablicę z losowymi elementami. Warto tutaj zaznaczyć, ten skrypt ingeruje w tablicę z danymi. Jeżeli nie jest to pożądany przez nas efekt, to wynik funckji shuffle musimy przyporządkować do nowej tablicy.

Testy wydajności

Czym byłyby moje słowa bez potwierdzenia w rzeczywistych wynikach wydajności. Oto jak przedstawiają się wyniki w zależności od liczba iteracji. Liczba iteracji oznacza ilość uruchomień części kodu losującej. Wyniki są średnią z 10 wykonań operacji.

jeżeli już testujemy wydajność, to trzeba wziąć pod uwagę 3 warianty danych dla skryptów - najgorszy, średni oraz najlepszy. Algorytm powinien być przecież dostosowany do danych wejściowych, o ile takie posiadamy. W tym przypadku jedynie skrypt 1 jest podatny na różne dane. Skrypt drugi zawsze wykonuje się dokładnie tak samo, niezależnie od tego, ile liczb chcemy wylosować. Tak więc dla wydajnego skryptu został przeprowadzony test natomiast dla pierwszego 3 (WC - worst case, AC - average case oraz BC - best case). WC to wylosowanie 100 różnych liczb ze 100 możliwych, AC to 50 ze 100 a BC to 1 ze 100.

Testy zostały przeprowadzone na lokalnym komputerze w terminalu w zupełnie czystym środowisku, by nic nie mogło wpływać na wyniki. Wyniki testów są zależne od konfiguracji sprzętowej oraz zmiennych środowiskowych.

Liczba iteracji Skrypt 1 BC Skrypt 1 AC Skrypt 1 WC Skrypt 2
1 0.166 0.160 0.166 0.160
10 0.164 0.160 0.170 0.161
100 0.165 0.167 0.219 0.161
1000 0.165 0.225 0.685 0.167
10000 0.173 0.780 5.340 0.233
100000 0.239 6.424 52.435 0.887
1000000 0.912 64.155 522.219 7.451

Wnioski są proste. Skrypt drugi jest wydajniejszy w zdecydowanej większości przypadków. Biorą pod uwagę fakt, ze BC jest bez sensu, bo przecież do losowania jednej liczby używamy zwyczajnie random a nie tak zawiłego skryptu, to oczywiste jest, że skrypt 2 jest lepszy. Nie dość, że w większości przypadków jest wydajniejszy, to jeszcze jest bardziej czytelny i prostszy.

W powyższych skryptach został pominięty test losowości, gdyż w tym przypadku nie ma to znaczenia. W obu przypadkach losować liczb jest na tyle dobra, że powinna spełniać wymagania większości osób.

Należy tutaj również zaznaczyć, że skrypt pierwszy, w przeciwieństwie do drugiego, działa jedynie z przypadku liczb. Aby zmienić i dostosować go do losowania dowolnych elementów konieczna byłaby zamiana funkcii random na array_rand. W tym przypadku wyniki były zdecydowanie lepsze dla skryptu nr 2, ponieważ on tablica z danymi jest zadekladowana, przez co różnice, które występowały w przypadku testy by zwyczajnie zanikły.


Podsumowując

Wydajność skryptów jest bardzo ważnym aspektem przy projektowaniu aplikacji i stron internetowych. Stosowanie gotowych rozwiązań znalezionych w Internecie nie zawsze przynosi oczekiwane efekty. O wyborze algorytmu i sposobu realizacji warto pomyśleć jeszcze przed programowaniem, gdyż w przypadku rozrostu systemu jedna drobna zmiana może być bardzo kosztowna. Warto od samego początku pisać, jakby nasz skrypt miał być wywoływany wiele tysięcy razy.

Warto również zaznaczyć, że wybór algorytmu powinien być zależny od danych, jakie będzie przyjmował. Tak jak w tym przypadku - dwa różne rozwiązania okazały się lepsze w różnych sytuacjach w zależności od danych. W przypadku braku informacji o danych musimy niestety wybrać "najmniejsze zło".

A Ty, jakie masz doświadczenia w wydajności skryptów? Znasz jeszcze lepszą metodę do wykonania tego problemu? Zapraszam do dzielenia się swoimi doświadczeniami.

Inne wpisy, które mogą Cię zainteresować

Poniżej przedstawiamy Ci propozycje innych wpisów, które mogą Cię zainteresować. Sprawdź, czytaj i poszerzaj swoją wiedzę.


Czytaj
Wesołych Świąt Wielkanocnych!

Wesołych Świąt Wielkanocnych!

Czytaj
ISO-8859-2 vs. UTF-8. Standardy kodowania nowoczesnych witryn

ISO-8859-2 vs. UTF-8. Standardy kodowania nowoczesnych witryn

Czytaj
Era wyświetlaczy HiDPI. Jak się do niej przygotować?

Era wyświetlaczy HiDPI. Jak się do niej przygotować?

Czytaj
Układ treści prosto z gazet, czyli kolumny w CSS3

Układ treści prosto z gazet, czyli kolumny w CSS3

Komentarze do tego wpisu


comments powered by Disqus