Как просмотреть дерево списка смежности с помощью цикла for (нерекурсивное решение) - PullRequest
Новая
       26

Как просмотреть дерево списка смежности с помощью цикла for (нерекурсивное решение)

0 голосов
/ 24 февраля 2012

Я сохраняю дерево в базе данных MySQL, используя метод списка смежности

, когда я хочу просмотреть дерево, PHP извлекает все дерево из базы данных и просматривает его, используя рекурсию.

Но итерации лучше, чем рекурсия в производительности, поэтому я хочу заполнить дерево, используя циклы for для достижения лучшей производительности.

Я не хочу использовать какие-либо функции MySQL, методы или триггеры, я просто хочу заполнитьдерево с использованием итераций (для циклов)

1 Ответ

0 голосов
/ 30 августа 2015

Я наткнулся на этот старый вопрос без ответа, когда искал ссылку на помощника в ответе на аналогичный вопрос в IRC.

Это грубый пример, показывающий, как построить список путей из списка смежности,это требует, чтобы данные были отсортированы по 'parent', а затем 'id', это может быть легко переведено в SQL SELECT с предложением ORDER BY parent, id: 

<?php
$arr = [
    ['id' => 1, 'parent' => 0],
    ['id' => 2, 'parent' => 1],
    ['id' => 3, 'parent' => 2], 
    ['id' => 4, 'parent' => 3], 
    ['id' => 5, 'parent' => 0],
    ['id' => 6, 'parent' => 5],
    ['id' => 7, 'parent' => 5], 
    ['id' => 8, 'parent' => 7],
    ['id' => 9, 'parent' => 8],
    ['id' => 10, 'parent' => 5],
    ['id' => 11, 'parent' => 0],
    ['id' => 12, 'parent' => 5],
    ['id' => 13, 'parent' => 5],
    ['id' => 14, 'parent' => 11],
    ['id' => 15, 'parent' => 13],
    ['id' => 16, 'parent' => 1],
    ['id' => 17, 'parent' => 15],
];

usort($arr, function($a, $b) { return $a['parent'] - $b['parent']?: $a['id'] - $b['id']; });

$paths = [];
foreach($arr as $current) {
    if($current['parent'] > 0) {
        $paths[ $current['id'] ] = array_merge($paths[ $current['parent'] ], [ $current['parent'] ]);
    } else {
        $paths[ $current['id'] ] = [];
    }
}

ksort($paths);
foreach($paths as $k => $v) {
    printf("%s => %s\n", $k, implode('/', array_merge($v, [ $k ])));
}

Вывод: 

1 => 1
2 => 1/2
3 => 1/2/3
4 => 1/2/3/4
5 => 5
6 => 5/6
7 => 5/7
8 => 5/7/8
9 => 5/7/8/9
10 => 5/10
11 => 11
12 => 5/12
13 => 5/13
14 => 11/14
15 => 5/13/15
16 => 1/16
17 => 5/13/15/17
...