無限分類の 3 つの方法 (反復、再帰、参照)

一般的な分類ツリー構造は 2 つあります:

• 1 つは隣接リストで、ID と親 ID の形式です。

• もう 1 つはネストされた set で、左右の値の形式です。

左右の値フォームクエリはより効率的であり、再帰などを必要としません。使用することをお勧めしますが、pidフォームほど単純で直感的ではなく、一部の古いデータベースは似ています。構造設計は常に pid 形式になっています (詳しく説明せずに 2 つを変換できるアルゴリズムもあるようです)。 。 。

以下はすべて隣接リストの形式です。データ table の形式は、id、pid、name の形式に似ています。

通常、これはデータベースからすべてのデータを読み取り、配列を組み立てることによって実現されます。もちろん、再帰ごとにデータベースにクエリを実行することもできますが、データベースに負荷がかかるため、そうではありません。メソッドにカプセル化するのが簡単です。この方法はお勧めしません。

現在、よく使用されるメソッドが 3 つあります。selectdrop-down menu:

1 の表示スタイルを実装しましょう。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);
            }
        }
    }    return $options;
}

2. 2 番目の方法は、スタックへのプッシュとポップの再帰を使用して計算することです。効率は前の方法よりも優れていますが、かなり遅いです。このプロセスでは、まず配列を反転し、次に最上位の配列を取り出してスタックにプッシュし、while ループを開始し、最初にスタックから 1 つをポップして、その下に子ノードがあるかどうかを確認します。が子ノードである場合、この子ノードをスタックにプッシュし、次の 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. quote を使用して処理します。これは非常に賢く、最も効率的です。ここを参照してください:

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

その後、選択ドロップダウン メニューに必要なものを再帰的に生成します。このため、再帰は非常に高速です。 :

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

上記の 3 つは、少量のデータの場合はどちらを使用しても問題ありませんが、4000 の地域データを使用したテスト結果の効率の比較は非常に明白です。 :

• 最初の方法(再帰)は約8.9441471099854かかります

• 2番目の方法(反復)時間は約6.7250330448151

• 3番目の方法(引用)時間は約0.02 8863906860352

させてください行ってください、このギャップ、3 番目の方法は本当に信じられないほどです。ただし、これは一度に大量のデータを読み取る場合に限り、その差が最も効率的である必要はありません。遅延読み込みなどの他の方法を使用します。

ところで、クラスをカプセル化し、パディングを追加します。詳細については、次のカテゴリを参照してください:

  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 }

コードを表示

転載する場合は、ソースアドレスを明記してください

。

以上が無限分類の 3 つの方法 (反復、再帰、参照)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。