Trois façons de classification infinie (itération, récursivité, référence)

Il existe deux structures arborescentes de classification générale :

• L'une est la liste de contiguïté, qui est la forme de l'identifiant et de l'identifiant parent.

• L'autre est imbriqué set, qui est la forme de valeurs gauche et droite.

La forme de valeur gauche et droiterequête est plus efficace et ne nécessite pas de récursion, etc. C'est recommandé, mais ce n'est pas le cas aussi simple et intuitif que la forme pid, et elle est un peu ancienne. La conception structurelle des bases de données similaires aux régions a toujours été sous la forme pid (il semble qu'il existe des algorithmes qui peuvent convertir les deux, mais je n'y vais pas. dans les détails), donc. . .

Les éléments suivants sont tous sous forme de liste de contiguïté. Les données tableau sont similaires au format id, pid, name.

De manière générale, cela est réalisé en lisant toutes les données de la base de données puis en assemblant le tableau Bien sûr, vous pouvez également interroger la base de données à chaque fois qu'elle est récursive, mais ce sera le cas. provoquer une pression sur la base de données, et il n'est pas facile à encapsuler dans une méthode et n'est pas recommandé.

Actuellement, il existe trois méthodes couramment utilisées. Implémentons le style d'affichage select menu déroulant :

1. aussi la moins efficace La méthode récursive : il suffit de garder foreachloop de manière récursive.

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

2 La deuxième méthode consiste à utiliser la récursion consistant à pousser et à insérer dans la pile pour calculer, ce qui est plus. efficace que le précédent, mais aussi assez lent. Le processus consiste d'abord à inverser le tableau, puis à retirer le tableau de niveau supérieur et à le pousser sur la pile, à démarrer la boucle while, à en extraire d'abord un de la pile pour trouver s'il y a un nœud enfant sous et s'il y a un nœud enfant, poussez également ce nœud enfant dans la pile. La boucle while suivante vérifiera les nœuds enfants, et ainsi de suite :

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. Utilisez

pour citer pour gérer, c'est vraiment astucieux et le plus efficace, vous pouvez vous référer ici :

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

puis générer récursivement la sélection. Le menu déroulant nécessite une récursion très rapidement en raison du format spécial ci-dessus :

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

Les trois ci-dessus, pour Pour une petite quantité de données, peu importe laquelle utiliser, mais pour une grande quantité de données, c'est très évident . La comparaison d'efficacité des résultats des tests en utilisant 4000 données régionales :

• La première méthode La méthode (récursive) prend environ 8,9441471099854

• La seconde La méthode (itération) prend environ 6,7250330448151

• La troisième méthode (Citation) Consommation de temps : environ 0,028863906860352

Laisse-moi partir, cet écart, le la troisième méthode est vraiment incroyable. Mais rappelez-moi encore une fois, ce n'est que lors de la lecture d'un grand nombre de données en même temps que lorsque la quantité de données est très faible, la différence est presque la même. Il n'est pas nécessaire que ce soit le plus efficace. d'autres méthodes telles que le chargement paresseux.

Encapsulez une classe en passant, vous pouvez ajouter un peu de remplissage ou quelque chose du genre. Plus de détails peuvent être trouvés dans les classes suivantes :

  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 }

Afficher le code

Enregistrez ce qui précède, si vous réimprimez, veuillez indiquer l'adresse source

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!