算相邻数组中的元素 [英] Count elements in adjacent array
问题描述
我有具有分层结构的阵列。在本实施例中有第一级的两个元素，83和82。82有子84和87。 87是84的子
阵列
（
[_children] =＆GT;排列
（
[0] =＆GT;排列
（
[ID] =＆GT; 11
[UID] =＆GT; 24
[摆脱] =＆GT; 83
[日期] =＆GT; 2011-06-18 15点08分10秒
） [1] =＆GT;排列
（
[ID] =＆GT; 10
[UID] =＆GT; 24
[摆脱] =＆GT; 82
[日期] =＆GT; 2011-06-18 15点08分07秒
[_children] =＆GT;排列
（
[0] =＆GT;排列
（
[ID] =＆GT; 12
[UID] =＆GT; 82
[摆脱] =＆GT; 84
[日期] =＆GT; 2011-06-18十五时三十分34秒
[_children] =＆GT;排列
（
[0] =＆GT;排列
（
[ID] =＆GT; 13
[UID] =＆GT; 84
[摆脱] =＆GT; 87
[日期] =＆GT; 2011-06-18十六时十一分50秒
） ） ） ） ） ））
我想通过数组循环和存储在另一个阵列中的每个级别的一些信息。这是我的数组应该怎么看起来像在最后。
阵列
（
[0] =＆GT;排列
（
[内容] =＆GT; 2
） [1] =＆GT;排列
（
[内容] =＆GT; 1
） ）
例如。这表明，在0级有3个节点和1级有5个节点。我该怎么办呢？任何想法？
我只算数字。
这意味着基本密钥的每一个项目，加上同样为它的孩子。
在对面的递归，我决定用一个栈这一点。
要具有每级的值，计数器需要一个水平上下文为好，这是添加到堆栈旁边的节点
$计数=阵列（）;
$堆叠[] =阵列（-1，$ ARR）;
而（$项目= array_shift（$堆栈））{
列表（$级，$节点）= $项目;
$计数[$级别] =使用isset（$计数[$级别]）？ $计数[$级别] +1：1;
如果（！使用isset（$节点['_儿童']））
继续;
的foreach（$节点['_儿童]为$项）
$堆叠[] =阵列（$级别+ 1，$项目）;
}
后续代码var_dump（$数）;
这确实输出：
阵列（4）{
[-1] =＆GT; INT（1）
[0] =＆GT; INT（2）
[1] =＆GT; INT（1）
[2] =＆GT; INT（1）
}
其中， 1 仅包含儿童根节点。所以，你可能希望处理之后将其删除：
array_shift（$数）;
编辑：存储在节点
以下code增加每级节点的收藏家，以及被称为 $节点。这是一个有点多余的，因为每计数（$节点[$级别]）是 $计数[$级别] ，但它只是说明如何收集节点以及
$计数=阵列（）;
$节点=阵列（）; //每级节点去这里。
$堆叠[] =阵列（-1，$ ARR）;
而（$项目= array_shift（$堆栈））{
列表（$级，$节点）= $项目;
$计数[$级别] =使用isset（$计数[$级别]）？ $计数[$级别] +1：1;
$节点[$级别] [] = $节点; //这里设置！
如果（！使用isset（$节点['_儿童']））
继续;
的foreach（$节点['_儿童]为$项）
$堆叠[] =阵列（$级别+ 1，$项目）;
}
后续代码var_dump（$计数，$节点）;
讨论
使用堆栈prevents进行递归函数调用和降低复杂性。其背后的想法是很简单的：
- 堆栈初始化与所述第一节点（其仅包含儿童） - 树的根节点
- 在堆栈中的条目包含要计算节点和它的水平
- 在堆栈中的每个元素都被视为是相同的：
- 的项被从栈的开头（或末尾）除去。
- 为它的水平计数器加一。
- 如果有孩子，每个孩子节点添加到栈与它的水平。
- 堆栈将被处理，直到所有的元素都消耗掉。
这确保每个节点将具有最小开销进行计数。消费堆栈的策略可以完全控制。无论是FIFO（先入先出），后进先出（的后进先出） - 这是很容易实现 - 甚至加权策略有（第一道工序子节点无/最子女消耗他们快）甚至随意堆消费分发数据结构意味着accros整个堆栈的制约。
协议栈递归函数堆栈比较
用自己的堆栈到PHP函数栈首先比较表明，这两种方法有共同的东西。它们都利用堆栈的。
但是，主要的区别是，在使用该函数调用的自己的堆栈prevents。调用一个函数，尤其是递归具有能够避免多个含义。
另一个关键的区别是，一个是自己的堆栈总是可以用它来询问，而有超过PHP语言本身的堆栈无法控制的。
下一步是，一个自己的堆栈可以按顺序进行处理，而函数堆栈是数据的处理1映射递归构建体：1到程序流
虽然递归将遁形数据（树）为code的的的内部递归特性的功能（这可以简化处理），有必要提供，获取国家藏起来通过函数调用进行介绍，作为函数的参数。
管理数据，因此要解决的问题是不少，但与递归相等或更复杂的
因此，下给函数调用的开销，人们已经可以闻到用于数据的开销。
这是值得看到这个在PHP语言本身的光芒。
为使递归工作，PHP需要添加额外的变量表上的函数堆栈。这些表需要在每次函数调用后进行管理。
递归也需要您通过引用传递变量。这是一个额外的开销，因为这些值需要之前和之后的功能被PHP结束被设置/处理
中需要递归这种参照共享数据结构为计数器。这架空中递归实现的可能的通过执行递归到一个类它自己的PHP，而没有被到目前为止建议，可能是值得考虑减少。
在用户栈实现的计数器阵列一样，这样的类可以共享所有的函数调用之间的柜台，提供了一个哈希访问类的成员函数（S）W / O利用变量引用。进一步上，在解决问题的复杂性可以在类分布在不同的功能与甚至注射作为依赖。 PHP提供了一个默认的递归迭代器接口了。
，以减少人们可以利用的另一个地方是全局变量表（ $ GLOBALS ），但制作的缺点的code较少的可重复使用的这预示着设计缺陷。即使设计不是一个问题，即所谓的超全局阵列需要管理之间的函数调用的为好。这导致通过引用非常类似的行为，以通过为它被认为是prevent它。因此它不是一个preferable溶液
按类
递归实现这是基于在讨论中提出上述得到它更多的抓地力的想法递归实现：
/ **
*类实现递归孩子计数器
*
*使用方法：
*
*对象使用：
*
* $反=新LevelChildCounter（$改编，_children'）;
* $计数= $反＆GT; countPerLevel（）;
*
*功能的使用：
*
* $计数= LevelChildCounter ::计数（$改编，_children'）;
* /
类LevelChildCounter {
私人$树;
私人$ childKey;
私人$计数器;
公共职能__construct（数组$树，$ childKey）{
$这个 - ＆GT;树= $树;
$这个 - ＆GT; childKey = $ childKey;
}
/ **
* countPerLevel的功能接口
* /
公共静态函数count（数组$树，$ childKey）{
$计数器=新的自我（$树，$ childKey）;
返回$反＆GT; countPerLevel（）;
}
私有函数COUNTUP（$级）{
使用isset（$这个 - ＆GT;计数器[$级别]）
？ $这个 - ＆GT;计数器[$级别] ++
函数：$ this-＆GT;计数器[$级别] = 1;
}
私有函数countNode（$节点，$级）{
//计数节点
$这个 - ＆GT;计数进位（$级）; //子处理？
如果（使用isset（$节点[$这个 - ＆GT; childKey]！））
返回; //递归算子节点
的foreach（$节点[$这个 - ＆GT; childKey]为$ childNode）
$这个 - ＆GT; countNode（$ childNode，$级+ 1）
;
}
/ **
*计数每级的所有节点
*
* @返回数组
* /
公共职能countPerLevel（）{
$这个 - ＆GT;计数器=阵列（）;
$这个 - ＆GT; countNode（$这个 - ＆GT;树，-1）;
返回$这个 - ＆GT;计数器;
}
}$数= LevelChildCounter ::计数（$改编，_children'）;
array_shift（$数）;后续代码var_dump（$数）;
和它的输出：
阵列（3）{
[0] =＆GT; INT（2）
[1] =＆GT; INT（1）
[2] =＆GT; INT（1）
}
I have an array that has a hierarchic structure. In this example there are two elements in the first level, 83 and 82. 82 has children 84 and 87 . 87 is a child of 84.
Array
(
[_children] => Array
(
[0] => Array
(
[id] => 11
[uid] => 24
[rid] => 83
[date] => 2011-06-18 15:08:10
)
[1] => Array
(
[id] => 10
[uid] => 24
[rid] => 82
[date] => 2011-06-18 15:08:07
[_children] => Array
(
[0] => Array
(
[id] => 12
[uid] => 82
[rid] => 84
[date] => 2011-06-18 15:30:34
[_children] => Array
(
[0] => Array
(
[id] => 13
[uid] => 84
[rid] => 87
[date] => 2011-06-18 16:11:50
)
)
)
)
)
)
)
I want to loop through that array and store some information for each level in another array. This is how my array should look like at the end.
Array
(
[0] => Array
(
[elements] => 2
)
[1] => Array
(
[elements] => 1
)
)
E.g. this shows that at level 0 are 3 nodes and at level 1 there are 5 nodes. How can I do that? Any ideas?
I would just count the numbers.
This means each item of the base key plus the same for it's children.
In opposite to recursion, I decided to use a stack for this.
To have a value per level, the counter needs a level context as well, which is added to the stack next to the node:
$count = array();
$stack[] = array(-1, $arr);
while($item = array_shift($stack)) {
list($level, $node) = $item;
$count[$level] = isset($count[$level]) ? $count[$level]+1 : 1;
if (!isset($node['_children']))
continue;
foreach($node['_children'] as $item)
$stack[] = array($level+1, $item);
}
var_dump($count);
This does output:
array(4) {
[-1]=> int(1)
[0] => int(2)
[1] => int(1)
[2] => int(1)
}
where -1 is the root node only containing children. So you might want to remove it after processing:
array_shift($count);
Edit: Storing the nodes
The following code adds a collector of nodes per level as well, called $nodes. It's a bit redundant as per count($nodes[$level]) is $count[$level], but it's just to show how to collect nodes as well:
$count = array();
$nodes = array(); // nodes per level go here.
$stack[] = array(-1, $arr);
while($item = array_shift($stack)) {
list($level, $node) = $item;
$count[$level] = isset($count[$level]) ? $count[$level]+1 : 1;
$nodes[$level][] = $node; // set here!
if (!isset($node['_children']))
continue;
foreach($node['_children'] as $item)
$stack[] = array($level+1, $item);
}
var_dump($count, $nodes);
Discussion
Using a stack prevents to make recursion function calls and reduces complexity. The idea behind it is fairly simple:
- The stack is initialized with the first node (which only contains children) - the tree's root node.
- An entry on the stack contains the node to be counted and it's level
- Each element on the stack is treated the same:
- An item gets removed from the beginning (or end) of the stack.
- The counter for it's level is increased by one.
- If it has children, each child-node is added to the stack with it's level.
- The stack will be processed until all elements are consumed.
This ensures that every node will be counted with a minimal overhead. The strategy of consuming the stack can be fully controlled. Either FIFO (First In, First Out), LIFO (Last In, First Out) - which is easy to implement - or even a weighted strategy (first process child-nodes that have no/the most children to consume them fast) or even random stack consumption to distribute the constraints the data-structure implies accros the whole stack.
Comparing Stack to Recursion Function Stack
Comparing using an own stack to the PHP's function stack first of all shows that both ways have things in common. Both make use of a stack.
But the main difference is, that an own stack prevents using the function calls. Calling a function, especially recursively has multiple implications that can be avoided.
Another key difference is, that an own stack always allows to interrogate with it while there is no control over the PHP language's own stack.
Next to that, an own stack can be processed sequentially, while the function stack is a recursive construct that maps the processing of the data 1:1 into the program flow.
While recursion will hide away the recursive nature of the data (tree) for the code within the function (which can simplify processing), there is the need to offer the state that gets hidden away by function calls to be introduced as function parameters.
Managing the data to solve the problem therefore is not less but equal or more complex with recursion.
So next to the overhead of the function calls, one can already smell an overhead for data.
It's worth to see this in the light of the PHP language itself.
To make recursion work, PHP needs to add additional variable tables onto the function stack. These tables need to be managed before and after each function call.
The recursion also needs you to pass variables by references. This is an additional overhead, as those values need to be set/processed before and after the function ends by PHP.
Such a reference is needed in the recursion to share the data structure for the counter. This overhead in a recursive implementation could be reduced by implementing the recursion into a class of it's own in PHP, which has not been suggested so far and is probably worth to consider.
Like the counter array in a user stack implementation, such a class could share the counter between all function calls, providing a hash accessible to the class's member function(s) w/o making use of variable references. Further on, complexity in solving the problem can be distributed over different functions with in the class or even injected as a dependency. PHP offers a default recursive iterator interface already.
Another place to reduce one could make use of is the global variable table ($GLOBALS) but with the downside of making the code less re-useable which signals a design flaw. Even if design is not an issue, that so called superglobals array needs to be managed between function calls as as well. That results in a quite-like behavior to passing by reference for which it was considered to prevent it. Therefore it is not a preferable solution.
Recursive Implementation by Class
This is a recursive implementation based on the idea raised in the discussion above to get more grip on it:
/**
* class implementation of a recursive child counter
*
* Usage:
*
* Object use:
*
* $counter = new LevelChildCounter($arr, '_children');
* $count = $counter->countPerLevel();
*
* Functional use:
*
* $count = LevelChildCounter::count($arr, '_children');
*/
class LevelChildCounter {
private $tree;
private $childKey;
private $counter;
public function __construct(array $tree, $childKey) {
$this->tree = $tree;
$this->childKey = $childKey;
}
/**
* functional interface of countPerLevel
*/
public static function count(array $tree, $childKey) {
$counter = new self($tree, $childKey);
return $counter->countPerLevel();
}
private function countUp($level) {
isset($this->counter[$level])
? $this->counter[$level]++
: $this->counter[$level] = 1;
}
private function countNode($node, $level) {
// count node
$this->countUp($level);
// children to handle?
if (!isset($node[$this->childKey]))
return;
// recursively count child nodes
foreach($node[$this->childKey] as $childNode)
$this->countNode($childNode, $level+1)
;
}
/**
* Count all nodes per level
*
* @return array
*/
public function countPerLevel() {
$this->counter = array();
$this->countNode($this->tree, -1);
return $this->counter;
}
}
$count = LevelChildCounter::count($arr, '_children');
array_shift($count);
var_dump($count);
And it's output:
array(3) {
[0]=> int(2)
[1]=> int(1)
[2]=> int(1)
}
这篇关于算相邻数组中的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
