|
楼主 |
发表于 2013-4-11 13:03
|
显示全部楼层
本帖最后由 lee1892 于 2013-4-16 12:13 编辑
使用正确的数据结构的例子(四)由28秒到2秒!
本贴附件:
水样监测_使用数据结构加速 by Lee1892.rar
(353.63 KB, 下载次数: 762)
示例原贴:[求助] 紧急求助高手,如何解决这个水样监测统计,字典法可能最好!
相关的初步讨论:[原创] 申明变量与否及何种变量对代码执行速度的对比
示例的简短介绍:
该贴原始数据中有9586个数据条目,每条记录有19个数据,需要找出15个或以上的数据完全一样的条目。显然,一个最为朴素的方法就是冒泡式大循环,保证任意两个条目都对比过一次,且仅对比一次。对比的次数为:(9858 - 1) ^ 2 = 91,872,225 次,9千万+次。
我在前贴中使用字典数组将19个指标数据值转化为了整数型的索引值,加快了单次对比的速度。进一步的加速,则只能是避免采用冒泡大循环的方式,减少对比数量。
找出15个或以上的指标数据相同的条目,换而言之即找出4个及以下的指标数据不同的条目,对应于数学语言就是Sum(Combine(19, 15~19)) = Sum(Combine(19, 4~0))。进一步对问题的分析如下:
1、结合之前通过字典数组转化的办法,我们可以注意到对于每个指标数据而言,9586个条目被分为了若干个指标值相同的数组,这样一来整个数据就可以理解为这样的一个树形结构:根节点有19个子节点对应于19个指标,每个分支节点有若干个以指标值为区分的子节点,指标值子节点下又有若干个子节点对应于条目的编号。
2、查找的结果可以理解为符合条件的若干个条目编号对,这些编号对必然存在于指标值子节点下。可以对所有指标值子节点进行遍历,每个指标值子节点内的条目编号进行两两对比,也同样得可以获得结果,但这样的对比势必存在大量的重复。
3、对比的要求是19个指标中最多有4个不同,由组合的基本知识,其等价于19个指标中任意5个至少有1个是相同的。于是我们可以仅对比19个指标中所需对比次数最小的前5个就可以了。对于某一个指标的所需的对比次数的计算,是其下各指标值子节点所需对比次数的累加,而某一个指标值节点的对比次数则是其下的条目编号数量减1的平方。
通过以上的分析,我们可以采用如下的数据结构:- Private Type PARAMETER_INDEX
- Value As Double
- RowNums() As Long
- RowCount As Long
- End Type
- Private Type PARAMETER_INFO
- Name As String
- Indexes() As PARAMETER_INDEX
- IndexCount As Long
- DicValue As Object
- CmpCount As Long
- End Type
复制代码 主程序中的arrParameters数组为PARAMETER_INFO,对应了19个指标节点
其下的Indexes数组为PARAMETER_INDEX,对应了各指标节点下的指标值子节点
其下的RowNums数组则对应了条目编号子节点
具体的实现代码见附件。作为对比于前贴中冒泡大循环用时28秒,这样处理后仅需用时2秒!当然,这样的速度对比有些偏颇,因为大循环所需用时受数据本身特性影响较小。但考虑到该问题实际上是在检查水质监测数据的真实性,而真实的数据理当是十分分散的,如果数据是真实的话,那么这样的优化后执行效率的提升会是相当可观的。而冒泡式大循环则无论数据特性如何(或言真实与否),其对比次数是固定的,即用时仅取决于数据的数量。
补充内容 (2013-4-26 09:28):
还有提速的余地~
有兴趣的可以琢磨一下那个dicCompared的作用
补充内容 (2013-5-2 10:39):
改进后更快的实现可移步:
http://club.excelhome.net/thread-1007797-1-1.html
该贴中还有香川的另一种实现方法 |
评分
-
1
查看全部评分
-
|