Przetwarzanie danych na szybkości – cz. 2

Na pierwszy rzut idzie sprawdzenie jak poradzi sobie php w dwóch różnych wersjach. Ze wstępnych testów wynika, że pracuje na lekko ponad 110 000 kombinacjach. Dla zwykłego komputera nie jest to specjalnie wymagające. Ale gdyby skrypt był bardziej skomplikowany lub danych byłoby więcej? W tej części poznamy odpowiedź na pytanie czy wybrany algorytm będzie najlepszy w tym wypadku. Zobaczymy też różnice pomiędzy pracą z bazą lokalną i zdalną.

Baza danych

Zanim zaczniemy tworzyć skrypty i programy, należałoby utworzyć odpowiednie tabele. Ja stworzyłem dwie tabele: losowania i trojki.  Wszystko mam w bazie danych lotto. Tabela losowania składa się z kolumn:

• id
• date
• first
• second
• third
• fourth
• fifth
• sixth

 

Tabela trojki składa się z:

• id
• count
• one
• two
• three

 

Do tej bazy został dodany indeks unikalny:

ALTER TABLE `trojki` ADD UNIQUE `unique_index`(`one`, `two`, `three`);

 

Dzięki niemu możliwe jest przeniesienie liczenia występujących trójek na bazę danych. Jest to wykorzystywane tylko w pierwszym algorytmie.

 

INSERT INTO trojki(count, one, two, three) VALUES('1', '@one', '@two', '@three')
ON DUPLICATE KEY UPDATE count = count+1

 

Kod powoduje warunkowe dodawanie. Jeżeli w tabeli jest już unikalna wartość trzech kolumn to jest zwiększany licznik.

 

Funkcje podstawowe

W każdym moim skrypcie/programie będę używał takich samych funkcji. Podstawową funkcją jest generateThree, czyli funkcja generująca wszystkie trójki z danego kompletu 6 liczb.

function generateThree($numbers){
  $data = array();
  for($x=0;$x<6;$x++)
    for($y=0;$y<6;$y++)
      for($z=0;$z<6;$z++)
        if($x != $y && $x != $z && $y != $z){
          $tmp[0] = $numbers[$x];
          $tmp[1] = $numbers[$y];
          $tmp[2] = $numbers[$z];
          sort($tmp);
          $data[] = $tmp;
        }
  return removeDoubles($data);
}

Funkcja jako argument dostaje tablicę z liczbami (adresy od 0-5). Następnie uruchamiane są 3 pętle. Każda dla jednej liczby z trójki. Później pojawia się warunek, który wyklucza dublowanie się liczb w danej trójce. Później następuje sortowanie każdej trójki. Na koniec tuż przed zwróceniem danych wywoływana jest funkcja removeDoubles, która usuwa podwójnie występujące trójki. Zmniejsza ona 120 kombinacji wygenerowanej z jednego losowania do 20. Wygląda ona tak:

function removeDoubles($numbers){
  $data = array();
  foreach($numbers as $n)
    if(!seekDoubles($data, $n))
      $data[] = $n;
  return $data;
}

Funkcja w pętli sprawdza czy tablicy $data jest już aktualna trójka. Jeżeli nie ma to dopisuje. Za sprawdzanie odpowiada funkcja seekDoubles.

function seekDoubles($numbers, $three){
  $found = false;
  foreach($numbers as $n)
    if($n[0] == $three[0] && $n[1] == $three[1] && $n[2] == $three[2])
    $found = true;
 return $found;
}

Funkcja przeszukuje tablicę $numbers aby znaleźć tam trójkę. Jeżeli znajdzie to zwraca prawdę.

Przyszła pora na skrypt pierwszego typu.

Pobiera on liczby z tablicy losowania i na bieżąco generuje dane i dodaje do bazy danych. Wszytko dzieje się w pętli przy użyciu pojedynczej transakcji dla każdej wygenerowanej trójki.

Pobieranie losowań z bazy, generowanie trójek i liczenie ich zajmuje skryptowi ok 35s. Rozszerzenie skryptu o dodawanie wpisów do trójek wydłuża ten czas do ok 120 sekund.

Kilka liczb

Do bazy mam wprowadzone 5560 losowań. Trzy pętle z funkcji generateThree generują 120 kombinacji dla każdego losowania. Daje nam to 667 200 możliwości. Oczywiście jest tutaj mnóstwo powtórzeń wynikających z generowania tych samych liczb tylko w odwrotnej kolejności. Po usunięciu ich przez funkcję removeDoubles pozostaje 20 kombinacji na każde losowanie. Jest to dokładnie 111 200 trójek. Po wyeliminowaniu zdublowanych z różnych losowań zostaje nam 18 374.

Skrypt numer dwa

We wstępnej fazie projektowania drugiego algorytmu popełniłem błąd. Zastosowałem równie czasochłonne rozwiązanie jakim było zastosowanie funkcji zbliżonej do seekDoubles . W przypadku tak dużej ilości kombinacji sprawdzanie trwało niezwykle długo. Z moich szybkich szacowań wyszło, że skrypt mysiałby działać ponad 2 godziny aby wygenerować listę trójek.

Zastosowałem jednak inną metodę. Utworzyłem trójwymiarową tablicę każda z indeksami od 1 do 49 włącznie. Tablica została wyzerowana w konstruktorze klasy. Następnie proces dodawania wygląda tak:

public function add($six){
  $list = $this->generateThree($six);
  foreach($list as $l)
    $this->numbers[$l[0]][$l[1]][$l[2]]++;
}

Funkcja na wejściu dostaje tablicę z sześcioma liczbami [0-5]. Następnie na jej podstawie generowane są kombinacje trójek. Każda trójka służy jako indeks w tablicy trójwymiarowej. Wartość takiej pozycji jest zwiększana tworząc nam ilość występowań.

Następnie jest użyta funkcja która zamienia tablicę 3D w coś bardziej przyziemnego. Następnie jest już tylko dodawanie do bazy danych.

Skrypt jest zdecydowanie wydajniejszy od wersji pierwszej. Czas jaki potrzebuje na dodanie trójek do pamięci to 35 sekund, 1 sekundę zajmuje zamiana na tablicę jednowymiarową i policzenie wszystkich dostępnych. Natomiast dodawanie do bazy danych zajęło niecałe 6 sekund. Jak łatwo policzyć, cały skrypt wypracował takie działanie w niecałe 42 sekundy.

Wszystko fajnie, ale jak się to ma do bazy zdalnej?

Jak można było się spodziewać czas pracy skryptów się wydłużył. Pierwszy skrypt przerwałem po lekko ponad 20 minutach. Drugi skrypt sam zakończył pracę po 18 minutach i 19 sekundach. Pierwszy skrypt ma 5 razy więcej transakcji czyli łatwo policzyć, że pracowałby 1 godzinę i 40 minut. Różnica jest dosyć duża, dlatego należy jak najbardziej ograniczyć kontakty z bazą danych. Oczywiście ja zastosowałem tutaj rozwiązanie nie najlepsze pod kątem wydajności. Zamiast zastosować jedną transakcję lub kilka (w zależności od ograniczeń serwera), użyłem tutaj jednej dla każdej trójki.

Ograniczamy transakcje

Na początek zabrałem się za drugi, szybszy skrypt. Zamieniłem wiele transakcji na jedną. Czas pracy skryptu skrócił się z 18 minut do 40 sekund. Czy takie samo rozwiązanie dla pierwszego skryptu również się sprawdzi?

Niestety takie rozwiązanie się nie sprawdziło. Spowodowane było to zbyt dużą ilością zapytań w jednej transakcji. Pomimo niedodania informacji do bazy danych skrypt pracował od 100 do 170 sekund.

Jak widać, jest to rozwiązanie które nie spełnia wymagań wobec wydajności. Tak jak zakładałem najlepszym rozwiązaniem będzie zastosowanie skryptu, który przeprowadza odpowiednie obliczenia we własnym zakresie.