记一次带层级结构列表数据计算性能优化

释放双眼,带上耳机,听听看~!

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多张表格的计算,由原来的十几分钟,改进到几十秒。好了,本次分享就到这里,希望能帮助到大家。

 

人已赞赏
站长资讯

Vue图片懒加载插件

2020-11-9 3:41:29

站长资讯

2019CVPR《Mask Scoring R-CNN》

2020-11-9 3:41:40

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索