세 가지 무한 분류 방식(반복, 재귀, 참조)
- 大家讲道理원래의
- 2017-04-16 14:11:124095검색
일반적인 분류 트리 구조는 두 가지가 있습니다.
하나는 인접 리스트(adjacency list)로 id와 parent id의 형태입니다.
다른 하나는 중첩된 set으로, 왼쪽 값과 오른쪽 값의 형태입니다.
왼쪽 및 오른쪽 값 형식쿼리가 더 효율적이고 재귀 등이 필요하지 않습니다. 권장되지만 그렇지 않습니다. pid 형식만큼 간단하고 직관적이며 다소 오래되었습니다. 지역과 유사한 데이터베이스의 구조 설계는 항상 pid 형식이었습니다(둘을 변환할 수 있는 알고리즘이 있는 것 같지만 저는 가지 않겠습니다. 세부적으로) 그렇습니다. . .
다음은 모두 인접 리스트 형식입니다. 테이블 은 id, pid, name 형식과 유사합니다.
일반적으로 이는 데이터베이스에서 모든 데이터를 읽은 다음 배열 을 조합하여 수행됩니다. 물론 재귀적일 때마다 데이터베이스를 쿼리할 수도 있지만 그렇게 됩니다. 데이터베이스에 압력을 가할 수 있으며 메서드로 캡슐화하기가 쉽지 않아 권장되지 않습니다.
현재 일반적으로 사용되는 세 가지 방법이 있습니다. 선택 드롭다운 메뉴 표시 스타일을 구현해 보겠습니다.
첫 번째는 가장 일반적으로 사용되는 방법입니다. 또한 가장 효율적이지 않은 방법입니다. foreachloop를 재귀적으로 유지하세요.
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. 두 번째 방법은 스택에 push하고 pop하는 재귀를 사용하여 계산하는 것보다 효율성이 좋습니다. 이전 버전이지만 속도도 상당히 느립니다. 프로세스는 먼저 배열을 뒤집은 다음 최상위 배열을 꺼내 스택에 푸시하고 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;
} 그런 다음 필요한 선택 드롭다운 메뉴를 재귀적으로 생성합니다. 위의 특수 형식으로 인해 재귀가 매우 빠릅니다.
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;
}
위 세 가지는 적은 양의 데이터에 적합하며 어느 것을 사용하든 상관없지만 대량의 데이터에는 효율성이 매우 분명합니다. 4000개의 지역 데이터를 사용한 테스트 결과:
첫 번째 방법(재귀)은 시간이 많이 걸립니다. : 약 8.9441471099854
두 번째 방법(반복) 약 6.7250330448151 소요
세 번째 방법(참조) 시간 소요: 0.028863906860352 왼쪽 및 오른쪽
가자, 이 틈, 세 번째 방법 정말 터무니없습니다. 하지만 이는 한 번에 많은 양의 데이터를 읽을 때만 해당되며, 데이터의 양이 매우 적을 때 그 차이가 가장 효율적일 필요는 없습니다. 지연 로딩과 같은 다른 방법을 통해.
클래스를 캡슐화하면 패딩 등을 추가할 수 있습니다. 자세한 내용은 다음 클래스에서 확인할 수 있습니다.
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 }
코드 보기
위 내용을 기록하고, 재인쇄할 경우 출처 주소를 명시해 주세요
위 내용은 세 가지 무한 분류 방식(반복, 재귀, 참조)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.