|
|
楼主 |
发表于 2013-4-11 13:03
|
显示全部楼层
本帖最后由 lee1892 于 2013-4-16 12:13 编辑
使用正确的数据结构的例子（四）由28秒到2秒！
本贴附件：
水样监测_使用数据结构加速 by Lee1892.rar
(353.63 KB, 下载次数: 763)
示例原贴：[求助] 紧急求助高手，如何解决这个水样监测统计，字典法可能最好！
相关的初步讨论：[原创] 申明变量与否及何种变量对代码执行速度的对比
示例的简短介绍：
该贴原始数据中有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
其下的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
查看全部评分
-
|
楼主: lee1892
[复制链接]
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2013-4-10 17:57
