Drzewka w PHP [rzseattle] |
Drzewka w PHP [rzseattle] |
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 |
-------------------- |
|
|
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
|
|
|
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
BTW: trzy dni temu, to świętować było, a nie pracować -------------------- |
|
|
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%) |
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
-------------------- "Nie wiedziałem tylko, że Bóg też był na grzybach, gdy majstrował przy wszechświecie" (Janusz Wisniewski) dev: gazeta.ie |
|
|
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 . 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 -------------------- |
|
|
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++; } ?> |
|
|
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 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 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 |
|
|
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 .
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 ). @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."
|
|
|
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%) |
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 |
|
|
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 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 |
|
|
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."
|
|
|
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.
|
|
|
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:
czyli kod :
co do oznaczeń nie jestem pewien. |
|
|
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."
|
|
|
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
|
|
|
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."
|
|
|
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
|
|
|
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
[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 ). 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."
|
|
|
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
|
|
|
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 ? |
|
|
Wersja Lo-Fi | Aktualny czas: 27.09.2024 - 01:14 |