defektologs.lv Par web izstrādes lietām

Rekursīva lapas karte

Tā nu ir sanācis, ka esmu mājaslapu izstrādātājs un šoreiz gribu padalīties ar kādu jauku algoritmu – lapas karte.

Sākumā apstāstīšu, ar ko esmu saskāries vairumā gadījumu. Liela daļa mājaslapu ir būvētas klasiskajā koka algoritmā, ko es atbalstu – id, parent_id. Šajā gadījumā tabula izskatīsies, aptuveni, šādi:

+----+-----------+----------+----------+
| id | parent_id | name     | position |
+----+-----------+----------+----------+
| 1  | 0         | Sākums   | 1        |
+----+-----------+----------+----------+
| 2  | 0         | Kontakti | 2        |
+----+-----------+----------+----------+
| 3  | 1         | Raksti   | 2        |
+----+-----------+----------+----------+
| 4  | 1         | Foto     | 1        |
+----+-----------+----------+----------+
| 5  | 2         | Karte    | 1        |
+----+-----------+----------+----------+

Funkcija, kuru izmanto veidojot rekursīvu lapas karti, uz šāda tipa datubāzes struktūras, visbiežāk izskatās šādi:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

<?  
  function sitemap($pid){
    $sql="SELECT id, name FROM `topics` WHERE parent_id=".intval($pid)." ORDER BY position ASC";
    $res=mysql_query($sql);
    if(mysql_num_rows($res)<1){
      return "";
    }
    $s='<ul>';
    while($row=mysql_fetch_object($res)){
      $s.='<li>';
      $s.=$row->name;
      $s.=sitemap($row->id);
      $s.='</li>';
    }
    $s.='</ul>';
    return $s;  	
  }       
  echo sitemap(0);
?>

Iedomājamies, ka ir tāda nopietnāka lapa, piemēram, ar 10 pirmā līmeņa sadaļām un katrai pirmā līmeņa sadaļai ir 5 apkšsadaļas. Cik pieprasījumi tiks sūtīti uz datubāzi?  1+10*5=26
Kapēc veidot 26 pieprasījumus, ja var iztikt ar vienu? Izmantosim sarežģītāku, taču ātrāku, algoritmu.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

<?
  function sitemap($pid,$arr){
    if(!is_array($arr[$pid])){
      return "";
    }
    $s='<ul>';
    foreach($arr[$pid] as $key=>$value){
      $s.='<li>';
      $s.=$value;
      $s.=sitemap($key,$arr);
      $s.='</li>';
    }
    $s.='</ul>';
    return $s;
  }
 
  $topics=array();
  $sql="SELECT id, parent_id, name FROM `topics` ORDER BY position ASC";
  $res=mysql_query($sql);
  while($row=mysql_fetch_object($res)){
    $topics[$row->parent_id][$row->id]=$row->name;
  }
  echo sitemap(0,$topics); 
?>

Testējot koda izpildes laiku (uz lēnas kastes, lai atšķirību vieglāk pamanīt), pirmā algoritma izpildes laiks bija ~ 0.77 sekundes, bet otrā ~ 0.015 sekundes. Atšķirība ir diezgan paliela, ņemot vērā, ka lapai, uz kuras tika veikts tests, nebija diezko daudz sadaļu.