Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

3 Stron V   1 2 3 >  
Reply to this topicStart new topic
> Drzewka w PHP [rzseattle]
scanner
post 14.04.2004, 10:19:48
Post #1





Grupa: Zarząd
Postów: 3 503
Pomógł: 28
Dołączył: 17.10.2002
Skąd: Wrocław




Dyskusje na temat artykułu "Drzewka w php"

Ten post edytował nospor 14.12.2005, 20:12:38


--------------------
scanner.info
Warto pamiętać: KISS, DRY
Go to the top of the page
+Quote Post
Seth
post 14.04.2004, 11:34:49
Post #2





Grupa: Przyjaciele php.pl
Postów: 2 335
Pomógł: 6
Dołączył: 7.03.2002

Ostrzeżenie: (0%)
-----


Trzy dni wczesniej ten art byl by dla mnie zbawieniem winksmiley.jpg
Go to the top of the page
+Quote Post
scanner
post 14.04.2004, 11:36:42
Post #3





Grupa: Zarząd
Postów: 3 503
Pomógł: 28
Dołączył: 17.10.2002
Skąd: Wrocław




Trzy dni wcześniej byłem na wyjeżdzie, a art dostałem tuz przed wyjazdem właśnie smile.gif
BTW: trzy dni temu, to świętować było, a nie pracować smile.gif


--------------------
scanner.info
Warto pamiętać: KISS, DRY
Go to the top of the page
+Quote Post
halfik
post 14.04.2004, 13:43:55
Post #4





Grupa: Zarejestrowani
Postów: 259
Pomógł: 0
Dołączył: 17.05.2003
Skąd: Nysa

Ostrzeżenie: (10%)
X----


No a dla mnie byłby zbawienny 2 tygonei temu, gdy kombinowałem jak na bazie zrobić tree żeby móc pruszac się zarówno w pionie jak i poziomie (prawie 2h bym zaoszczędził...). Nic, pewnie się jeszcze nie jedemu przyda smile.gif


--------------------


"Nie wiedziałem tylko, że Bóg też był na grzybach, gdy majstrował przy wszechświecie" (Janusz Wisniewski)
dev: gazeta.ie
Go to the top of the page
+Quote Post
lukaswoj
post 14.04.2004, 14:28:23
Post #5





Grupa: Zarejestrowani
Postów: 136
Pomógł: 0
Dołączył: 2.01.2004
Skąd: Lublin

Ostrzeżenie: (0%)
-----


Bardzo ciekawe podejście.

Ja jakiś czas temu jak musiałem się uporać z drzewkami, zrobiłem to wykorzystując dwie tablice. Jedna odzwierciedlała strukturę drzewa a druga - jednowymiarowa trzymała referencje do każdego z elementów drzewa.

Każdy element drzewa to był obiekt klasy TreeElement, a do zarządzania całością była klasa Tree (ona miała w sobie te dwie tablice) posiadająca metody realizujące podobne zadania jak wymienione w art'sie.

Nigdy nie sprawdzałem jak bardzo wolne to jest ale z góry zakładam, że chociażby w porównaniu ze sposobem przedstawionym w tym arts'ie - moje rozwiązanie jest żółwiem smile.gif.

Czy ma ktoś z was jakieś linki do podobnych artykułów (mogą być po angielsku) ? Jeśli tak to będę wdzięczny za zapodanie ich.

pozdrawiam

Dzieki za prace


--------------------
Pozdrawiam
Łukasz Wojciechowski
New Generation Software
+48 602 214 629
http://www.ngsoft.pl
Go to the top of the page
+Quote Post
kwiateek
post 14.04.2004, 16:00:15
Post #6





Grupa: Zarejestrowani
Postów: 223
Pomógł: 0
Dołączył: 13.01.2003
Skąd: 3rd ball of mud behind a big ball of burning gas

Ostrzeżenie: (0%)
-----


Jasno, zwięźle i konkretnie (-;. Mi także się ten artykuł przyda.

Pozdrawiam.


--------------------
It's Time to Join the PLD Linux Generation!
<? while (!$success) { $try++; } ?>
Go to the top of the page
+Quote Post
enceladus
post 14.04.2004, 21:10:53
Post #7





Grupa: Zarejestrowani
Postów: 127
Pomógł: 0
Dołączył: 19.11.2003
Skąd: Poznań

Ostrzeżenie: (0%)
-----


Fajna i prosta implementacja, tylko to ograniczenie głębokości sad.gif Stosowanie stringów do przetrzymywania schematu drzewa może też wpłynąć na wydajność przy większych drzewkach.
Dlatego zawsze będę polecał metodą Depesza - http://www.depesz.pl/various-sqltrees-impl...lementation.php - Jest kompilacją najlepszych metod jakie znam smile.gif Zainteresowanych odsyłam do artykułu - przykłady są na bazie Postgresa - w tym konkretnym przypadku widać jego ogromną przewagę na MySQL-em (funkcje, triggery). Nie ma jednak problemu z przeportowaniem wszystkiego ma MySQL-a.


--------------------
Enceladus
Warsztat: bez warsztatu
Aktua
Go to the top of the page
+Quote Post
rzseattle
post 14.04.2004, 22:22:52
Post #8





Grupa: Przyjaciele php.pl
Postów: 554
Pomógł: 0
Dołączył: 4.04.2002
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Ciesze sie ze art bedzie pomocny biggrin.gif.

Co do samej implementacji to moze dopisze kiedys czesc druga "Jak rozszezyc funkcjonalnosc" i opisze tam sposob zwiekszenia mozliwosci (ilosc dzieci ograniczona np do 99 lub nawet do 999 winksmiley.jpg ).

@enceladus

Oczywiscie masz racje ale mi chodzilo o prosta i wmiare szybka klase. Nie chcialem stosowac zaawansowanych i nie przenosnych na inne bazy funkcji i triggerow.


--------------------
"Real children don't go hoppity-skip unless they are on drugs."
Go to the top of the page
+Quote Post
halfik
post 15.04.2004, 07:19:04
Post #9





Grupa: Zarejestrowani
Postów: 259
Pomógł: 0
Dołączył: 17.05.2003
Skąd: Nysa

Ostrzeżenie: (10%)
X----


Ale dlaczego chesz ograniczać wielkość drzewa? Czy nie lepiej zrobić bez limitu wysokości?

Tree z ograniczeniami, to jednak nie to co każdemu w każdej sytuacji mogłoby sie przydać.


--------------------


"Nie wiedziałem tylko, że Bóg też był na grzybach, gdy majstrował przy wszechświecie" (Janusz Wisniewski)
dev: gazeta.ie
Go to the top of the page
+Quote Post
enceladus
post 15.04.2004, 10:34:56
Post #10





Grupa: Zarejestrowani
Postów: 127
Pomógł: 0
Dołączył: 19.11.2003
Skąd: Poznań

Ostrzeżenie: (0%)
-----


Cytat
Nie chcialem stosowac zaawansowanych i nie przenosnych na inne bazy funkcji i triggerow.

Tu bym właśnie dyskutował nad słabościami MySQL, brak funkcji i triggerów o kluczach obcych nie wspomnę - są to niestety poważne braki - jedyna nadzieja w przyszłych wersjach smile.gif Każda poważna baza danych posiada takie funkcjonalności i wcale nie są zaliczane do kategorii zaawansowane - raczej podstawowe.


--------------------
Enceladus
Warsztat: bez warsztatu
Aktua
Go to the top of the page
+Quote Post
rzseattle
post 15.04.2004, 19:27:27
Post #11





Grupa: Przyjaciele php.pl
Postów: 554
Pomógł: 0
Dołączył: 4.04.2002
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Cytat
Ale dlaczego chesz ograniczać wielkość drzewa? Czy nie lepiej zrobić bez limitu wysokości?

Tree z ograniczeniami, to jednak nie to co każdemu w każdej sytuacji mogłoby sie przydać.


Owszem ograniczenia sa, ale tylko w arcie, pisze teraz klase ktora omija wszystkie niedoskonalosci pierwowzoru. Jak juz wspominalem w podsumowaniu - nie chodzilo mi o podanie na tacy gotowego rozwiazania. Wydaje mi sie ze nie taka jest rola artow.

UPDATE:
heh jeszcze raz to przeczytalem i zauwazylem ze wlasciwie nie odpowiedzialem na pytanie.
Otoz ograniczenie wysokosci drzewa istnieje poniewaz pomaga w utrzymaniu odpowiedniej wydajnosci. Jesli potrzebujesz drzewa z 4 poziomami zaglebienia to po co ci level ze stoma cyframi?

Cytat
Tu bym właśnie dyskutował nad słabościami MySQL, brak funkcji i triggerów o kluczach obcych nie wspomnę - są to niestety poważne braki - jedyna nadzieja w przyszłych wersjach Każda poważna baza danych posiada takie funkcjonalności i wcale nie są zaliczane do kategorii zaawansowane - raczej podstawowe.


Zdaje sobie z tego sprawe jednak MySQL jest obecnie jesli nie najpopularniejsza to jedna z najpopularniejszych baz. I wlasnie na nia chcialem to napisac. Pozatym art pelniac roleedukacyjna tylko wskazuje pewna mozliwosc. Nie mowie ze masz na tej metodzie oprzec super wielkie drzewa uprawnien z setkami podgrup itd. Jesli natomiast potrzebujesz na szybko czegos drzewiastego to nie widzialem zreczniejszej i szybszej implementacji. I naprawde to nie sa puste slowa ale podparte doswiadczeniem. Drzewka wedlug depesza studiowalem i stosowalem jednak stopien komplikacji nie jest czasami adekwatny do zastosowania.


--------------------
"Real children don't go hoppity-skip unless they are on drugs."
Go to the top of the page
+Quote Post
DhuCerbin
post 15.04.2004, 20:37:31
Post #12





Grupa: Zarejestrowani
Postów: 14
Pomógł: 0
Dołączył: 10.06.2003

Ostrzeżenie: (0%)
-----


troche nieciekawym rozwiazaniem jest korzystanie w artykule z klasy, o któej nic nie wiadomo, a mianowici 'db' - newbie moze nie miec pojecia co robia jej metody ... dobrym wyjsciem by było podać co zwracają. A same metody napisać moze użytkownik sobie sam.
Go to the top of the page
+Quote Post
Bora
post 15.04.2004, 22:39:40
Post #13





Grupa: Zarejestrowani
Postów: 270
Pomógł: 0
Dołączył: 15.06.2003

Ostrzeżenie: (0%)
-----


Zastanawiało mnie czy to LIKE jest optymalne
i moja propozycja:
  1. SELECT *, INSTR(level,'0')-1 AS depth, INSTR(level,'0')-1 - 1 AS relativeDepth
  2. FROM groups WHERE cluster = 1 AND level LIKE '1%' AND INSTR(level,'0')-1 <= (5+1)
  3. ORDER BY level
  4.  
  5. ## zmienić na
  6.  
  7. SELECT * , INSTR(
  8. level , '0' ) -1 AS depth, INSTR(level , '0' ) -1 -1 AS relativeDepth
  9. FROM groups WHERE cluster =1 AND LEFT(level , '1' ) = '1' AND INSTR(
  10. level , '0' ) -1 <= ( 5 +1 )
  11. ORDER BY level

czyli kod :
  1. SELECT *, INSTR(level,'0')-1 AS depth, INSTR(level,'0')-1 - [*parent_depth*] AS relativeDepth
  2. FROM groups WHERE cluster = [*parent_cluster*] AND # level LIKE '[*parent_cutLevel]%'
  3. LEFT(level, [*$depth*]) = [*parent_cutLevel] AND INSTR(level,'0')-1 <= ([*$depth*]+[*parent_depth*])
  4. ORDER BY level

co do oznaczeń nie jestem pewien.
Go to the top of the page
+Quote Post
rzseattle
post 15.04.2004, 22:50:37
Post #14





Grupa: Przyjaciele php.pl
Postów: 554
Pomógł: 0
Dołączył: 4.04.2002
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Bora podejscie i oznaczenia jak najbardziej sluszne.

Dorwe scannera to w arcie poprawimy to zapytanie/a.


--------------------
"Real children don't go hoppity-skip unless they are on drugs."
Go to the top of the page
+Quote Post
Nalfein][WR
post 17.04.2004, 13:35:17
Post #15





Grupa: Zarejestrowani
Postów: 66
Pomógł: 0
Dołączył: 22.04.2003
Skąd: Żory / K-ce

Ostrzeżenie: (0%)
-----


rzseattle - fajna koncepcja, a co do głównego ograniczenia - 9 dzieci - możesz przecież umieszczać w tym stringu litery, które także można traktować operatorami "<" i ">". I tak 1 < A < Z, bo ord('1') < ord('A') < ord('Z'). Mały problem by był z działaniami arytmetycznymi, bo między ostatnią cyfrą, a pierwszą literą jest trochę innych znaków w tablicy ASCII. Sposobem na to jest traktowanie tego ciągu znaków jak np. liczby szesnastkowej z wykorzystaniem HEX2DEC (ale wtedy mamy do 15 dzieci) albo po prostu użycie całej tablicy ascii, wtedy zapiszemy 255 dzieci.


--------------------
Gadu-Gadu: 3909164
Go to the top of the page
+Quote Post
rzseattle
post 17.04.2004, 14:42:28
Post #16





Grupa: Przyjaciele php.pl
Postów: 554
Pomógł: 0
Dołączył: 4.04.2002
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Cytat
[WR"]a co do głównego ograniczenia - 9 dzieci - możesz przecież umieszczać w tym stringu litery, które także można traktować operatorami "<" i ">". I tak 1 < A < Z, bo ord('1') < ord('A') < ord('Z'). Mały problem by był z działaniami arytmetycznymi, bo między ostatnią cyfrą, a pierwszą literą jest trochę innych znaków w tablicy ASCII. Sposobem na to jest traktowanie tego ciągu znaków jak np. liczby szesnastkowej z wykorzystaniem HEX2DEC (ale wtedy mamy do 15 dzieci) albo po prostu użycie całej tablicy ascii, wtedy zapiszemy 255 dzieci.


Tez dobry pomysl. Prawde mowiac ostatnio nie mam czasu rozbudowac tej koncepcji ale i tak to bede musial zrobic bo bede musial ja wykorzystac w kilku projetach. Jak juz sie za to wezme to rozwaze kilka mozliwosci w tym twoja. Jednak myslalem przedewszystkim o zwiekszeniu ilosci liczb do zapisu levelu tylko ze nie moge wykorzytywac w takich liczbach zer i w tym momecie pojawia sie maly problem. Ale to drobiazg bo przeciez jako znak konca levelu mozna wziasc podwojne zero.


--------------------
"Real children don't go hoppity-skip unless they are on drugs."
Go to the top of the page
+Quote Post
Nalfein][WR
post 18.04.2004, 13:29:00
Post #17





Grupa: Zarejestrowani
Postów: 66
Pomógł: 0
Dołączył: 22.04.2003
Skąd: Żory / K-ce

Ostrzeżenie: (0%)
-----


Jeśli już masz tak gmatwać to może rozważ użycie nested sets (left i right marker) rozszerzonych o informację o głębokości danego rekordu względem korzenia drzewa(depth). Dzięki temu masz wszystkie zalety nested sets i rozwiązania Depesza w jednym. Rozbudowa podobnie trudna jak w przypadku Twojego pomysłu, ale szybkość odczytu nieporównywalnie większa.

Pobrać wszystkie dzieciaki, wnuki, prawnuki itd. wybranego rekordu:
[sql:1:9b52cbd8af]SELECT * FROM tree WHERE lft BETWEEN $my[lft] AND $my[rgt][/sql:1:9b52cbd8af]

Pobrać tylko dzieciaki:
[sql:1:9b52cbd8af]SELECT * FROM tree WHERE lft BETWEEN $my[lft] AND $my[rgt] AND depth = $my[depth]+1[/sql:1:9b52cbd8af]

Pobrać n-tego dzieciaka wiedząc że istnieje (assert($my[rgt]-$my[lft]>1)):
[sql:1:9b52cbd8af]SELECT * FROM tree WHERE lft = $my[lft]+$n[/sql:1:9b52cbd8af]

Pobrać nagłówki 120 postów z najnowszych wątków z forum o strukturze drzewiastej (tnąc w razie potrzeby wątki nie mieszczące się na stronie) :
[sql:1:9b52cbd8af]SELECT * FROM forum ORDER BY lft DESC LIMIT 120[/sql:1:9b52cbd8af]

Ze względu na prostotę działa hiper-super-szybko. Jedynym minusem jest użycie nieraz poprzedzającego zapytania (lub od razu inner joina), gdyż trzeba znać namiary rodzica (lft, rgt, depth) aby móc znaleźć jego dzieci.


--------------------
Gadu-Gadu: 3909164
Go to the top of the page
+Quote Post
rzseattle
post 26.04.2004, 21:30:32
Post #18





Grupa: Przyjaciele php.pl
Postów: 554
Pomógł: 0
Dołączył: 4.04.2002
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Pisalem ze ta klasa jest kompatybilna z ADODB (link w stopce forum), jesli natomiast z jakis przyczyn nie chce uzywac powyzszej klasy to prosze uzyc tej winksmiley.jpg
[php:1:2d6e60d161]<?php
class db{

var $debug =1;

function db(){

$conn = mysql_connect('localhost','root','root');

if (!$conn){
trigger_error ('[db] Nie mozna polaczyc z baza danych ', E_USER_ERROR);
exit();
}

mysql_select_db('trees');

}

//zwraca wynikz zapytania
function execute ( $query ){
if($this->debug) { print $query."nn"; }
$wynik = mysql_query( $query ) or ($this->error( $query, mysql_error()));
return $wynik;
}


// zwraca wynik w ktorym kazdy wiersz jest kolejnym indexem zwracanej tablicy
function getArray ( $query ) {
$r = $this->execute( $query );
if ($r != FALSE ){
while( $line = mysql_fetch_assoc( $r ) ){
$wynik[] = $line;
}
if( isset($wynik) && is_array($wynik)){
return $wynik;
}else{
return FALSE;
}
}else{
return FALSE;
}

}

// zwraca tablice w ktorej kazde pole jest indexem tablicy assocjacyjnej (zwraca tylko 1 wiersz)
function getRow ( $query )
{
$r = $this->execute( $query );
if ($r != FALSE ){
$line = mysql_fetch_assoc( $r ) ;
$wynik=$line;
return $wynik;
}else{
return FALSE;
}
}


function error( $query, $error ){
$query = nl2br($query);
$this->errStr[] = '<hr><table><tr><td><b>Query: </b>'.$query .'</td></tr><tr><td><b>Return Error: </b>'.mysql_error().'</td></tr></table><hr>';

$this->errorMsg();

return true;
}

function errorMsg(){
foreach($this->errStr as $error){
print $error;
}
return true;
}

}

?>[/php:1:2d6e60d161]

co prawda jest stara i wrecz troche zakurzona ale wystarczy.

Na marginesie dodam ze w przygotowaniu jest artykul o roziazanu usuwajacym wszelkie ograniczenia z tej implementacji (dzialajaaca klasa juz jest winksmiley.jpg ). Musze tylko znalezc odrobine wolnego czasu.

UPDATE
Moglbym przysiadz ze przed chwila tu byl post od kogos kto nie zazyl zkad sie wzielo $db


--------------------
"Real children don't go hoppity-skip unless they are on drugs."
Go to the top of the page
+Quote Post
itsme
post 27.04.2004, 06:06:44
Post #19





Grupa: Zarząd
Postów: 1 512
Pomógł: 2
Dołączył: 22.04.2002
Skąd: Koszalin




rowniez go widzialem prosze Moderatorów Wortal - Redakcja o info na PW kto go skasowal
Go to the top of the page
+Quote Post
DhuCerbin
post 27.04.2004, 21:47:10
Post #20





Grupa: Zarejestrowani
Postów: 14
Pomógł: 0
Dołączył: 10.06.2003

Ostrzeżenie: (0%)
-----


rzseattle : jaki masz sposób odczytu wszystkich rodziców w góre ?
Czyli z id win xp odczytać :
systemy operacyjne, windows, nt, win xp
?

ja jako zwolennik generacji zapytań troche topornie to zrobiłem i chciałbym sie dowiedzieć jak to robia inni. Oczywiscie wiem, ze trzeba zastepowac ostatnia liczbe =/= 0 zerem i pobierać, do momentu uzyskania 00000000. Ale jakim sposobem to robisz ?
Go to the top of the page
+Quote Post

3 Stron V   1 2 3 >
Reply to this topicStart new topic
1 Użytkowników czyta ten temat (1 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Wersja Lo-Fi Aktualny czas: 28.03.2024 - 22:53