Pomoc - Szukaj - Użytkownicy - Kalendarz
Pełna wersja: Tworzenie drzewa z danych z bazy
Forum PHP.pl > Forum > PHP
tkopacki
7.07.2011, 08:27:15
Witam, problem chyba typowy:
W bazie danych mam użytkowników, każdy z nich ma przypisanych co najwyżej pięciu innych użytkowników. Potrzebuję uzyskać id tych użytkowników poziomami, najlepiej w tablicy, gdzie każdy następny wiersz to tablica id użytkowników kolejnego poziomu.
Przykład bazy danych (dla trzech powiązanych userów):
Kod
                        1
        2                3            4
    5    6    7        8    9    0    11    12    13
                        itd...

Domyślam się, by osiągnąć zamierzony efekt, muszę użyć rekurencji.
Maksymalne zagłębienie takiego drzewa to max 10. poziomów.
Rozwiązanie może nie być specjalnie złożonym algorytmem, ja naskrobałem coś takiego:
[PHP] pobierz, plaintext 
  1. <?
  2. function wyswietlPoziomy($ide,$p=0, $tab=array())
  3. {
  4. 		if($p <= 10)
  5. 		{
  6. 			$zapytanie = "SELECT powiazani, liczbaPow FROM `uzytkownicy` WHERE `id` = '$ide'";
  7. 			$w = mysql_fetch_assoc(mysql_query($zapytanie));
  8.  
  9. 			$t = explode(",",$w["powiazani"]);
  10.  
  11. 			$tab[$p] = $t;
  12.  
  13. 			for($j=0; $j<count($w["liczbaPow"]); $j++)
  14. 				wyswietlPoziomy($t[$j], $p+1, $tab);
  15.  
  16. 		}
  17. 		else
  18. 			return $tab;
  19. }
[PHP] pobierz, plaintext

Niestety ten algorytm jest błędny a nie wiem jak go poprawić.

Prosiłbym bardzo o pomoc w rozwiązaniu problemu.
Pozdrawiam, Tomasz.
morbic
7.07.2011, 20:52:59
Chętnie pomogę, ale potrzebuję więcej informacji. Jak to wygląda w bazie danych? Co oznacza dokładnie liczbaPow? Jaką liczbę powiązań?
tkopacki
8.07.2011, 08:29:01
Dziękuję za odpowiedź.
W bazie danych każdy użytkownik ma oczywiście unikalne pole `id`, pole `powiazani` - w którym przechowuję dane w formie: 5,8,12,45,90 (tak, wiem, że to można optymalniej zrobić na oddzielnej tabeli ale nie w tym teraz sęk), pole `liczbaPow` - jest to liczba numerów id w polu `powiazani` (każdy użytkownik może mieć max. 5 id powiązanych ze swoim kontem). Jeżeli `liczbaPow` == 5 to algorytm szuka, wśród już powiązanych, id do którego może wykonać powiązanie (użytkownika z już powiązanych, którego pole `liczbaPow` < 5).

Przy rejestracji nowego użytkownika, podawany jest id użytkownika już istniejącego w systemie (klient polecający).
Fragment kodu rejestracji:
[PHP] pobierz, plaintext 
  1. $r = mysql_query("SHOW TABLE STATUS LIKE 'uzytkownicy'");
  2. $row = mysql_fetch_array($r);
  3. $ai = $row['Auto_increment'];
  4. mysql_free_result($r);
  5. $idRefs = ustawPowiazanie($ai,$idRef);//$idRef to id klienta polecającego, $idRefs jest zapisywane w polu `idRef` nowego użytkownika
[PHP] pobierz, plaintext

Funkcja odpowiedzialna za wyliczenie "wolnego" (`liczbaPow` < 5) klienta polecającego:
[PHP] pobierz, plaintext 
  1. function ustawPowiazanie($idNowego,$idPolecajacego)
  2. {
  3. 		$zapytanie = "SELECT powiazani, liczbaPow FROM `uzytkownicy` WHERE `id` = '$idPolecajacego'";
  4. 		$w = mysql_fetch_assoc(mysql_query($zapytanie));
  5. 			$ls = array();
  6. 		$ls = explode(",",$w['powiazani']);
  7. 		if(strlen($ls[0]) == 0)
  8. 			$ls = array();
  9.  
  10. 		$lpow = $w['liczbaPow'];
  11. 		if($lpow == 5)
  12. 			for($i = 0; $i < 5; $i++)
  13. 			{
  14. 				$zapytanie = "SELECT powiazani, liczbaPow FROM `uzytkownicy` WHERE `id` = '".$ls[$i]."'";
  15. 				$ws = mysql_fetch_assoc(mysql_query($zapytanie));
  16. 				if($ws["liczbaPow"] < 5)
  17. 					return ustawPowiazanie($idNowego,$ls[$i]);
  18. 			}
  19. 		else
  20. 		{
  21. 			array_push($ls, $idNowego);
  22. 			$im = implode(",", $ls);
  23. 			$lpow++;
  24. 			$zapytanie = "UPDATE `uzytkownicy` SET `powiazani` = '$im', `liczbaPow` = '$lpow' WHERE `id` = '$idPolecajacego'";
  25. 			$q = mysql_query($zapytanie);
  26. 			return $idPolecajacego;
  27. 		}
  28. 		return false;
  29. }
[PHP] pobierz, plaintext


I teraz najważniejsza sprawa, bo powyższe działa dobrze, potrzebuję wyświetlić dane w formie tabeli, czy też drzewa - potrzebna mi do tego tablica wielowymiarowa, tworzona po podaniu numeru id klienta/użytkownika, zawierająca id wszystkich powiązanych klientów, powiązanych powiązanych, powiązanych powiązanych powiązanych itd. - 10 poziomów w głąb. Chodzi o drabinkę systemu MLM.

Jej format powinien być następujący:
[PHP] pobierz, plaintext 
  1. array(
  2. 	idPowiazanego => array(
  3. 		idPowiazanego => array(
  4. 			idPowiazanego => array(/*itd*/),
  5. 			idPowiazanego => array(/*itd*/),
  6. 			idPowiazanego => array(/*itd*/),
  7. 			idPowiazanego => array(/*itd*/),
  8. 			idPowiazanego => array(/*itd*/)
  9. 		),
  10. 		idPowiazanego => array(
  11. 			idPowiazanego => array(/*itd*/),
  12. 			idPowiazanego => array(/*itd*/),
  13. 			idPowiazanego => array(/*itd*/),
  14. 			idPowiazanego => array(/*itd*/),
  15. 			idPowiazanego => array(/*itd*/)
  16. 		),
  17. 		idPowiazanego => array(
  18. 			idPowiazanego => array(/*itd*/),
  19. 			idPowiazanego => array(/*itd*/),
  20. 			idPowiazanego => array(/*itd*/),
  21. 			idPowiazanego => array(/*itd*/),
  22. 			idPowiazanego => array(/*itd*/)
  23. 		),
  24. 		idPowiazanego => array(
  25. 			idPowiazanego => array(/*itd*/),
  26. 			idPowiazanego => array(/*itd*/),
  27. 			idPowiazanego => array(/*itd*/),
  28. 			idPowiazanego => array(/*itd*/),
  29. 			idPowiazanego => array(/*itd*/)
  30. 		),
  31. 		idPowiazanego => array(
  32. 			idPowiazanego => array(/*itd*/),
  33. 			idPowiazanego => array(/*itd*/),
  34. 			idPowiazanego => array(/*itd*/),
  35. 			idPowiazanego => array(/*itd*/),
  36. 			idPowiazanego => array(/*itd*/)
  37. 		)
  38. 	),
  39. 	idPowiazanego => array(
  40. 		idPowiazanego => array(
  41. 			idPowiazanego => array(/*itd*/),
  42. 			idPowiazanego => array(/*itd*/),
  43. 			idPowiazanego => array(/*itd*/),
  44. 			idPowiazanego => array(/*itd*/),
  45. 			idPowiazanego => array(/*itd*/)
  46. 		),
  47. 		idPowiazanego => array(
  48. 			idPowiazanego => array(/*itd*/),
  49. 			idPowiazanego => array(/*itd*/),
  50. 			idPowiazanego => array(/*itd*/),
  51. 			idPowiazanego => array(/*itd*/),
  52. 			idPowiazanego => array(/*itd*/)
  53. 		),
  54. 		idPowiazanego => array(
  55. 			idPowiazanego => array(/*itd*/),
  56. 			idPowiazanego => array(/*itd*/),
  57. 			idPowiazanego => array(/*itd*/),
  58. 			idPowiazanego => array(/*itd*/),
  59. 			idPowiazanego => array(/*itd*/)
  60. 		),
  61. 		idPowiazanego => array(
  62. 			idPowiazanego => array(/*itd*/),
  63. 			idPowiazanego => array(/*itd*/),
  64. 			idPowiazanego => array(/*itd*/),
  65. 			idPowiazanego => array(/*itd*/),
  66. 			idPowiazanego => array(/*itd*/)
  67. 		),
  68. 		idPowiazanego => array(
  69. 			idPowiazanego => array(/*itd*/),
  70. 			idPowiazanego => array(/*itd*/),
  71. 			idPowiazanego => array(/*itd*/),
  72. 			idPowiazanego => array(/*itd*/),
  73. 			idPowiazanego => array(/*itd*/)
  74. 		)
  75. 	),
  76. 	idPowiazanego => array(
  77. 		idPowiazanego => array(
  78. 			idPowiazanego => array(/*itd*/),
  79. 			idPowiazanego => array(/*itd*/),
  80. 			idPowiazanego => array(/*itd*/),
  81. 			idPowiazanego => array(/*itd*/),
  82. 			idPowiazanego => array(/*itd*/)
  83. 		),
  84. 		idPowiazanego => array(
  85. 			idPowiazanego => array(/*itd*/),
  86. 			idPowiazanego => array(/*itd*/),
  87. 			idPowiazanego => array(/*itd*/),
  88. 			idPowiazanego => array(/*itd*/),
  89. 			idPowiazanego => array(/*itd*/)
  90. 		),
  91. 		idPowiazanego => array(
  92. 			idPowiazanego => array(/*itd*/),
  93. 			idPowiazanego => array(/*itd*/),
  94. 			idPowiazanego => array(/*itd*/),
  95. 			idPowiazanego => array(/*itd*/),
  96. 			idPowiazanego => array(/*itd*/)
  97. 		),
  98. 		idPowiazanego => array(
  99. 			idPowiazanego => array(/*itd*/),
  100. 			idPowiazanego => array(/*itd*/),
  101. 			idPowiazanego => array(/*itd*/),
  102. 			idPowiazanego => array(/*itd*/),
  103. 			idPowiazanego => array(/*itd*/)
  104. 		),
  105. 		idPowiazanego => array(
  106. 			idPowiazanego => array(/*itd*/),
  107. 			idPowiazanego => array(/*itd*/),
  108. 			idPowiazanego => array(/*itd*/),
  109. 			idPowiazanego => array(/*itd*/),
  110. 			idPowiazanego => array(/*itd*/)
  111. 		)
  112. 	),
  113. 	idPowiazanego => array(
  114. 		idPowiazanego => array(
  115. 			idPowiazanego => array(/*itd*/),
  116. 			idPowiazanego => array(/*itd*/),
  117. 			idPowiazanego => array(/*itd*/),
  118. 			idPowiazanego => array(/*itd*/),
  119. 			idPowiazanego => array(/*itd*/)
  120. 		),
  121. 		idPowiazanego => array(
  122. 			idPowiazanego => array(/*itd*/),
  123. 			idPowiazanego => array(/*itd*/),
  124. 			idPowiazanego => array(/*itd*/),
  125. 			idPowiazanego => array(/*itd*/),
  126. 			idPowiazanego => array(/*itd*/)
  127. 		),
  128. 		idPowiazanego => array(
  129. 			idPowiazanego => array(/*itd*/),
  130. 			idPowiazanego => array(/*itd*/),
  131. 			idPowiazanego => array(/*itd*/),
  132. 			idPowiazanego => array(/*itd*/),
  133. 			idPowiazanego => array(/*itd*/)
  134. 		),
  135. 		idPowiazanego => array(
  136. 			idPowiazanego => array(/*itd*/),
  137. 			idPowiazanego => array(/*itd*/),
  138. 			idPowiazanego => array(/*itd*/),
  139. 			idPowiazanego => array(/*itd*/),
  140. 			idPowiazanego => array(/*itd*/)
  141. 		),
  142. 		idPowiazanego => array(
  143. 			idPowiazanego => array(/*itd*/),
  144. 			idPowiazanego => array(/*itd*/),
  145. 			idPowiazanego => array(/*itd*/),
  146. 			idPowiazanego => array(/*itd*/),
  147. 			idPowiazanego => array(/*itd*/)
  148. 		)
  149. 	),
  150. 	idPowiazanego => array(
  151. 		idPowiazanego => array(
  152. 			idPowiazanego => array(/*itd*/),
  153. 			idPowiazanego => array(/*itd*/),
  154. 			idPowiazanego => array(/*itd*/),
  155. 			idPowiazanego => array(/*itd*/),
  156. 			idPowiazanego => array(/*itd*/)
  157. 		),
  158. 		idPowiazanego => array(
  159. 			idPowiazanego => array(/*itd*/),
  160. 			idPowiazanego => array(/*itd*/),
  161. 			idPowiazanego => array(/*itd*/),
  162. 			idPowiazanego => array(/*itd*/),
  163. 			idPowiazanego => array(/*itd*/)
  164. 		),
  165. 		idPowiazanego => array(
  166. 			idPowiazanego => array(/*itd*/),
  167. 			idPowiazanego => array(/*itd*/),
  168. 			idPowiazanego => array(/*itd*/),
  169. 			idPowiazanego => array(/*itd*/),
  170. 			idPowiazanego => array(/*itd*/)
  171. 		),
  172. 		idPowiazanego => array(
  173. 			idPowiazanego => array(/*itd*/),
  174. 			idPowiazanego => array(/*itd*/),
  175. 			idPowiazanego => array(/*itd*/),
  176. 			idPowiazanego => array(/*itd*/),
  177. 			idPowiazanego => array(/*itd*/)
  178. 		),
  179. 		idPowiazanego => array(
  180. 			idPowiazanego => array(/*itd*/),
  181. 			idPowiazanego => array(/*itd*/),
  182. 			idPowiazanego => array(/*itd*/),
  183. 			idPowiazanego => array(/*itd*/),
  184. 			idPowiazanego => array(/*itd*/)
  185. 		)
  186. 	)
  187. );
[PHP] pobierz, plaintext

Z obliczeń wynika, że przy takim zagłębieniu i maksymalnym zapełnieniu tablicy, liczba jej elementów wyniesie , ale przy zagłębieniu 7 liczba elementów to

Z reguły w takich aplikacjach przyjmuje się, że liczba osób podpiętych pod każdego klienta jest nie większa od 3 - ja mam w specyfikacji, że ma być nie większa od 5, co drastycznie zwiększa ilość danych przy 10. stopniach zagłębienia.

Jak teraz wykonać metodę, która będzie w stanie utworzyć tak dużą tablicę wielokrotnie zagnieżdżonych tablic?
tkopacki
8.07.2011, 10:17:48
Dzięki za odpowiedź, chodzi o to, że poziom zagłębienia jest dynamiczny, tzn, że każdy klient może być na poziomie 0 względem klientów podpiętych pod niego, ale także na dowolnym poziomie 1-10 względem klientów nadrzędnych.
zegarek84
8.07.2011, 10:20:49
Cytat(tkopacki @ 8.07.2011, 11:17:48 ) *
Dzięki za odpowiedź, chodzi o to, że poziom zagłębienia jest dynamiczny, tzn, że każdy klient może być na poziomie 0 względem klientów podpiętych pod niego, ale także na dowolnym poziomie 1-10 względem klientów nadrzędnych.

więc zagłębień jest więcej niż 10 poziomów ;]

sorki - usunęła mi się poprzednia odpowiedź - więc jak w końcu masz te dane gdyż nie do końca chyba jednak rozumiem - odpytując bazę rekurencyjnie nieźle po niej pojedziesz ;]
tkopacki
8.07.2011, 18:02:35
Struktura tabeli:
[SQL] pobierz, plaintext 
  1. CREATE TABLE  `ml`.`klient` (
  2. `id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY ,
  3. `imie` VARCHAR( 20 ) NOT NULL ,
  4. `nazwisko` VARCHAR( 20 ) NOT NULL ,
  5. `idParent` INT NOT NULL
  6. ) ENGINE = MYISAM ;
[SQL] pobierz, plaintext

Funkcja mająca stworzyć tablicę:
[PHP] pobierz, plaintext 
  1. function makeArray($idParent,$deep){
  2. 	$sql="SELECT idParent, id, FROM tabela WHERE idParent=".$idParent>0?$idParent:'null';
  3. 	foreach ($sql AS $krotka){
  4. 		if(isset($krotka['id'])){
  5. 			makeArray($krotka['idParent'],$deep++);
  6. 			return array("id"=>$krotka['id'], "deep"=>$deep);
  7. 		}
  8. 	}
  9. }
[PHP] pobierz, plaintext


Tylko teraz jest problem, bo ta funkcja bardzo przeciąża serwer i skrypt się nie wykonuje.
Czy można jakoś usprawnić powyższy kod dla założeń przedstawionych wcześniej?
CuteOne
8.07.2011, 19:00:03
Ja bym zastosował metodę szukania wg. IP tzn. każdy użytkownik miał by zapisany adres wszystkich powiązań w górę. Bazując na twoi przykładzie:
Kod
                        1
        2                3            4
    5    6    7        8    9    0    11    12    13
                        itd...


Dla użytkownika 8 IP = 1.3.8 dla 12 IP=1.4.12 itd..

Teraz wystarczy użyć w zapytaniu LIKE np. dla 3:
[SQL] pobierz, plaintext 
  1. SELECT * FROM users WHERE concat_ip LIKE CONCAT("3.%")
[SQL] pobierz, plaintext



Możesz też dodać kolumnę określającą zagłębienie - znacznie ułatwi ci to wyszukiwanie / edycję drzewa

ano
8.07.2011, 19:25:50
Wydaje mi się, że źle do tego podchodzisz.
Powinieneś w jednym zapytaniu pobrać z DB wiersze z wymaganymi użytkownikami.
Po pobraniu tego fragmentu tabeli, przetwarzasz go odpowiednio w php. (czyli: w jednym zapytaniu do mysql pobierasz array() użytkowników, który następnie przetwarzasz już na poziomie php).
A problem z powiązaniami wymaga użycia struktury grafu. (broń Boże drzewa! sam zobacz jak dużo miejsca zajmuje Twoja struktura danych, w porównaniu z tym co zaraz przeczytasz;) )

Graf implementujesz jako "lista sąsiedztwa". Taka reprezentacja grafu wygląda mniej więcej tak
Wierzchołek | array() wierzchołków powiązanych
1: 2,3,4
2: 1,4,
3: 1, 4
4: 1,2,3

czyli mniej więcej tak:
Kod
array(
    array(
        Object: wierzcholek,
        array(
            Object: wierzcholek,  //lista
            ...
        ),
    ),
    array(
        Object: wierzcholek,
        array(
            Object: wierzcholek,
            ...
        ),
    ),
)


gdzie Wierzchołek to Twój obiekt "użytkownik".

A teraz klucz do rozwiazania problemu:
A jak juz bedziesz miał tak zapisany graf, to do przedstawienia 'poziomów' powiązań użytkowników wykorzystujesz algorytm DFS (przejście WGŁĄB ) - http://pl.wikipedia.org/wiki/Przeszukiwanie_w_głąb.

Twój problem jest o tyle fajny, że wreszcie zmusza do programowania (a nie kolejnego klepania tego samego kodu ;P )

//jakbyś chciał to pisałem kiedyś kod DFSa ale w Javie, jednak jest to tak zbliżone do php, że myślę że dałbyś sobie rade z przepisaniem do php//
tkopacki
9.07.2011, 00:49:34
Koncepcja grafu jak najbardziej mi odpowiada, sam też w javie pisałem metody BSF i DSF więc jakoś to na php przełożę - dzięki za sugestie! Bardzo trafny pomysł smile.gif
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.
Invision Power Board © 2001-2025 Invision Power Services, Inc.