0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Однажды я обнаружил очень интересную особенность развития современных web-программистов. Мы смело оперируем фабриками, синглтонами и декораторами, но забываем о такой фундаментальной части программирования, как<strong>классические алгоритмы</strong>. Ведь если присмотреться к их реализации, то это тоже своего рода паттерны. С институтской скамьи можно вспомнить, к примеру, nested sets, b-tree, сортировку "пузырьком". Реализация многих алгоритмов давно устоялась. А потому, я хотел бы посвятить несколько статей алгоритмам и их применении в PHP.</p>
1
<p>Однажды я обнаружил очень интересную особенность развития современных web-программистов. Мы смело оперируем фабриками, синглтонами и декораторами, но забываем о такой фундаментальной части программирования, как<strong>классические алгоритмы</strong>. Ведь если присмотреться к их реализации, то это тоже своего рода паттерны. С институтской скамьи можно вспомнить, к примеру, nested sets, b-tree, сортировку "пузырьком". Реализация многих алгоритмов давно устоялась. А потому, я хотел бы посвятить несколько статей алгоритмам и их применении в PHP.</p>
2
<p>Начну я с самого простого -<strong>построения древовидной иерархии</strong>.</p>
2
<p>Начну я с самого простого -<strong>построения древовидной иерархии</strong>.</p>
3
<p>Казалось бы, что тут сложного? В базе данных есть таблица примерно следующего содержания:</p>
3
<p>Казалось бы, что тут сложного? В базе данных есть таблица примерно следующего содержания:</p>
4
<p>Необходимо представить этот массив в виде древовидного меню. Я не буду говорить о том, какими неправильными способами можно решить эту задачу =)</p>
4
<p>Необходимо представить этот массив в виде древовидного меню. Я не буду говорить о том, какими неправильными способами можно решить эту задачу =)</p>
5
<p>Единственно верный подход в данном случае -<strong>рекурсивный метод</strong>.</p>
5
<p>Единственно верный подход в данном случае -<strong>рекурсивный метод</strong>.</p>
6
<p>Алгоритм (паттерн, если так хотите) будет примерно следующим: 0. Создаем объект дерева и выбираем все элементы в таблице. 1. Вызываем метод построения. Он инициализирует сборку массива родительских категорий. Именно этот момент является ноу-хау данного алгоритма. Он позволяет нам организовать изящную рекурсию. 2. Итеративно обходим массив, начиная с нулевого элемента. Выводим информацию о текущем элементе. 3. Увеличиваем уровень погружения. Рекурсивно вызываем метод для дочернего элемента. Если он есть в массиве родительских категорий, то идем к шагу 2, иначе - выходим в шаг-инициализатор. 4. Уменьшаем уровень погружения. Выходим из итерации.</p>
6
<p>Алгоритм (паттерн, если так хотите) будет примерно следующим: 0. Создаем объект дерева и выбираем все элементы в таблице. 1. Вызываем метод построения. Он инициализирует сборку массива родительских категорий. Именно этот момент является ноу-хау данного алгоритма. Он позволяет нам организовать изящную рекурсию. 2. Итеративно обходим массив, начиная с нулевого элемента. Выводим информацию о текущем элементе. 3. Увеличиваем уровень погружения. Рекурсивно вызываем метод для дочернего элемента. Если он есть в массиве родительских категорий, то идем к шагу 2, иначе - выходим в шаг-инициализатор. 4. Уменьшаем уровень погружения. Выходим из итерации.</p>
7
<p>Итак, метод сборки массива категорий будет выглядеть примерно вот так</p>
7
<p>Итак, метод сборки массива категорий будет выглядеть примерно вот так</p>
8
private function getCategoryArray() { $query = $this->db_connect->prepare("SELECT * FROM tree_table"); $query->execute(); $result = $query->fetchAll(PDO::FETCH_OBJ); $category_array = array(); foreach ($result as $value) { $category_array[$value->id_parent][] = $value; } return $category_array; }<p>Далее напишем наш рекурсивный метод в соответствии с приведенным выше алгоритмом:</p>
8
private function getCategoryArray() { $query = $this->db_connect->prepare("SELECT * FROM tree_table"); $query->execute(); $result = $query->fetchAll(PDO::FETCH_OBJ); $category_array = array(); foreach ($result as $value) { $category_array[$value->id_parent][] = $value; } return $category_array; }<p>Далее напишем наш рекурсивный метод в соответствии с приведенным выше алгоритмом:</p>
9
public function buildTree($parent_id, $tree_level) { if (isset($this->category[$parent_id])) { foreach ($this->category[$parent_id] as $value) { echo " " . $value->id_tree_test . " : " . $value->title . " "; $tree_level++; $this->buildTree($value->id_tree_test, $tree_level); $tree_level--; } } }<p>Теперь можем вызвать построение дерева, начиная с нулевого элемента и нулевого уровня. Замечу, что приведенный метод может вызывать построение с любой вложенной ноды и не ограничен по глубине.</p>
9
public function buildTree($parent_id, $tree_level) { if (isset($this->category[$parent_id])) { foreach ($this->category[$parent_id] as $value) { echo " " . $value->id_tree_test . " : " . $value->title . " "; $tree_level++; $this->buildTree($value->id_tree_test, $tree_level); $tree_level--; } } }<p>Теперь можем вызвать построение дерева, начиная с нулевого элемента и нулевого уровня. Замечу, что приведенный метод может вызывать построение с любой вложенной ноды и не ограничен по глубине.</p>
10
$tree = new Tree(); $tree->buildTree(0, 0);<p>А вот как будет выглядеть наше дерево в итоге:</p>
10
$tree = new Tree(); $tree->buildTree(0, 0);<p>А вот как будет выглядеть наше дерево в итоге:</p>
11
<?php class Tree { private $db_connect = null; public $category = array(); public $tree = array(); public function __construct() { # $this->db_connect = new PDO("mysql:dbname=devenergru_drup1;host=localhost", "devenergru_drup1", "weduucixwa"); $this->category = $this->getCategoryArray(); } private function getCategoryArray() { $category_array = [ 0 => [ [ 'id_tree_test' => 2, 'id_parent' => 0, 'title' => "Два" ] ], 1 => [ [ 'id_tree_test' => 4, 'id_parent' => 1, 'title' => "Четыре" ] ], 2 => [ [ 'id_tree_test' => 1, 'id_parent' => 2, 'title' => "Один" ], [ 'id_tree_test' => 5, 'id_parent' => 2, 'title' => "Пять" ] ], 4 => [ [ 'id_tree_test' => 3, 'id_parent' => 4, 'title' => "Три" ] ] ]; return $category_array; } public function buildTree($parent_id, $level) { if (isset($this->category[$parent_id])) { foreach ($this->category[$parent_id] as $value) { echo "<div style=\"margin-left:" . ($level * 25) . "px;\">" . $value["id_tree_test"] . " : " . $value["title"] . "</div>"; $level++; $this->buildTree($value["id_tree_test"], $level); $level--; } } } } $tree = new Tree(); $tree->buildTree(0, 0); ?><p>Данный метод применим при построении меню на сайте, каталогов продукции и т. п. У него, разумеется, есть недостатки. При построении достаточно большого каталога метод будет работать довольно долго. Но выигрыш тут в том, что<strong>метод можно модифицировать</strong>и ограничить не только уровнем входа, но и уровнем погружения. Таким образом, можно достраивать дерево постепенно при запросе пользователей, что решит данную проблему.</p>
11
<?php class Tree { private $db_connect = null; public $category = array(); public $tree = array(); public function __construct() { # $this->db_connect = new PDO("mysql:dbname=devenergru_drup1;host=localhost", "devenergru_drup1", "weduucixwa"); $this->category = $this->getCategoryArray(); } private function getCategoryArray() { $category_array = [ 0 => [ [ 'id_tree_test' => 2, 'id_parent' => 0, 'title' => "Два" ] ], 1 => [ [ 'id_tree_test' => 4, 'id_parent' => 1, 'title' => "Четыре" ] ], 2 => [ [ 'id_tree_test' => 1, 'id_parent' => 2, 'title' => "Один" ], [ 'id_tree_test' => 5, 'id_parent' => 2, 'title' => "Пять" ] ], 4 => [ [ 'id_tree_test' => 3, 'id_parent' => 4, 'title' => "Три" ] ] ]; return $category_array; } public function buildTree($parent_id, $level) { if (isset($this->category[$parent_id])) { foreach ($this->category[$parent_id] as $value) { echo "<div style=\"margin-left:" . ($level * 25) . "px;\">" . $value["id_tree_test"] . " : " . $value["title"] . "</div>"; $level++; $this->buildTree($value["id_tree_test"], $level); $level--; } } } } $tree = new Tree(); $tree->buildTree(0, 0); ?><p>Данный метод применим при построении меню на сайте, каталогов продукции и т. п. У него, разумеется, есть недостатки. При построении достаточно большого каталога метод будет работать довольно долго. Но выигрыш тут в том, что<strong>метод можно модифицировать</strong>и ограничить не только уровнем входа, но и уровнем погружения. Таким образом, можно достраивать дерево постепенно при запросе пользователей, что решит данную проблему.</p>
12
<p>Я не рассматриваю здесь проблемы хранения такой структуры, т. к. нас сейчас интересует только обход массива.</p>
12
<p>Я не рассматриваю здесь проблемы хранения такой структуры, т. к. нас сейчас интересует только обход массива.</p>
13
<p>За сим все! Безошибочного вам кода!</p>
13
<p>За сим все! Безошибочного вам кода!</p>
14
14