Three ways of infinite classification (iteration, recursion, reference)-PHP Tutorial-php.cn

Home

Backend Development

PHP Tutorial

Three ways of infinite classification (iteration, recursion, reference)

大家讲道理

Apr 16, 2017 pm 02:11 PM

There are two general classification tree structures:

One is the adjacency list, which is the form of id and parent id.
The other is nested set, which is the form of left and right values.

The left and right value formquery is more efficient and does not require recursion, etc. It is recommended to use, but it is not as simple and intuitive as the pid form, and some are old The structural design of databases similar to regions has always been in the form of pid (it seems that there are algorithms that can convert the two, but I won’t go into details), so. . .

The following are all in the form of adjacency list. The data table is similar to the format of id, pid, name.

Usually, this is achieved by reading all the data from the database and then assembling the array. Of course, you can also query the database every time you recurse, but it will cause database pressure, and It is not easy to encapsulate into a method and is not recommended.

Currently, there are three commonly used methods. Let’s implement the select drop-down menu display style:

1. The first is the most commonly used and common, and also the least efficient. The recursive method: just keep foreach looprecursion.

function getTreeOptions3($list, $pid = 0)
{    $options = [];    foreach ($list as $key => $value) {        if ($value['id'] == $pid) {//查看是否为子元素，如果是则递归继续查询
            $options[$value['id']] = $value['name'];            unset($list[$key]);//销毁已查询的，减轻下次递归时查询数量
            $optionsTmp = $this->getTreeOptions3($list, $value['id']);//递归
            if (!empty($optionsTmp)) {                $options = array_merge($options, $optionsTmp);
            }
        }
    }    return $options;
}

Copy after login

2. The second method is to use the recursion of pushing and popping into the stack to calculate. The efficiency is better than the previous one, but It's also quite slow. The process is to first reverse the array, then take out the top-level array and push it onto the stack, start the while loop, first pop one out of the stack to find if there is a child node under it, and if there is a child node, push this child node into the stack as well. The next while loop will check the child nodes, and so on:

function getTreeOptions2($list, $pid = 0)
{    $tree = [];    if (!empty($list)) {        //先将数组反转，因为后期出栈时会优先出最上面的
        $list = array_reverse($list);        //先取出顶级的来压入数组$stack中，并将在$list中的删除掉
        $stack = [];        foreach ($list as $key => $value) {            if ($value['pid'] == $pid) {                array_push($stack,$value);                unset($list[$key]);
            }
        }        while (count($stack)) {            //先从栈中取出第一项
            $info = array_pop($stack);            //查询剩余的$list中pid与其id相等的，也就是查找其子节点
            foreach ($list as $key => $child) {                if ($child[pid] == $info['id']) {                    //如果有子节点则入栈，while循环中会继续查找子节点的下级
                    array_push($stack,  $child);                    unset($list[$key]);
                }
            }            //组装成下拉菜单格式
            $tree[$info['id']] = $info['name'];
        }
    }    return $tree;
}

Copy after login

3. Use to quote Processing, this is really clever and the most efficient, you can refer to here:

/**
* 先生成类似下面的形式的数据
* [
*  'id'=>1,
*  'pid'=>0,
*  'items'=>[
*      'id'=>2,
*      'pid'=>'1'
*       。。。
*  ]
* ]*/function getTree($list, $pid = 0)
{    $tree = [];    if (!empty($list)) {        //先修改为以id为下标的列表
        $newList = [];        foreach ($list as $k => $v) {            $newList[$v['id']] = $v;
        }        //然后开始组装成特殊格式
        foreach ($newList as $value) {            if ($pid == $value['pid']) {//先取出顶级
                $tree[] = &$newList[$value['id']];
            } elseif (isset($newList[$value['pid']])) {//再判定非顶级的pid是否存在，如果存在，则再pid所在的数组下面加入一个字段items，来将本身存进去
                $newList[$value['pid']]['items'][] = &$newList[$value['id']];
            }
        }
    }    return $tree;
}

Copy after login

Then recursively generate the select drop-down menu required , due to the special format above, the recursion is very fast:

function formatTree($tree)
{    $options = [];    if (!empty($tree)) {        foreach ($tree as $key => $value) {            $options[$value['id']] = $value['name'];            if (isset($value['items'])) {//查询是否有子节点
                $optionsTmp = $this->formatTree($value['items']);                if (!empty($optionsTmp)) {                    $options = array_merge($options, $optionsTmp);
                }
            }
        }
    }    return $options;
}

Copy after login

The above three are suitable for small amounts of data. , it doesn’t matter which one is used, but it is very obvious for large amounts of data. Efficiency comparison of test results using 4000 regional data:

The first method (recursive) is time-consuming : About 8.9441471099854
The second method (iteration) takes about 6.7250330448151
The third method (reference) takes time: 0.028863906860352 Left and right

Let me go, this gap, the third method is really outrageous. But remind me again, this is only when reading a lot of data at one time. When the amount of data is very small, the difference is almost the same. You don’t have to use the most efficient one. It can also be achieved through other methods such as lazy loading.

Encapsulate a class by the way, you can add some padding or something. More details can be found in the following classes:

1 <?php 2 /** 3 * parent_id类型树结构相关 4 * 没必要非要写成静态的方法，静态方法参数太多，所以用实例在构造函数中修改参数更合适 5 * 需要首先将所有数据取出，然后再用此方法重新规划数组，其它的边取边查询数据库的方法不推荐 6 * 经测试第一种方法要快很多，建议使用 7 * @author vishun <nadirvishun@gmail.com> 8 */ 9 10 class Tree 11 { 12 /** 13 * 图标 14 */ 15 public $icon = '└'; 16 /** 17 * 填充 18 */ 19 public $blank = ' '; 20 /** 21 * 默认ID字段名称 22 */ 23 public $idName = 'id'; 24 /** 25 * 默认PID字段名称 26 */ 27 public $pidName = 'pid'; 28 /** 29 * 默认名称字段名称 30 */ 31 public $titleName = 'name'; 32 /** 33 * 默认子元素字段名称 34 */ 35 public $childrenName = 'items'; 36 37 /** 38 * 构造函数，可覆盖默认字段值 39 * @param array $config 40 */ 41 function construct($config = []) 42 { 43 if (!empty($config)) { 44 foreach ($config as $name => $value) { 45 $this->$name = $value; 46 } 47 } 48 } 49 50 /** 51 * 生成下拉菜单可用树列表的方法 52 * 经测试4000条地区数据耗时0.02左右，比另外两种方法快超级多 53 * 流程是先通过引用方法来生成一种特殊树结构，再通过递归来解析这种特殊的结构 54 * @param array $list 55 * @param int $pid 56 * @param int $level 57 * @return array 58 */ 59 public function getTreeOptions($list, $pid = 0, $level = 0) 60 { 61 //先生成特殊规格的树 62 $tree = $this->getTree($list, $pid); 63 //再组装成select需要的形式 64 return $this->formatTree($tree, $level); 65 } 66 67 /** 68 * 通过递归来解析特殊的树结构来组装成下拉菜单所需要的样式 69 * @param array $tree 特殊规格的数组 70 * @param int $level 71 * @return array 72 */ 73 protected function formatTree($tree, $level = 0) 74 { 75 $options = []; 76 if (!empty($tree)) { 77 $blankStr = str_repeat($this->blank, $level) . $this->icon; 78 if ($level == 0) {//第一次无需有图标及空格 79 $blankStr = ''; 80 } 81 foreach ($tree as $key => $value) { 82 $options[$value[$this->idName]] = $blankStr . $value[$this->titleName]; 83 if (isset($value[$this->childrenName])) {//查询是否有子节点 84 $optionsTmp = $this->formatTree($value[$this->childrenName], $level + 1); 85 if (!empty($optionsTmp)) { 86 $options = array_merge($options, $optionsTmp); 87 } 88 } 89 } 90 } 91 return $options; 92 } 93 94 /** 95 * 生成类似下种格式的树结构 96 * 利用了引用&来实现，参照：http://blog.csdn.net/gxdvip/article/details/24434801 97 * [ 98 * 'id'=>1, 99 * 'pid'=>0,100 * 'items'=>[101 * 'id'=>2,102 * 'pid'=>'1'103 * 。。。104 * ]105 * ]106 * @param array $list107 * @param int $pid108 * @return array109 */110 protected function getTree($list, $pid = 0)111 {112 $tree = [];113 if (!empty($list)) {114 //先修改为以id为下标的列表115 $newList = [];116 foreach ($list as $k => $v) {117 $newList[$v[$this->idName]] = $v;118 }119 //然后开始组装成特殊格式120 foreach ($newList as $value) {121 if ($pid == $value[$this->pidName]) {122 $tree[] = &$newList[$value[$this->idName]];123 } elseif (isset($newList[$value[$this->pidName]])) {124 $newList[$value[$this->pidName]][$this->childrenName][] = &$newList[$value[$this->idName]];125 }126 }127 }128 return $tree;129 }130 131 /**132 * 第二种方法，利用出入栈迭代来实现133 * 经测试4000条地区数据耗时6.5s左右，比较慢134 * @param $list135 * @param int $pid136 * @param int $level137 * @return array138 */139 public function getTreeOptions2($list, $pid = 0, $level = 0)140 {141 $tree = [];142 if (!empty($list)) {143 144 //先将数组反转，因为后期出栈时会有限出最上面的145 $list = array_reverse($list);146 //先取出顶级的来压入数组$stack中，并将在$list中的删除掉147 $stack = [];148 foreach ($list as $key => $value) {149 if ($value[$this->pidName] == $pid) {150 array_push($stack, ['data' => $value, 'level' => $level]);//将层级记录下来，方便填充空格151 unset($list[$key]);152 }153 }154 while (count($stack)) {155 //先从栈中取出第一项156 $info = array_pop($stack);157 //查询剩余的$list中pid与其id相等的，也就是查找其子节点158 foreach ($list as $key => $child) {159 if ($child[$this->pidName] == $info['data'][$this->idName]) {160 //如果有子节点则入栈，while循环中会继续查找子节点的下级161 array_push($stack, ['data' => $child, 'level' => $info['level'] + 1]);162 unset($list[$key]);163 }164 }165 //组装成下拉菜单格式166 $blankStr = str_repeat($this->blank, $info['level']) . $this->icon;167 if ($info['level'] == 0) {//第一次无需有图标及空格168 $blankStr = '';169 }170 $tree[$info['data'][$this->idName]] = $blankStr . $info['data'][$this->titleName];171 }172 }173 return $tree;174 }175 176 /**177 * 第三种普通列表转为下拉菜单可用的树列表178 * 经测试4000条地区数据耗时8.7s左右，最慢179 * @param array $list 原数组180 * @param int $pid 起始pid181 * @param int $level 起始层级182 * @return array183 */184 public function getTreeOptions3($list, $pid = 0, $level = 0)185 {186 $options = [];187 if (!empty($list)) {188 $blankStr = str_repeat($this->blank, $level) . $this->icon;189 if ($level == 0) {//第一次无需有图标及空格190 $blankStr = '';191 }192 foreach ($list as $key => $value) {193 if ($value[$this->pidName] == $pid) {194 $options[$value[$this->idName]] = $blankStr . $value[$this->titleName];195 unset($list[$key]);//销毁已查询的，减轻下次递归时查询数量196 $optionsTmp = $this->getTreeOptions3($list, $value[$this->idName], $level + 1);//递归197 if (!empty($optionsTmp)) {198 $options = array_merge($options, $optionsTmp);199 }200 }201 }202 }203 return $options;204 }205 }

Copy after login

View Code

Record the above, if you reprint, please indicate the source address

The above is the detailed content of Three ways of infinite classification (iteration, recursion, reference). For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress images for free

Clothoff.io

AI clothes remover

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

What's New in Windows 11 KB5054979 & How to Fix Update Issues

1 months ago By DDD

How to fix KB5055523 fails to install in Windows 11?

3 weeks ago By DDD

How to fix KB5055518 fails to install in Windows 10?

3 weeks ago By DDD

Strength Levels for Every Enemy & Monster in R.E.P.O.

3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Blue Prince: How To Get To The Basement

3 weeks ago By DDD

Hot Tools

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial

1653

CakePHP Tutorial

1413

Laravel Tutorial

1304

PHP Tutorial

1251

C# Tutorial

1224

Related knowledge

Recursive implementation of C++ functions: Is there a limit to recursion depth? Apr 23, 2024 am 09:30 AM

The recursion depth of C++ functions is limited, and exceeding this limit will result in a stack overflow error. The limit value varies between systems and compilers, but is usually between 1,000 and 10,000. Solutions include: 1. Tail recursion optimization; 2. Tail call; 3. Iterative implementation.

Do C++ lambda expressions support recursion? Apr 17, 2024 pm 09:06 PM

Yes, C++ Lambda expressions can support recursion by using std::function: Use std::function to capture a reference to a Lambda expression. With a captured reference, a Lambda expression can call itself recursively.

How to use block quotes in Apple Notes Oct 12, 2023 pm 11:49 PM

In iOS 17 and macOS Sonoma, Apple has added new formatting options for Apple Notes, including block quotes and a new Monostyle style. Here's how to use them. With additional formatting options in Apple Notes, you can now add block quotes to your notes. The block quote format makes it easy to visually offset sections of writing using the quote bar to the left of the text. Just tap/click the "Aa" format button and select the block quote option before typing or when you are on the line you want to convert to a block quote. This option applies to all text types, style options, and lists, including checklists. In the same Format menu you can find the new Single Style option. This is a revision of the previous "equal-width"

Count the number of occurrences of a substring recursively in Java Sep 17, 2023 pm 07:49 PM

Given two strings str_1 and str_2. The goal is to count the number of occurrences of substring str2 in string str1 using a recursive procedure. A recursive function is a function that calls itself within its definition. If str1 is "Iknowthatyouknowthatiknow" and str2 is "know" the number of occurrences is -3. Let us understand through examples. For example, input str1="TPisTPareTPamTP", str2="TP"; output Countofoccurrencesofasubstringrecursi

Recursive implementation of C++ functions: Comparative analysis of recursive and non-recursive algorithms? Apr 22, 2024 pm 03:18 PM

The recursive algorithm solves structured problems through function self-calling. The advantage is that it is simple and easy to understand, but the disadvantage is that it is less efficient and may cause stack overflow. The non-recursive algorithm avoids recursion by explicitly managing the stack data structure. The advantage is that it is more efficient and avoids the stack. Overflow, the disadvantage is that the code may be more complex. The choice of recursive or non-recursive depends on the problem and the specific constraints of the implementation.

C++ Recursion Advanced: Understanding Tail Recursion Optimization and Its Application Apr 30, 2024 am 10:45 AM

Tail recursion optimization (TRO) improves the efficiency of certain recursive calls. It converts tail-recursive calls into jump instructions and saves the context state in registers instead of on the stack, thereby eliminating extra calls and return operations to the stack and improving algorithm efficiency. Using TRO, we can optimize tail recursive functions (such as factorial calculations). By replacing the tail recursive call with a goto statement, the compiler will convert the goto jump into TRO and optimize the execution of the recursive algorithm.

What are the benefits of C++ functions returning reference types? Apr 20, 2024 pm 09:12 PM

The benefits of functions returning reference types in C++ include: Performance improvements: Passing by reference avoids object copying, thus saving memory and time. Direct modification: The caller can directly modify the returned reference object without reassigning it. Code simplicity: Passing by reference simplifies the code and requires no additional assignment operations.

Detailed explanation of C++ function recursion: application of recursion in string processing Apr 30, 2024 am 10:30 AM

A recursive function is a technique that calls itself repeatedly to solve a problem in string processing. It requires a termination condition to prevent infinite recursion. Recursion is widely used in operations such as string reversal and palindrome checking.

See all articles