记一次带层级结构列表数据计算性能优化
记一次带层级结构列表数据计算性能优化
1、背景
最近，负责一个类财务软件数据计算的性能优化工作。先说下=这项目的情况，一套表格，几十张表格，每张表格数据都是层级结构的，通过序号确定父子级关系，如1，1.1,1.1.1,1.1.2，1.1.3,1.2,1.2.1,1.2.2,1.3.。。。而且，列表数据带表内编辑功能，就跟Excel体验一样。没错，你猜对了，不出意外的，这是个CS项目，前端采用WPF，在计算之前，对应表格数据已经拉取到前端内存中，通过MVVM双向绑定到UI列表。计算公式分横向和纵向，叶子级的都是横向计算，如金额 = 单价 * 数量；父级的纵向计算，如 1.金额 = 1.1金额 + 1.2金额 + 1.3金额。。。很明显，只能先计算叶子级，再逐级往上计算父级，而且是自底向上的。
自然而然的，你会想到递归，而且之前项目中也是这么整的，递归调用自底向上计算。问题是，每张表格数据量都很大，实际环境中，最多的出现了30W条。我们按照递归调用顺序去分析下这个过程：首先，从30W里找根级（虽然最终需要自底向上计算，但系统本身它是不知道谁是子级的，只能由父级往下去逐个找），找到之后，根据根级Id从30W数据中找到其所有子级，循环每个子级，根据每个子级ID，从30W数据找到该子级对应的子级。。。只到最终叶子级，可以计算了，该层递归出栈，计算其父级，父级完了计算父级的父级。。。
那么，问题来了：首先，递归本身就是极耗空间的，这么大数据量，内存浪费更是了不得，而且，数据检索也把CPU给占尽了；更严重的，这还只是一张，系统有30多张表格。。。实际测试也发现，计算一开启，i5 CPU，8G的机器，CPU直接打满，内存也飙升（要不是Windows对进程内存做限制，我估计内存也打满了，实际测试出现过OutOfMemory异常。。。）。运气好，30W数据，花个大几分钟能算完，运气不好就等个大几分钟，OutOfMemory。。。这么搞，肯定是不行的，开发机都不行，更别提客户环境千差万别，有些客户机配置很恶劣，老旧XP，2G内存，32位。。。
2、方案
一把辛酸一把泪，问题给出来了，自然是要解决。上述方案的问题在于，查找每个节点，都需要从30W数据里边遍历，能不能访问每个节点时候，不用去遍历这30W数据呢？本身，这30W数据就是一个树状结构，假如事先把这30W数据构造成一颗树，那么只需要按照后续遍历，岂不就避免了频繁的30W遍历？
好，确定了用树遍历解决，那是用普通树，还是二叉树（是不是好奇，为什么会想到这个问题）？答案是，二叉树，因为最开始，我就用的普通树，但测试发现，虽然性能极大提升（几分钟到几十秒），但还是有点儿难以接受，用VS性能探查器发现，普通树需要跟踪某级别未访问节点（通俗点儿说就是，访问完某个节点，需要从同根的子级中遍历寻找下一个未访问的节点），这个特别耗时，假如该级节点特别多，则会遇到上述同样的问题，从大批量数据中检索，虽然这个数据范围已经比30W极大减少了。用二叉树，就左子树右子树，是不需要这个的。
3、实现
首先，树节点的定义：
/// <summary>
/// 二叉树节点
/// </summary>
/// <typeparam name="T"></typeparam>
public class TreeNode<T>
where T : Data
{
public TreeNode()
{
this.Children = new List<T>();
}
public TreeNode(T data)
: this()
{
this.Data = data;
}
/// <summary>
/// 节点对应数据节点
/// </summary>
public T Data { get; set; }
/// <summary>
/// 树节点
/// </summary>
public TreeNode<T> Parent { get; set; }
/// <summary>
/// 左子树
/// </summary>
public TreeNode<T> Left { get; set; }
/// <summary>
/// 右子树
/// </summary>
public TreeNode<T> Right { get; set; }
/// <summary>
/// 该节点对应业务节点的子业务节点集合
/// </summary>
public List<T> Children { get; private set; }
}节点，节点数据，左子树节点，右子树节点，父级节点，比较简单。这里唯一需要说明的是，节点对应的子级数据集合，因为原始数据，是一个普通树，最终我们是要把它转化为一个二叉树的，转化之后，我们需要记录某个数据节点它对应的原始子级数据集合是哪些，便于后续跟踪和计算。
好，二叉树节点定义好了，对二叉树进行处理的前提，是先要构造二叉树。数据结构中，有一种普通树状结构转为二叉树的方式是，第一个子节点作为左子树，剩余兄弟节点，都作为上一个子节点的右子树存在，也就是说，左子树子节点，右子树兄弟节点。假如我们有这么几个数据节点：1,1.1,1.1.1,1.1.2,1.1.3,1.2,1.2.1,1.2.2,1.3，则构建完成之后，二叉树应该是这样子的：
具体代码，怎么实现呢？这里先说下前提，系统中数据是按照对应序号排序的，比如1,1.1,1.1.1,1.1.2,1.1.3,1.2,1.2.1，1.2.2,1.3。那么，从一维列表构建二叉树的代码如下：
/// <summary>
/// 根据实体列表构建二叉树
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <returns></returns>
public static TreeNode<T> GenerateTree<T>(List<T> list, Func<T, bool> rootCondition, Func<T, T, bool> parentCondition)
where T : Data
{
if (!list.Any())
{
return null;
}
var rootData = list.FirstOrDefault(x => rootCondition(x));
TreeNode<T> root = new TreeNode<T>(rootData);
Stack<TreeNode<T>> stackParentNodes = new Stack<TreeNode<T>>();
stackParentNodes.Push(root);
foreach (var item in list)
{
if (item == rootData)
{
continue;
}
TreeNode<T> parent = stackParentNodes.Peek();
while (!parentCondition(item, parent.Data))
{
stackParentNodes.Pop();
if (stackParentNodes.Count == 0)
{
stackParentNodes.Push(root);
parent = root;
break;
}
parent = stackParentNodes.Peek();
}
var currentNode = new TreeNode<T>(item);
if (parent.Left == null)
{
parent.Left = currentNode;
currentNode.Parent = parent;
}
else
{
if (parent.Left.Right == null)
{
parent.Left.Right = currentNode;
currentNode.Parent = parent.Left;
}
else
{
parent.Left.Right.Parent = currentNode;
currentNode.Right = parent.Left.Right;
currentNode.Parent = parent.Left;
parent.Left.Right = currentNode;
}
}
parent.Children.Add(item);
stackParentNodes.Push(currentNode);
}
return root;
}这段代码，参考网上的，出处我已经找不到了，如果哪位网友看见了，麻烦告诉我，我注明出处。说下这段代码的核心思想，首先有个父级栈，用来记录上次遍历的节点及其父节点，然后开始遍历数据列表中每条记录，在这过程中，从父节点栈中找该节点对应的父节点，不匹配的元素直接出栈，只到找到对应父节点。找到之后，如果父节点左子树不存在，直接将当前节点挂在左子树，如果左子树存在，则该节点是当前左子树的兄弟节点，需要作为该左子树的右子树去挂。这时候有个问题，如果左子树的右子树不存在，直接挂在左子树的右子树就可以，如果存在，则需要将其挂为右子树，左子树的原右子树变成当前节点的右子树。因为遍历时候，是按照顺序来的，这么一来，则兄弟节点在树上挂的顺序，是逆序的，最终效果会如下：
有点儿拧，大家知道是那么回事儿就行了。树构建好了，接下来就是遍历计算。很明显，对于这种计算，是需要后续遍历的，则实现代码如下：
/// <summary>
/// 后续遍历二叉树进行计算
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="root"></param>
/// <param name="leaveCompute"></param>
/// <param name="branchCompute"></param>
public static void Compute<T>(TreeNode<T> root, Action<T> leafCompute, Action<T, List<T>> branchCompute)
where T : Data
{
if (root == null)
{
return;
}
TreeNode<T> currentNode = null,
preNode = null;
Stack<TreeNode<T>> stackParentNodes = new Stack<TreeNode<T>>();
stackParentNodes.Push(root);
while (stackParentNodes.Any())
{
currentNode = stackParentNodes.Peek();
if ((currentNode.Left == null && currentNode.Right == null)
|| (preNode != null) && (preNode == currentNode.Left || preNode == currentNode.Right))
{
preNode = currentNode;
if (currentNode.Children.Any())
{
currentNode.Data.LeavesCount = currentNode.Children.Sum(x => x.LeavesCount);
branchCompute?.Invoke(currentNode.Data, currentNode.Children);
}
else
{
currentNode.Data.LeavesCount = 1;
leafCompute?.Invoke(currentNode.Data);
}
stackParentNodes.Pop();
}
else
{
if (currentNode.Right != null)
{
stackParentNodes.Push(currentNode.Right);
}
if (currentNode.Left != null)
{
stackParentNodes.Push(currentNode.Left);
}
}
}
}核心思想是记录遍历过程中的父级节点及上次遍历的节点。当前节点需要被访问的条件是，当前节点左子树右子树都为空（叶子节点）或者上次访问的节点是本节点的子节点，否则当前节点不应该被访问，而是将其右子树左子树进栈以备考察。这个是全量计算的方式。还有一种情况是，改变了其中某个单元格，例如上述，我改了1.1.3其中的单价，则这时候也需要计算，但计算应该仅限于本级节点及父节点，你非要全量计算也没问题，无非性能低点儿。那么，计算本级和父级的功能，如下：
/// <summary>
/// 计算指定节点极其父级
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="node"></param>
/// <param name="branchCompute"></param>
public static void ComputeParent<T>(TreeNode<T> node, Action<T> leafCompute, Action<T, List<T>> branchCompute)
where T : Data
{
if (node == null)
{
return;
}
TreeNode<T> currentNode = node;
if (node.Children.Any())
{
currentNode.Data.LeavesCount = currentNode.Children.Sum(x => x.LeavesCount);
branchCompute?.Invoke(currentNode.Data, currentNode.Children);
}
else
{
currentNode.Data.LeavesCount = 1;
currentNode.Data.IsLeaf = true;
leafCompute?.Invoke(currentNode.Data);
}
while (currentNode != null)
{
var parentNode = currentNode.Parent;
if (parentNode != null && parentNode.Left == currentNode)
{
branchCompute?.Invoke(parentNode.Data, parentNode.Children);
}
currentNode = parentNode;
}
}核心思想是，首先计算当前节点，然后，根据树节点中保存的parent节点信息，逐级向上计算其父节点。比较简单，不多说。后续遍历计算有了，还有一种情况，就是要从树里边查找某个节点，这里明显是要前序遍历的，因为扎到某个节点我就直接返回了，犯不着每个节点都过一遍及保留中途父节点信息。实现如下：
/// <summary>
/// 查找符合指定条件的节点
/// </summary>
/// <typeparam name="T"></typeparam>
/// <returns></returns>
public static TreeNode<T> FindNode<T>(TreeNode<T> node, Func<T, bool> condition)
where T : Data
{
if (node == null)
{
return null;
}
Stack<TreeNode<T>> stackParentsNodes = new Stack<TreeNode<T>>();
TreeNode<T> currentNode = node;
while (currentNode != null || stackParentsNodes.Any())
{
if (currentNode != null)
{
if (condition(currentNode.Data))
{
return currentNode;
}
stackParentsNodes.Push(currentNode);
currentNode = currentNode.Left;
}
else
{
currentNode = stackParentsNodes.Pop().Right;
}
}
return null;
}典型的前序遍历，比较简单，不多说。
4、总结
这么一套解决方案下来，全套30多张表格的计算，由原来的十几分钟，改进到几十秒。好了，本次分享就到这里，希望能帮助到大家。
腾讯云开发者
