首页 > > 网络编程 > Php编程 >

无限极分类（adjacency list）的三种方式（迭代…

2018-06-22 05:15:23来源：未知阅读 ()

一般的分类树状结构有两种方式：

一种是adjacency list，也就是是id，parent id这中形式。
另一种是nested set，即左右值的形式。

左右值形式查询起来比较高效，无需递归等，推荐使用，但是没有pid形式简单直观，而且有些旧的数据库类似地区等结构设计一直是pid这种形式（貌似也有算法可以将两者转换，不做深入了解），所以。。。

下面所说的都为adjacency list的形式，数据表格式类似id,pid,name这种格式。

通常来说是将数据全部从数据库读取后，然后再组装数组来实现，当然也可以每次递归等都查询数据库，但是会造成数据库压力，且不容易封装成方法，不建议这样做。

目前来说常用的有三种方式，我们来实现select下拉菜单展示的样式：

1、首先是最常用最普通，同样也是效率最低的递归方法：就是不停的foreach循环递归。

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);//销毁已查询的，减轻下次递归时查询数量
               $options =$options+ $optionsTmp;//用array_merge会导致索引重排
            }
        }
    }
    return $options;
}

2、第二种是利用入栈、出栈的递归来计算，效率比上个好点，但是也挺慢的。流程是先反转数组，然后取出顶级数组入栈，开始while循环，先出栈一个查找其下有没有子节点，如果有子节点，则将此子节点也入栈，下次while循环就会查子节点的，依次类推：

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;
}

3、利用引用来处理，这个真的很巧妙，而且效率最高，可参照这里，如果想看再详细的解释，可以查看这个问答。

/**
* 先生成类似下面的形式的数据
* [
*  '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;
}

然后再递归生成select下拉菜单所需要的，由于上方的特殊格式，导致递归起来非常快：

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);
                    $options =$options+ $optionsTmp;//用array_merge会导致索引重排
                }
            }
        }
    }
    return $options;
}

以上三种，对于数据量小的来说，无所谓用哪种，但是对于数据量大的来说就非常明显了，用4000条地区数据测试结果效率对比：

第一种方法（递归）耗时：8.9441471099854左右
第二种方法（迭代）耗时：6.7250330448151左右
第三种方法（引用）耗时：0.028863906860352左右

我去，这差距，第三种方法真是逆天了。但是再次提醒，这只是一次性读取多的数据的时候，当数据量很小的时候，相差无几，不一定非要用最高效率的，还可以通过懒加载等其他方式来实现。

顺便封装个类，可以增加一些填充什么的。更多的细节可以查看下面的类：

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