Проблема с таймаутом при обходе дерева страниц

[Кинотавр]

Проблема с таймаутом при обходе дерева страниц

Есть CMS. Структура страниц в ней древесная, у каждой страницы есть идентификатор родительской страницы. В админке выводится вся структура сайта, при помощи рекурсивной функции. Из базы данных страницы выдергиваются до обращения к рекурсивной функции, а в функции крутится только глобальный массив, содержащий некоторые нужные данные страниц (id, название и пр.). Массив крутится таким образом: каждое обращение к функции вызывает циклический перебор всех элементов массива (от 0 до max) с необходимыми проверками.
Все работало нормально, но один из сайтов разросся. Приблизительно при количестве страниц около 350 вышеописанная схема начинает валиться ошибкой maximum execition time 30 sec.
Прошу помочь разобрать ситуацию и дать идеи оптимизации алгоритма.
Спасибо.

 

[Romantik]

Увеличивать время, ИМХО. Оптимизация особо не спасет, если она изначально сделана правильно. Притом это админка.

 

[Макс]

насколько я знаю есть 2 вида рекурсивного обхода дерева.
1. выборка всего дерева в ПХП-массив и сортировка с помощью ПХП
2. построчно выбирается каждая запись (много SQL-запросов)

Какой вариант у тебя используется ?

 

[Кинотавр]

У меня используется первый вариант.
Чтобы разговор был более предметным, покажу куски кода.
Команды echo я из кода убрал, чтобы не мешали.

Первый фрагмент. Выборка страниц из базы данных, формирование массива страниц и цикл корневых обращений к рекурсивной функции.

$index = 0;

// id - идентификатор страницы, section - идентификатор родительской страницы (у корневых страниц он равен 0), title - название страницы
$result = mysql_query("SELECT id, section, title FROM pages ORDER BY id", $cid);

for ($i=0;$i<mysql_num_rows($result);$i++)
{
  $row = mysql_fetch_row($result);
      
// Заполняем массив всех страниц
  $page_array[$i][0] = $row[0];
  $page_array[$i][1] = $row[1];
  $page_array[$i][2] = $row[2];

// Заполняем массив корневых страниц
  if ($row[1]==0)
    $index_array[$index++] = $i;
}

// Прочесываем массив корневых страниц и вызываем рекурсивную функцию для каждой
for ($i=0;$i<count($index_array);$i++)
{
  $k = $index_array[$i];
  thread_list($k);  // Обращение к рекурсивной функции
}

Второй фрагмент. Рекурсивная функция.

function thread_list($a)
{
  GLOBAL $page_array;

  for ($i=0;$i<count($page_array);$i++)
  { 
    if ($page_array[$i][1]==$page_array[$a][0])
    { 
// Выводится название текущей страницы

      thread_list($i); // Новое рекурсивное обращение
    }
  }
}

Функция в целях понимания сокращена, из нее изъяты команды вывода строк. Вроде нигде затыков по производительности быть не должно.
Какие будут комментарии?

 

[Макс]

Хмм, с деревьями типа id->parent_id я не работал.
Есть такое предложение.
Создавать свой $page_array вида :

$page_array = array(
    "[section]"  => array(
                   [row1],
                    [row2],
     ),
//напрмиер
     "0" => array( // здесь список всех корневых страниц, у которых section == 0
          array(1, 0, 'title1'),
          array(2, 0, 'title2'),
      ),
      "1" => array ( // страницы для категории id = = 1
                array(3,1, "subdir  1"),
                array(4,1, "subdir 2"),
      ),
      "2" => array ( // страницы для категории id = = 2
                array(3,2, "subdir  3"),
                array(4,2, "subdir 4"),
      ),
);

это позволит избавится от перебора всех узлов в функции thread_list(). Например выводишь корневую страницу с id=1 , все ее подстраницы будут в массиве $page_array[1].
Все корневые страницы - в $page_array[0].
Идея ясна ?

-~{}~ 12.09.04 17:06:

кстати, можно попробовать оставить твой алгоритм, только добавить unset() для уже обработанных элементов

function thread_list($a)
{
  GLOBAL $page_array;

  for ($i=0;$i<count($page_array);$i++)
  {
    if ($page_array[$i][1]==$page_array[$a][0])
    {
// Выводится название текущей страницы

      unset($page_array[$i]); // <<<<<< 

      thread_list($i); // Новое рекурсивное обращение
    }
  }
}

 

[SergeR]

Раз там много страниц, то можно выводить не развернутое дерево, а только все узлы верхнего уровня + узлы раскрытой "ветки".

Если открытие/закрытие ветвей сделано на javascript'е, можно в отдельный файл вынести данные для javascript'a и обновлять этот файл только при добавлении нового узла.