Drei Möglichkeiten der unendlichen Klassifizierung (Iteration, Rekursion, Referenz)

Es gibt zwei allgemeine Klassifizierungsbaumstrukturen:

• Eine davon ist die Adjazenzliste, die die Form von ID und Eltern-ID hat.

• Der andere ist ein verschachtelter Satz, der die Form der linken und rechten Werte darstellt.

Die linke und rechte WertformAbfrage ist effizienter und erfordert keine Rekursion usw. Es wird empfohlen, ist es aber nicht So einfach und intuitiv wie die PID-Form, und sie ist etwas alt. Das strukturelle Design von Datenbanken, die Regionen ähneln, hatte immer die Form von PID (es scheint, dass es Algorithmen gibt, die die beiden konvertieren können, aber ich werde nicht darauf eingehen ins Detail), so. . .

Die folgenden Daten liegen alle in Form einer Adjazenzliste vor. Die Datentabelle ähnelt dem Format von ID, PID und Name.

Im Allgemeinen wird dies erreicht, indem alle Daten aus der Datenbank gelesen und dann das

Array zusammengestellt werden. Natürlich können Sie die Datenbank auch jedes Mal abfragen, wenn sie rekursiv ist, aber das wird der Fall sein Datenbankdruck verursachen, und es ist nicht einfach, es in eine Methode zu kapseln, und wird nicht empfohlen.

Derzeit gibt es drei häufig verwendete Methoden. Wir implementieren den Anzeigestil „Auswahl“

: 1 auch die am wenigsten effiziente Methode: Halten Sie einfach die

foreach

Schleife rekursiv.

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. Die zweite Methode besteht darin, die Rekursion des Schiebens und Einfügens in den Stapel zum Berechnen zu verwenden, was mehr ist effizienter als das vorherige, aber auch ziemlich langsam. Der Prozess besteht darin, zuerst das Array umzukehren, dann das Array der obersten Ebene herauszunehmen und auf den Stapel zu schieben, die

while-Schleife

zu starten und zuerst einen vom Stapel zu entfernen, um herauszufinden, ob sich darunter ein untergeordneter Knoten befindet es, und wenn es einen untergeordneten Knoten gibt, schieben Sie diesen untergeordneten Knoten ebenfalls in den Stapel. Die nächste while-Schleife überprüft die untergeordneten Knoten und so weiter:

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. Verwenden Sie

, um

zu zitieren. Das ist wirklich clever und am effizientesten, Sie können sich hier darauf beziehen:

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

und dann rekursiv die Auswahl generieren. Das Dropdown-Menü erfordert aufgrund des oben genannten speziellen Formats eine sehr schnelle Rekursion:

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

Die oben genannten drei, für Bei einer kleinen Datenmenge spielt es keine Rolle, welche verwendet wird, bei einer großen Datenmenge ist dies jedoch sehr offensichtlich . Vergleich der Effizienz der Testergebnisse anhand von 4000 regionalen Daten:

Die erste Methode Die Methode (rekursiv) dauert etwa 8,9441471099854
Die Die zweite Methode (Iteration) dauert ungefähr 6,7250330448151
Die dritte Methode ( Zitat) Zeitverbrauch: ungefähr 0,028863906860352
Lass mich gehen, diese Lücke, Die dritte Methode ist wirklich unglaublich. Aber erinnern Sie mich noch einmal daran, dass dies nur dann der Fall ist, wenn die Datenmenge sehr gering ist. Sie müssen nicht die effizienteste verwenden Dies wird durch andere Methoden wie Lazy Loading erreicht.

Kapseln Sie übrigens eine Klasse und fügen Sie etwas Polsterung hinzu. Weitere Details finden Sie in den folgenden Kursen:

  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 }

Code anzeigen

Notieren Sie das Obige. Wenn Sie es erneut drucken, geben Sie bitte die Quelladresse an

Das obige ist der detaillierte Inhalt vonDrei Möglichkeiten der unendlichen Klassifizierung (Iteration, Rekursion, Referenz). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!