对于运行不了几次,一次运行不了多久的方法,我们不需要考虑性能优化,对于那些需要经常运行几百次几千次的方法,我们头脑里还是要有性能这根弦。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算法的实现代码:
不考虑Model部分,只考虑单次迭代过程中的随机抽样,可抽象出这样一个过程:
(1)假设数据集是points,它的类型是List<T>;(2)从points中随机选取n个对象,放入容器samples中;
(3)依次处理剩下的对象,根据处理结果决定放入samples或不放入samples
我把libsift的Ransac代码中上述逻辑部分单独提取出来了,并作了以下简化:
(1) 直接令points是List<int>类型(2) 处理剩下的对象时,全部决定放入samples中
代码如下:
准备测试数据,进行性能测试:
这个测试中假设共有10000个数据,一共进行50次迭代,每次迭代的n值为4000。用老赵的CodeTimer测量运行时间,结果为:
CaseLibSiftTime 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))
您有更好的方案吗?
下面是娱乐时间。娱乐之后,放上我的改进方案。
三、娱乐
四、我的方案
再回顾一下问题:
(1)假设数据集是points,它的类型是List<T>;
(2)从points中随机选取n个对象,放入容器samples中;
(3)依次处理剩下的对象,根据处理结果决定放入samples或不放入samples
我采用的洗牌算法的变种。所谓洗牌问题,就是给定一个数组,编写程序将这个数组打乱。下面是一个经典的洗牌算法:
对于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个元素便是我们想要的随机采样结果。
把整个算法写成了扩展方法,代码如下:
同CaseLibSift对比性能:
结果为:
(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完整实现代码:
本文转自xiaotie博客园博客,原文链接http://www.cnblogs.com/xiaotie/archive/2009/11/19/1605769.html如需转载请联系原作者
xiaotie 集异璧实验室(GEBLAB)