Algoritmus nested set elemek törlésére

Internet: PHP, CGI, stb.

Sziasztok!

Gondolkodtam az algoritmusok témán is, de mivel ez nyelvspecifikus, jobbnak láttam ide írni. Nested set törlésénél kellene PHP-ben az olyan számpárokat kiszűrnöm, amelyeknek a szülő kategóriája is ki van jelölve törlése. Tehát ha a szülő kategória ki van jelölve törlésre, akkor minden alkategóriája is törlésre fog kerülni, vagyis ezekre az alkategóriákra nincs szükség a listában. Egy példán keresztül bemutatom. A törlésre kijelölt kategóriák: 

2 3
4 7
5 6

Ezek a számpárok egy array-ban vannak: 

Array ( [0] => Array ( [lft] => 2 [rgt] => 3 ) [1] => Array ( [lft] => 4 [rgt] => 7 ) [2] => Array ( [lft] => 5 [rgt] => 6 ) )

Az alkategóriák eltávolítására (jelen példa esetén az 5 6 számpárra) kellene valami jó algoritmust találnom (tehát hogy az eredmény 2 3, 4 7 legyen).

Arra gondoltam, hogy először megvizsgálom foreach-ben, hogy az adott tömb elemének van-e alkategóriája (rgt - lft > 1), majd ha van akkor a tömbben megszüntetem azokat az elemeket, amelyeknek az lft-je nagyobb és az rgt-je kisebb az adott elem lft és rgt értékénél, de ehhez foreach-ben kellene futtatnom egy újabb foreach-et ugyanarra a tömbre, még ha referencia hivatkozással (foreach $rows as &$row) oldom meg, akkor se szép megoldás, és nem is a leggyorsabb.... Valakinek van jobb ötlete? Előre is köszönöm!

  • 1218 megtekintés

( zamboriz v | 2009. 08. 10., h – 13:33 )

> akkor se szép megoldás, és nem is a leggyorsabb

A gyorsabb megoldások általában bonyolultabbak és emiatt csúnyábbak is. Mi az, ami lassú?

3 elemű tömbnél nincs probléma, de pl. ha már 100 elemről van szó, akkor egy foreach a foreach-ben már eléggé lelassítja a feldolgozást. Nem próbáltam ki mennyire lassú, ha más nem lesz természetesen marad az említett megoldás, de nekem már az elgondolás sem igazán tetszik (foreach-ben futtatni egy másik foreach-et ismeretlen számú tömb esetén...), ezért keresek egy jobb módszert.

> Nem próbáltam ki mennyire lassú

Akkor próbáld ki. A végrehajtási időbe vedd bele az adatbázis update-eket is. Ha ez megvan, akkor ebből kiderül, hogy ha az optimalizálás 0 időt vesz igénybe, akkor hány százalékkal gyorsítható a művelet. [ 1- update/(optimalizálás+update) vagy valami ilyesmi ] Ha 1% alatti érték jön ki, akkor nem érdemes foglalkozni a dologgal :-)

> a PHP optimalizálás gyorsabbnak tűnik

Nálam ez kb 1 másodperc alatt fut le: 


$tomb = range(0,1000,1);

foreach ($tomb as &$a) {
  foreach ($tomb as &$b) {
    for( $i=0; $i<10; $i++ ){
      $a += $i;
    }
  }
}

100 elem helyett 1000 van, plusz még ott van belül egy 10-es ciklus. Szerintem esélytelen a dupla foreach-en nagyot fogni.

( Frantique v | 2009. 08. 10., h – 13:42 )

Milyen variánsok lehetségesek?
Van olyan főkategoria, amelynek több alkategóriája van? Stb.? Példák? Van pár módszer ugyanis... array_walk, array_walk_recursive, (<= ezeket nézd meg, meg fogsz lepődni) array_slice, stb.
--
Coding for fun. ;)

Feltöltöttem egy képet a szemléltetéshez. Tehát itt a kategóriák listája látható. A felhasználó jelölőnégyzetekkel kiválasztja a törlendő kategóriákat. Viszont pl. ha kijelöli a teszt 4-et és a teszt 5-öt is, akkor a teszt 5 felesleges a törlendő kategóriák listájában, mert a teszt 4 törlése miatt a teszt 5 is törlésre kerül (törlésnél egy adott kategória összes alkategóriája törlődik). Ezért szeretném elvégezni ezt az optimalizálást, mielőtt elindítanám a query-ket az adatbázis felé. Az említett függvényeket ismerem, segítségükkel meg tudok hívni egy függvényt, de arra szeretnék megoldást találni, hogy a függvényben hogyan távolítsam el a felesleges elemeket...

Egyelőre nem optimalizálom, mert nem az nem egyszerű... Egy adott kategória (és annak alkategóriáinak törlése) 4 lépésben történik: 

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'MP3 PLAYERS';

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;

Mivel az lft és rgt értékek átszámítása az adott (törlendő) kategória tartományának szélességétől függ, egyszerre csak egyet lehet törölni, ellenkező esetben teljesen felborulna az egész. Később még lehet, hogy fogom ezt a részt finomítani, de ahogy nézegettem nincs nagyon egyszerűbb megoldás, stored procedure-rel lehetne még talán egyszerűsíteni, de annak létrehozásához meg super privilégium kell, amit pedig sajnos nem várhatok el egy átlag felhasználótól...

Ejnye, ha idézel akkor illik megadni a forrást: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

> egyszerre csak egyet lehet törölni, ellenkező esetben teljesen felborulna az egész.

Lehet ott többet is, csak jól végig kell gondolni. Ha nagy a fa, akkor nyilván az update-eken lehetne a legtöbbet nyerni, nem a php-n. Az update-ek számán nem lehet megtakarítást elérni, de a hatókörükön, hogy egy rekord legfeljebb egyszer legyen update-elve, azon már lehetne. Persze kérdés, hogy megérné-e: programozói ráfordításban, és futásidő megtakarításban.

A kategóriák törlése adminisztrátori feladat (tehát az nem jön szóba, hogy sok a látogató és a sok query-től kiaakad a szerver), tovább a kategóriák egy weboldal esetén nem is változnak gyakran, egyszer elkészítik a kategória rendszert és utána már csak egyet-egyet hozzáadnak / törölnek. Tehát a query optimalizálásba nem mennék bele, mert szerintem nem éri meg az időráfordítást. Egy-egy kategória törlése nem jelentős, ha többről van szó, az meg ritkán történik meg és ezesetben még megengedhető egy kis többlet feldolgozási idő. Amit viszont el szeretnék kerülni, hogy pl. 100 kategória törlése esetén 4*100 query fusson le (beleértve még, hogy a két UPDATE hány sort módosít), mert lehet, hogy elég csak 5-10 felső szintű kategóriát törölni, ha a maradék 90-95 ezeknek az alkategóriája.

> elég csak 5-10 felső szintű kategóriát törölni, ha a maradék 90-95 ezeknek az alkategóriája.

Sorba kell rakni a törlendő kategóriákat, és először a legszélesebbeket kell törölni. A törlendő kategóriák listáját aktualizálni kell minden törlés után (hogy a lft és a rgt az új értékeket kapja), ekkor kiderül, hogy melyik kategória törlődött automatikusan a szülő törlődése miatt.