Оптимизация рекурсивной функции на php

_voland_ · 2010-09-13T12:15:34.0000000Z

Господа, имеем такую функцию function getAllCategories($id,&$data,&$arr1,&$arr2) { unset ($children); $j=count($arr2); for ($i=0;$i<$j;$i++) { if ($arr2[$i]==$id) $children[]=$arr1[$i]; } if (!empty($children)) { foreach ($children as $child) { $data[]=$child; getAllCategories($child,$data,$arr1,$arr2); }} } Здесь массивы $arr1 и $arr2 из 1400 записей содержат id категории и соответсвенно id родителя. Задача найти всех детей категорий, то есть без рекурсии тут никак (от 2 до 7 уровней). Скрипт выполняется для текущих параметров порядка 10 секунд, что очень много. Как можно ускорить данный участок кода?

456

[umka]

13 сентября 2010, 16:24

#11

_voland_:
В один проход вызывается от 2 до 10 функций рекурсивно.. глубино рекурсии до 7.

Верно, это дерево каталогов, данные хранятся в виде строк id, parent в каждой.
Пишу не с нуля, так что преобразовывать структуру - никак.

Я имел в виду общее количество итераций за один вызов скрипта.

Мне тоже кажется, что оно у вас работает подозрительно медленно.

Лог в помощь!

_

158

_voland_

13 сентября 2010, 16:36

#12

'[umka:
;7605641']Я имел в виду общее количество итераций за один вызов скрипта.
Мне тоже кажется, что оно у вас работает подозрительно медленно.

Ну в среднем 5 за раз, 7 рекурсий - итого 35 раз.. совсем не много..

Настраиваю напильником Joomla 1.5 (http://joomla15.ru) Если постоянно взламывают движок, достаточно сменить хостинг (http://2s4.ru/ytx) всем СРОЧНО (14 дек) обновлять или патчить joomla-сайты (/ru/forum/919351)

65

dvaes

13 сентября 2010, 16:47

#13

не может такого быть. чтоб оно выполнялось 10 секунд

D5

51

dk547

13 сентября 2010, 16:55

#14

_voland_:

Верно, это дерево каталогов, данные хранятся в виде строк id, parent в каждой.
Пишу не с нуля, так что преобразовывать структуру - никак.

Можно не менять структуру, но снизить сложность до 1 прохода по списку. Для этого правда нужно ввести отдельный индекс (сортированный список), в котором проиндексировать каждый каталог со списком всех своих чилдов, что-то типа:

categoryA, categoryB

categoryA, categoryC

categoryA, categoryD

..

Такой индекс можно рассчитывать заранее и хранить в отдельной таблице или еще как.

Имея дело с деревом adjacency list от рекурсии можно избавится только вот такими ухищрениями, которые имеют свою цену. Например, более сложное обновление каталогов.

Программирование сайтов (http://lindir.ru)

Новые тарифы Яндекс.Мастера избавят В Pr.Sape появились ускорение Три важных обновления в

_

158

_voland_

13 сентября 2010, 17:09

#15

В итоге, благодаря еще одному рецепту удалось снизить время выполнения до 0,2-0,6 сек (VDS 1700МГц)

_voland_ добавил 13.09.2010 в 21:11

dk547:
Можно не менять структуру, но снизить сложность до 1 прохода по списку. Для этого правда нужно ввести отдельный индекс (сортированный список), в котором проиндексировать каждый каталог со списком всех своих чилдов, что-то типа:

categoryA, categoryB
categoryA, categoryC
categoryA, categoryD
..

Такой индекс можно рассчитывать заранее и хранить в отдельной таблице или еще как.
Имея дело с деревом adjacency list от рекурсии можно избавится только вот такими ухищрениями, которые имеют свою цену. Например, более сложное обновление каталогов.

Спасиб, вариант, если каталог разрастется - придется использовать

Зачем быть уникальным в мире, где все можно скопировать

VK приобрела 70% в структуре компании-разработчика red_mad_robot