当前位置：首页 > 编程日记 > 正文

通过改进算法来优化程序性能的真实案例（Ransac）

编程日记 2024-11-14 06:20:00

对于运行不了几次，一次运行不了多久的方法，我们不需要考虑性能优化，对于那些需要经常运行几百次几千次的方法，我们头脑里还是要有性能这根弦。C#太优雅方便了，以至于很多人写程序时根本就把性能抛到脑后了，不愿意耗费心思去进行代码优化和算法优化，结果写出来的程序奇慢无比。不明真相的群众把这怪罪给C#语言。这不是C#的杯具，是程序员的无能。

2个月前，我研究sift（一种重要的图像分析算法）。最先找到了一个C#实现的library——libsift，这个library处理一张正常大小的图像，要耗时2-3分钟。后来，又找到一个C实现的library，处理同样的图像，耗时在1秒以内——秒杀。

昨天，我写Ransac（随机抽样一致性）算法代码时参考了libsift里的Ransac实现。不看不知道，一看吓一跳。那代码性能低下得无以复加。我随手优化了一下算法，就将随机抽样那部分的性能提高了上千倍。

下面详细道出。

一、Ransac

Ransac是用途很广泛的算法，详细介绍请看http://en.wikipedia.org/wiki/RANSAC。下面简单介绍一下（没兴趣的可以略过不看）。

我们分析世界，需要对世界建模，把世界中的现象抽象成模型。每个模型，又存在一些参数，通过调节参数，可以得到不同的实例，进行推演。我们观察现象，得到一堆数据。如何为这堆数据找一个合适的模型，再确定合适的模型参数，这是很重要的问题，是人类理性的基础。
数据分两种：有效数据（inliers）和无效数据（outliers）。那些偏差不大的数据是有效数据，偏差大的数据是无效数据。
如果有效数据占大多数，无效数据只是很少量时，我们可以通过最小二乘法或类似的方法来确定模型的参数和误差。如果无效数据很多（比如，超过了50%的数据是无效数据），最小二乘法就失效了，我们需要新的算法。

上图左图是观察的数据。直觉可以看出，外面的散点是outliers，中间近似分布为一直线的是inliers。怎么设计一个算法，算出这条直线，使它对inliers的拟合度较高（如上图右图所示）？

再举一个更直观的例子：

上图左侧是一个验证码，我们将它看作“数据”。右侧是一个字符，我们将它看作“模型”，如何通过算法去除“数据”中的outlier，剩下inliner来和“模型”进行匹配
Ransac 是解决这类问题的代表性算法。它是一种随机算法，步骤如下：

输入：k,n,t,d,model,data
BestModel = null;
迭代k次——
（1）从data中随机取出n个点，用这n个点去拟合model和模型的model，将得到的带参数的model记为MaybeBestModel。
（2）依次取出剩下的点，计算该点对应MaybeBestModel模型的误差，如果这个误差小于阈值t，则认为这个点是有效的，把这个点也放进MaybeBestModel中。
（3）所有点取完了。这时，MaybeBestModel中有效点的数量是否大于或等于d，如果是，则对于MaybeBestModel，重新计算一下它的模型参数。
（4）评估一下MaybeBestModel和BestModel哪一个好？如果MaybeBestModel更好，则将MaybeBestModel 记做新的 BestModel。

二、libsift中Ransac算法的实现

Ransac算法中，model，model的拟合，不同参数model之间的比较都是因问题不同而不同，因此，可以将model抽象成接口。将model 抽象之后，Ransac 算法的骨干就只剩下一个随机采样的过程：

迭代k次——
（1）从data中随机抽取n个点，然后do something
（2）依次取出剩下的点，然后do something

下面是libsift中Ransac算法的实现代码：

Code

不考虑Model部分，只考虑单次迭代过程中的随机抽样，可抽象出这样一个过程：

（1）假设数据集是points，它的类型是List<T>；
（2）从points中随机选取n个对象，放入容器samples中；
（3）依次处理剩下的对象，根据处理结果决定放入samples或不放入samples

我把libsift的Ransac代码中上述逻辑部分单独提取出来了，并作了以下简化：

（1）直接令points是List<int>类型
（2）处理剩下的对象时，全部决定放入samples中

代码如下：

Code

准备测试数据，进行性能测试：

Code

这个测试中假设共有10000个数据，一共进行50次迭代，每次迭代的n值为4000。用老赵的CodeTimer测量运行时间，结果为：

CaseLibSift
        Time Elapsed:   24,492ms
        CPU Cycles:     44,426,562,664
        Gen 0:          6
        Gen 1:          0
        Gen 2:          0

24.5秒！雷人的慢！

为什么会这样呢？主要问题出在这两句中：

if (samples.Contains(sampleToAdd))

if (samples.Contains(point))

您有更好的方案吗？

下面是娱乐时间。娱乐之后，放上我的改进方案。

三、娱乐

四、我的方案

再回顾一下问题：

我采用的洗牌算法的变种。所谓洗牌问题，就是给定一个数组，编写程序将这个数组打乱。下面是一个经典的洗牌算法：

对于N个元素的数组
（1）从N个元素中随机取出一个元素，与数组最后一个元素调换
（2）从前N-1个元素中随机取出一个元素，与倒数第二个元素调换
（3） ……

将上述洗牌算法稍微改变一下，就得到本文问题的答案：

对于N个元素的数组
（1）从N个元素中随机取出一个元素，与数组第一个元素调换
（2）从后N-1个元素中随机取出一个元素，与第二个元素调换

……
（n）从后N-(n-1)个元素中随机取出一个元素，与第n个元素调换

这样，前n个元素就是随机取出的元素了。再考虑这样一个问题，就是n>N/2的情况，这时，n>N-n。我们不需要随机取出n个元素，只需要取出N-n个元素即可，剩下n个元素便是我们想要的随机采样结果。

把整个算法写成了扩展方法，代码如下：

Code

同CaseLibSift对比性能：

Code

结果为：

（1）datalenth=10000；n=1000；loops=100时的测试结果：

CaseLibSift
        Time Elapsed:   43,750ms
        CPU Cycles:     78,647,268,469
        Gen 0:          12
        Gen 1:          1
        Gen 2:          0

MyCase
        Time Elapsed:   20ms
        CPU Cycles:     29,902,543
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

（2）datalenth=10000；n=4000；loops=50时的测试结果：

CaseLibSift
        Time Elapsed:   24,626ms
        CPU Cycles:     44,217,626,002
        Gen 0:          6
        Gen 1:          1
        Gen 2:          0

MyCase
        Time Elapsed:   30ms
        CPU Cycles:     48,109,204
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

对比可见，性能提高了千倍。

下面是我的Ransac完整实现代码：

Code

本文转自xiaotie博客园博客，原文链接http://www.cnblogs.com/xiaotie/archive/2009/11/19/1605769.html如需转载请自行联系原作者

xiaotie 集异璧实验室(GEBLAB)

https://www.dkcj.cn/info/27431.html

ASP.NET中使用MD5和SHA1算法加密

你的主页或者你管理的网站有各种密码需要保护，把密码直接放在数据库或者文件中存在不少安全隐患，所以密码加密后存储是最常见的做法。在ASP.NET中实现加密非常容易。.NET SDK中提供了CookieAuthentication类，其中的HashPasswordForStoringInC…

编程日记2024/11/14 06:10:00

不追逐标准化产品，360数科的一站式风控体系有何不同？

新冠肺炎疫情无疑加速了金融行业数字化转型，竞争者不断涌入，逐渐形成由BATJ、传统银行旗下金融科技子公司、以及专注于金融机构的数字化服务公司构成的竞争格局。然而，风控始终是金融行业的核心。作为定位于中国零售金融领域科技服务商的360数…

编程日记2024/11/14 06:00:00

基于Bootstrap里面的Button dropdown打造自定义select

最近工作非常的忙，在对一个系统进行改版。项目后台是MVC1.0开发的，但是前端部分已经改过几个版本，而已之前的设计师很强大，又做设计又做前端开发。而已很时尚和前沿，使用了一直都很热门的Bootstrap工具包，有…

编程日记2024/11/14 05:50:00

HybridDB · 源码分析 · MemoryContext 内存管理和内存异常分析

背景最近排查和解决了几处 HybridDB for PostgreSQL 内存泄漏的BUG。觉得有一定通用性。这期分享给大家一些实现细节和小技巧。阿里云上的 HybridDB for PostgreSQL 是基于 PostgreSQL 开发，定位于 OLAP 场景的 MPP 架构数据库集群。它不少的内部机制沿用了 Post…

编程日记2024/11/14 05:40:00

联合南京大学，爱奇艺智能论文入选顶会CVPR 2021

日前，全球计算机视觉顶级会议CVPR (IEEE Conference on Computer Vision and Pattern Recognition)公布了2021年论文接收结果。作为计算机视觉领域世界三大顶会(CVPR、ICCV、ECCV)之一，CVPR的论文投稿量近五年来持续大涨。据CVPR官网显示，今…

编程日记2024/11/14 05:30:00

Forefront_TMG_2010-TMG发布Web服务器

1.环境拓扑图：2.准备DMZ区域的Web服务器：安装Web服务器：在DMZ区域的Web服务器进行测试：3.TMG发布Web服务器：打开TMG管理控制台，新建“网站发布规则”：新建名称：选择“允许”&#xf…

编程日记2024/11/14 05:20:00

ASP.NET实现身份模拟

使用模拟时，ASP.NET 应用程序可以选择以这些应用程序当前正为之操作的客户的身份执行。通常这样做的原因是为了避免在 ASP.NET 应用程序代码中处理身份验证和授权问题。而您依赖于 Microsoft Internet 信息服务 (IIS) 来验证用户，然后将已通过验证的标记…

编程日记2024/11/14 05:10:00

Mac homebrew类似apt-get命令安装包

INSTALL brew ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" 其它： 其他brew命令 brew list 列出已安装的软件 brew update 更新brew brew home 用浏览器打开brew的官方网站 brew inf…

编程日记2024/11/14 05:00:00

asp.net中长内容自动分页的实现

在一篇文章过长时,可以自动的写个小程序对其进行分页.具体代码:public class t3 : System.Web.UI.Page { private string str;//字符 private int strl;//字符总长度 private int pagesize;//每页显示的字符数 …

编程日记2024/11/14 04:50:00

黑马程序员之List--队列、栈...

--------------------- ASP.NetUnity开发、.Net培训、期待与您交流！ ---------------------- 1.队列：先进先出运行结果： zhangsan lisi wangwu 2.栈：先进后出结果： lisi wangwu zhangsan 3. 去除重复元素思路&#x…

编程日记2024/11/14 04:40:00

龙芯架构应用迁移技术分享——搜狗输入法应用迁移

技术引领创新，用“芯”构建生态，第一期龙芯生态论坛将于2021年3月12日（周五）盛大开讲！龙芯生态论坛作为龙芯生态建设的重要技术交流窗口，将汇聚龙芯资深技术专家及行业生态伙伴精英，持续开展行业…

编程日记2024/11/14 04:30:00

Health Check in eShop -- 解析微软微服务架构Demo（五）

引言 What is the Health Check Health Check（健康状态检查）不仅是对自己应用程序内部检测各个项目之间的健康状态（各项目的运行情况、项目之间的连接情况等），还包括了应用程序对外部或者第三方依赖库的状态检测。 Why…

编程日记2024/11/14 04:20:00

网易伏羲论文入选 CVPR：AI 感知表情能力或实现巨大突破！

出品 | AI科技大本营（ID:rgznai100）2月28日，人工智能顶级会议CVPR 2021（国际计算机视觉与模式识别会议，Conference onComputer Vision and Pattern Recognition）公布论文录取结果，网易伏羲共有3…

编程日记2024/11/14 04:10:00

asp.net/c#字符格式化大总结

一、用{0:?}格式化可通过 String.Format 方法或通过 Console.Write 方法格式化数值结果，其中后一种方法调用 String.Format。使用格式字符串指定格式。下表包含受支持的标准格式字符串。格式字符串采用的形式为 Axx，其中 A 为“格式说明符”&#xff0c…

编程日记2024/11/14 04:00:00

小鱼提问1 类中嵌套public修饰的枚举，外部访问的时候却只能Class.Enum这样访问，这是为何？...

/// <summary>/// 常量等定义/// </summary>public class General{/// <summary>/// 文件类型/// </summary>public enum FileType{}}小鱼提问：都是public修饰，为何外部只能General.FileType这样访问？既然外部都不能…

编程日记2024/11/14 03:50:00

radio根据name 获取选中值及判断是否被选中

$(input:radio[name"fjscfs"]:checked).val();根据id判断是否被选中if($("#A26").is(":checked")){}根据class判断是否被选中if($(".A26").is(":checked")){}转载于:https://blog.51cto.com/ty2538402559/1949828

编程日记2024/11/14 03:40:00

ASP.NET中用healthMonitor属性用

在ASP.NET 2.0中，可以使用healthMonitoring属性监测事件。healthMonitoring属性是一个基于方法的provider，在这里可以构造自己的provider。利用healthMonitoring属性，我们可以诸如记录错语、成功的事件等，对不同的数据源&#xff…

编程日记2024/11/14 03:30:00

用 Python 动态可视化，看看比特币这几年

作者 | 刘早起来源 | 早起Python头图 | 下载于视觉中国最近几年，一直站在风口浪尖的比特币被追捧为最佳的投资产品，拥护者们认为这种加密货币是一种类似于黄金的储值工具，可以对冲通胀和美元疲软。其他人则认为，比特币的暴涨只是一…

编程日记2024/11/14 03:20:00

违规用户处理办法

2019独角兽企业重金招聘Python工程师标准>>> 1.简单设置用户信赖状态给用户设置信任字段，0不可信任，1默认许可（默认值），2可信赖用户当用户违规后，对其进行惩罚并设置其为不可信赖状态&#…

编程日记2024/11/14 03:10:00

linux同步软件

linux同步软件：scp,rsync,inotify,sersync一、scpscp就是secure copy，是用来进行远程文件拷贝的。数据传输使用 ssh，并且和ssh 使用相同的认证方式，提供相同的安全保证。与rcp 不同的是，scp 在需要进行验证时会要求你…

编程日记2024/11/14 03:00:00

C语言内联函数

内联函数也称内嵌函数，它主要解决程序的运行效率。 #####################问题######################################### 函数调用需要建立栈内存环境，进行参数传递，并产生程序执行转移，这些转移都需要时间开销。有些函数在程序…

编程日记2024/11/14 02:50:00

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray [4,−1,2,1] has the largest sum 6. Code: class Solution { public:int …

编程日记2024/11/14 02:40:00