[PHP] Jak zoptymalizować tą pętlę i jej rekurencję Opcje

[jajcarzd1]

Witam

Mam w bazie danych zapisane kategorie gdzie tabela ta posiada między innymi takie nagłówki jak idCategories,idParent,name itp.

Potrzebuję wyciągnąć wszystkie kategorie wraz z ich potomkami niezależnie od stopnia zagnieżdzenia aby potem móc zrobić sobie menu np. takie http://jquery.bassistance.de/treeview/demo/?1 czyli wszystkie elementy pociągnięte od razu a nie w trakcie kliknięcia na danego potomka. Wiec konstrukcje <ul> z zagłębieniami

W tabeli kategorii jest około 1400 kategorii na chwilę obecną około 14 pierwszego poziomu czyli z idparent = 0, 165 drugiego i jakieś 1300 trzeciego poziomu. Elementy pobieram rekurencyjnie ale to nie jest za bardzo problemem a ilość pętli jaka musi być wykonana i jest ich w sumie w chwili obecnej około 240 000, czas wykonywania tej operacji to około 0,4 sekundy i tak nie mam za bardzo pomysłu co tu można jeszcze poprawić

[PHP] pobierz, plaintext 
/* tu pobieram wszystkie elementy z idparent = 0 i tworzę tablicę obiektów 
    bo normalnie to mi zwraca tablicę dwuwymiarową. Na każdym poziomie tworzę obiekty 
    gdyż nie bardzo widziałem rozwiązanie aby kombinować z określaniem kolejnego poziomu zagłębienia tablicy 
    a tak przekazuję referencję obiektu */
 
$result  = $this->classMysql->ta($sql);
		$r = array();
 
		foreach ($result as $item) {
			$object = new stdClass();
			$object->idCategories = $item['idCategories'];
			$object->item = $item['name'];
			$object->nodes = array();
			$r[] = $object;
		}
 
$this->dbGetNodes($r);
 
 
private function dbGetNodes(&$result) {
 
		$this->allCategories = $this->classMysql->ta("SELECT idCategories,idParent,name FROM categories ORDER BY sequence");
		$allIdParents = array();
		$this->allIdParentsAsKeys = array();
 
		foreach ($this->allCategories as $cat) {
			$allIdParents[] = $cat['idParent'];
		}
 
		$allIdParents = array_unique($allIdParents);
 
		foreach ($allIdParents as $item) {
			$this->allIdParentsAsKeys[$item] = 1;
		}
 
		for($i = 0, $ii = count($result); $i<$ii; $i++) {
 
			$this->createNodes($result[$i]->idCategories,$result[$i]);
 
		}
 
 
	}
 
 
	private function createNodes($idCategories,$object) {
 
		$this->iteration++;
 
 
		for($i = 0, $ii = count($this->allCategories); $i<$ii; $i++) {
 
			$this->iteration2++;
 
			if($this->allCategories[$i]['idParent'] == $idCategories) {
 
				$ob = new stdClass();
				$ob->idCategories = $this->allCategories[$i]['idCategories'];
				$ob->item = $this->allCategories[$i]['name'];
				$ob->nodes = array();
 
				$object->nodes[] = $ob;
 
				/*
				if(in_array($allCategories[$i]['idCategories'],$allIdParents)) {
					$this->createNodes($allCategories[$i]['idCategories'],$ob,$allCategories,$allIdParents);
				}
				*/
 
                                                /* szybsze niż in_array */
 
				if(isset($this->allIdParentsAsKeys[$this->allCategories[$i]['idCategories']])) {
					$this->createNodes($this->allCategories[$i]['idCategories'],$ob);
				}
 
 
			}
 
 
		}
 
	}
[PHP] pobierz, plaintext 

Jakby ktoś miał jakis pomysł jak to zoptymalizować to byłbym wdzięczny.
Pozdrawiam

[wookieb]

Zastosować inny rodzaj drzewa w bazie danych. Left right, bądź IP

[jajcarzd1]

Zastosować inny rodzaj drzewa w bazie danych. Left right, bądź IP

Zmiany w bazie odpadają dlatego pytam o optymalizację tego co jest.

[wookieb]

Jak już to:
1) Cache - dla każdego rodzica listę ich dzieci
2) Dlaczego pobierasz WSZYSTKIE elementy a dopiero potem je "wyszukujesz" w duzej tablicy?
Załóż klucz "index" na pole "idParent" w swojej bazie i wyszukuj tylko te rekordy, które potrzebujesz

[jajcarzd1]

2) Dlaczego pobierasz WSZYSTKIE elementy a dopiero potem je "wyszukujesz" w duzej tablicy?
Załóż klucz "index" na pole "idParent" w swojej bazie i wyszukuj tylko te rekordy, które potrzebujesz

Po to pobieram wszystkie i przelatuję w pętli aby ograniczać ilośc zapytań do bazy (których przy założeniu że kategorie trzeciego poziomu już nie mają potomków) będzie 165. Ta sama wersja ale oparta na pobieranie kategorii z bazy za kazdym razem wykonuję mi sie prawie 1,5 sekundy więc to tez odpada.

[wookieb]

A stworzyłeś klucze tak jak mówiłem?
Pozostaje Ci cache jak nic innego nie chcesz robić.

[taktu]

Można trochę udoskonalić kod, wywalić foreach czy wyciągnąć count przed pętle - to tak na pierwszy rzut oka. Może tutaj znajdziesz coś co pomoże.

[jajcarzd1]

A stworzyłeś klucze tak jak mówiłem?

No pewnie ale tak jak napisałem za dużo zapytań by było.

Można trochę udoskonalić kod, wywalić foreach czy wyciągnąć count przed pętle - to tak na pierwszy rzut oka. Może tutaj znajdziesz coś co pomoże.

No a co mi da wywalenie pętli jak ja jej potrzebuję. Count jest odpalany raz na początku pętli a nie za każdą iteracją. Natomiast zastosowanie tylko jednego count-a i przypisanie go do właściwości klasy aby uniknąć ponownego odpalania w rekurencji nie poprawiło efektywności. Zerknę jeszcze na link który zapodałeś

[wookieb]

No to nie ma opcji. Przebudowa drzewa albo siedzisz dodatkowych pare godzin nad cache.

[croc]

Count jest odpalany raz na początku pętli a nie za każdą iteracją.

Niestety mylisz się. Jak masz count( ) w środkowej części for to odpala się co iterację i tak musi być, bo przecież mógłbyś sobie dodawać/usuwać w pętli elementy tablicy i wtedy cache'owanie tej wartości byłoby bez sensu.

[jajcarzd1]

Niestety mylisz się. Jak masz count( ) w środkowej części for to odpala się co iterację i tak musi być, bo przecież mógłbyś sobie dodawać/usuwać w pętli elementy tablicy i wtedy cache'owanie tej wartości byłoby bez sensu.

Czegoś chyba nie kumam mówisz o tej części ?

[PHP] pobierz, plaintext 
 
for($i = 0, $ii = count($this->allCategories); $i<$ii; $i++) {
 
[PHP] pobierz, plaintext 

Przecież tu mam odpalanie counta raz dla danej rekurencji. Przecież gdyby było co iterację to by było

[PHP] pobierz, plaintext 
 
for($i = 0, $ii < count($this->allCategories); $i++) {
 
[PHP] pobierz, plaintext 

[marcio]

@cron ma racje wywal tego count() nad petle, przypisz to co zwraca do jakiejs zmiennej i to ja przekazuj do petli.

[jajcarzd1]

@cron ma racje wywal tego count() nad petle, przypisz to co zwraca do jakiejs zmiennej i to ja przekazuj do petli.

Napisałem wcześniej że nie widziałem praktycznie żadnej zmiany wydajności na plus gdy dałem wynik count-a do właściwości klasy

[PHP] pobierz, plaintext 
for($i = 0, $i < $this->quantity; $i++) 
[PHP] pobierz, plaintext 

[phpion]

@jajcarzd1:
Nie słuchaj ~crona ani ~marcio odnośnie tej pętli. Pierwotnie, czyli tak:

[PHP] pobierz, plaintext 
for($i = 0, $ii = count($this->allCategories); $i<$ii; $i++) {
[PHP] pobierz, plaintext 

miałeś dobrze.

[jajcarzd1]

@jajcarzd1:
Nie słuchaj ~crona ani ~marcio odnośnie tej pętli. Pierwotnie, czyli tak:

[PHP] pobierz, plaintext 
for($i = 0, $ii = count($this->allCategories); $i<$ii; $i++) {
[PHP] pobierz, plaintext 

miałeś dobrze.

No do tego rozwiązania jestem przekonany że miałem dobrze, ale oczywiście w każdej rekurencji pętla leci od nowa więc tam jest ponownie odpalany count(), ale tak jak napisałem przerzucenie jego wyniku do właściwości obiektu praktycznie nic nie dało bo to zbyt mały zysk.

[taktu]

z wywaleniem foreach miałem na myśli zamianę na for/while ale wiele to nie da bo tam akurat masz mało iteracji.

[croc]

Aha, zawarłeś to jednak w pierwszej części for, no to ok - liczy raz. Nie wczytałem się dokładnie w kod, sorry (IMG:style_emoticons/default/smile.gif) Ale uważam, że takie upychanie na siłę kodu nie jest zbyt dobrym pomysłem. Wprawdzie masz argument, że tego counta liczysz tylko na chwilę, dla pętli, ale chyba lepiej jak widać od razu poszczególne części for.