小赖子的英国生活和资讯

20分钟到1秒内的优化

JustYY.com 小赖子的英国生活和资讯
阅读 桌面完整版

背景

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

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

clutter of points

原始的实现算法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

        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维空间中被放在间隔分辨率的网格中. 那么分配在一个网络里的点就一定是相邻的(小于一个分辨率的). 但是反过来却不一定. 有可能相邻的点却分配在邻居. 我们可以通过两轮筛选. 第一轮通过哈希排队绝大部分的点. 第二轮则轻轻松松(穷举就可以了) 排除漏网之鱼.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

        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;
        }

结果

相同的输入数据下 新算法闪电般的就完成了 而在优化前 则需要运行 20分钟.

更新 使用 Hashset 数据结构就可以了 这样内存更加有效率.

英文: https://helloacm.com/refactoring-re-sampling-algorithm-using-on-hashtable/

强烈推荐

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

相关文章：

  1. Javascript 中 sleep 函数实现 阅读 桌面完整版 Javascript 中并没有 built-in 的 sleep 函数支持, 在 async/await/Promise 的支持之前, 我们可以用 busy-waiting 的方式来模拟: 1...
  2. 你给SteemIt中文微信群拖后腿了么? 阅读 桌面完整版 这年头不缺算法, 就缺数据. 这两天花了很多时间在整API上, 整完之后自己用了一下还觉得真是挺方便的. 今天就突然想看一看自己是否给大家拖后腿了, 于是调用每日中文区微信群排行榜单的API, 刷刷拿着 NodeJs 练手: 1 2 3 4...
  3. 智能手机 HTC One M9 使用测评 阅读 桌面完整版 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是...
  4. C++ 编程练习题: 如何合并两个二叉树? 阅读 桌面完整版 题意: 合并两个二叉树, 没有说不可以改变原来的二叉树. 合并的时候把结点求合. C/C++ 中二叉树的定义 在C或者C++中, 二叉树的定义可以很方便的用结构体来表征. 其中左右子树都是递归定义. 1 2 3 4...
  5. STEEM API 系列之获取货币转换 阅读 桌面完整版 STEEMIT 有 SBD, STEEM, STEEM POWER 还有 VESTS这几个概念. 时不时, 我们就需要知道它们之间几个转换关系: 1个STEEM等于多少SBD? 1个SBD 等于多少STEEM?...
  6. 按揭贷款(房贷,车贷) 每月还贷计算器 阅读 桌面完整版 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的....
  7. 如何在海外 在线观看 2016 欧洲杯比赛? 阅读 桌面完整版 四年一度的欧洲杯足球又开始了, 夏天来了 没有什么比边看足球边喝啤酒更爽的事了. 通过以下链接可以 免费在线观看 2016 欧洲杯比赛 (英语解说). 点击以下链接能在线免费看 2016 欧洲杯比赛 (The following...
  8. 入佳能 6D Mark II 入门级全幅单反 阅读 桌面完整版 一直以来都想要全幅的单反, 在之前入了经典24-70mm F2.8佳能红圈镜头 (万能焦), 但是一直机身还是半画幅的 T3i, 朋友就说这红圈镜头需要在全幅单反上才能发挥最大的功效. 考虑许久, 咬咬牙, 入了佳能 6D Mark II...
Exit mobile version