20分钟到1秒内的优化

背景

经理叫我优化一段代码. 因为发现当数据量太大时运行时间则会变得很久. 这个代码在软件里已经存在 4年之久了. 最开始我们都不知道是谁写的这代码但之后发现竟然是经理自己 4年前写的代码. 他自己都不记得了(代码里没有注释).

算法的目的是将一个密集点集重新按照一定的分辨率筛选. 使得任意两点之间的距离要大于这个采样分辨率并且点的个数要尽量的多.

clutter of points

原始的实现算法

经理原始的算法是通过迭代每次选出一个点(为了方便就选第一个点) 然后把候选集中和此点距离大于分辨率的点记录下来做为下一轮的候选集. 实现则用了LINQ的where 看起来只有O(n) 循环但是其实是 O(n^2) 因为每次LINQ从当前候选集选出新的点这个操作就是 O(n).

        public List<Point3F> Resampling(double resolution, List<Point3F> tempPtList)
        {
            var samplePtList = new List<Point3F>();
            Point3F currentPt;
 
            double T = resolution * resolution;
            while (tempPtList.Count != 0)
            {
                currentPt = new Point3F(tempPtList[0].X, tempPtList[0].Y, tempPtList[0].Z);
                tempPtList = tempPtList.Where(x => (Math.Pow(x.X - currentPt.X, 2) + Math.Pow(x.Y - currentPt.Y, 2) + Math.Pow(x.Z - currentPt.Z, 2)) >= T).ToList();
                samplePtList.Add(currentPt);
            }
 
            return samplePtList;
        }

        public List<Point3F> Resampling(double resolution, List<Point3F> tempPtList)
        {
            var samplePtList = new List<Point3F>();
            Point3F currentPt;

            double T = resolution * resolution;
            while (tempPtList.Count != 0)
            {
                currentPt = new Point3F(tempPtList[0].X, tempPtList[0].Y, tempPtList[0].Z);
                tempPtList = tempPtList.Where(x => (Math.Pow(x.X - currentPt.X, 2) + Math.Pow(x.Y - currentPt.Y, 2) + Math.Pow(x.Z - currentPt.Z, 2)) >= T).ToList();
                samplePtList.Add(currentPt);
            }

            return samplePtList;
        }

O(n) 哈希表实现

HASH 哈希表是非常有用的数据结果因为它的查询和添加记录的时间复杂度可以内为是O(1) 常量级. 就因为这样很多算法在用了哈希表的话都能降至少一个数量级比如 O(n^2) 到 O(n). 你可以自己写哈希算法但是.NET系统提供的已经很好了碰撞的概率已经比较小了.

小于分辨率相邻的点就应该有一样的哈希键值. 我们可以假设这些点在3维空间中被放在间隔分辨率的网格中. 那么分配在一个网络里的点就一定是相邻的(小于一个分辨率的). 但是反过来却不一定. 有可能相邻的点却分配在邻居. 我们可以通过两轮筛选. 第一轮通过哈希排队绝大部分的点. 第二轮则轻轻松松(穷举就可以了) 排除漏网之鱼.

        public List<Point3F> Resampling(double resolution, List<Point3F> tempPtList)
        {
            var samplePtList = new List<Point3F>();
            var added = new Hashtable();
 
            for (var i = 0; i < tempPtList.Count; i ++)
            {
                var cur = tempPtList[i];
                // 三维网络中的位置
                int x = (int)Math.Round(cur.X / resolution);
                int y = (int)Math.Round(cur.Y / resolution);
                int z = (int)Math.Round(cur.Z / resolution);
                var key = x + "," + y + "," + z;   // hash key
                if (added.ContainsKey(key)) continue; // 已经添加过了 不再添加
                var currentPt = new Point3F(tempPtList[i].X, tempPtList[i].Y, tempPtList[i].Z);
                samplePtList.Add(currentPt);
                added.Add(key, key); // 记录一下这个点
            }
 
            var T = resolution*resolution;
            for (var i = 0; i < samplePtList.Count; i ++) // 第二轮过滤
            {
                var cur = samplePtList[i];
                samplePtList.RemoveAll( // 排除相邻的点
                    x =>
                        (
                            ((x != cur) && 
                             ((x.X - cur.X) * (x.X - cur.X) + (x.Y - cur.Y) * (x.Y - cur.Y) + (x.Z - cur.Z) * (x.Z - cur.Z)) < T
                        )
                ));
            }
 
            return samplePtList;
        }

        public List<Point3F> Resampling(double resolution, List<Point3F> tempPtList)
        {
            var samplePtList = new List<Point3F>();
            var added = new Hashtable();

            for (var i = 0; i < tempPtList.Count; i ++)
            {
                var cur = tempPtList[i];
                // 三维网络中的位置
                int x = (int)Math.Round(cur.X / resolution);
                int y = (int)Math.Round(cur.Y / resolution);
                int z = (int)Math.Round(cur.Z / resolution);
                var key = x + "," + y + "," + z;   // hash key
                if (added.ContainsKey(key)) continue; // 已经添加过了 不再添加
                var currentPt = new Point3F(tempPtList[i].X, tempPtList[i].Y, tempPtList[i].Z);
                samplePtList.Add(currentPt);
                added.Add(key, key); // 记录一下这个点
            }

            var T = resolution*resolution;
            for (var i = 0; i < samplePtList.Count; i ++) // 第二轮过滤
            {
                var cur = samplePtList[i];
                samplePtList.RemoveAll( // 排除相邻的点
                    x =>
                        (
                            ((x != cur) && 
                             ((x.X - cur.X) * (x.X - cur.X) + (x.Y - cur.Y) * (x.Y - cur.Y) + (x.Z - cur.Z) * (x.Z - cur.Z)) < T
                        )
                ));
            }

            return samplePtList;
        }