VBA编程技巧 之 浅谈数据结构 （不定期持续更新，最后更新130411）

lskvslgt

lee1892 发表于 2012-12-18 15:26
迭代（Iteration）与递归（Recursion）

在我们讲数据结构之前，先作一下思维训练。经常看到有人说什么递 ...

从数学角度而言，所谓迭代可以指函数迭代的过程，即反复的运用同一函数计算，前一次迭代得到的结果被用于作为下一次迭代的输入。   迭代  ，太精彩了。一直让“迭代”困扰着，虽然代码不会写，但是原理明白了。谢谢老师。

840205910

确实好贴，只是不能静下心来看懂

lee1892

使用正确的数据结构的例子（一）

此帖附件： 彭希仁的汇总表.rar (456.93 KB, 下载次数: 720)

2013-2-2 11:45 上传

点击文件名下载附件

需在VBE内添加Microsoft Scripting Runtime引用

翻到一个久远的帖子，正好可以用来说明如下观点：
1、好的代码应该具备：可读性、易维护性、通用性、易扩展功能等特性。
2、简短的代码并不意味着执行效率的提升，事实上在很多情况下，恰恰相反！
3、正确的使用数据结构是十分重要的。

原贴地址：http://club.excelhome.net/thread-281621-1-1.html

该贴楼主提出了一个如下图的数据提供和统计需要



可以看到，数据分为三列，分别为省份名、机型编号和故障类型，每一条记录代表出现该故障一次。要求统计不同机型各类故障出现的次数及其占比，并列出该故障出现次数最多的前三个省份和次数值。

我将该贴的代码全部收集到附件里，以进行对比，并采用了该贴内提供的6万+条数据供测试。同时进行了强度测试，即将数据源通过循环读取扩展为60万+乃至600万+。

测试的对比结果完全验证了正确使用数据结构的重要性。

实际上，表现最为良好的“树形数据结构_多字典”是我写的第一段代码，很明显的这段代码是可读性最强、扩展功能也最容易的了。

原贴中有人提到了通用性，我的看法是真正的通用性意味着列的扩展，即属性的扩展或是类别的扩展，这样的不确定的扩展意味着树形结构的层数以及每层含义的不确定。如果要达到代码能够适应这样的不确定性，受VBA自定义数据类型不能自循环定义的限制，我所能想到的办法只能是通过字典的嵌套来动态构建树形数据结构了，关于这个的讨论可参考我的字典的帖子。

原贴的讨论中，只有一位朋友提到了使用自定义数据类型来构造树形数据结构，可惜的是他的代码不能正确运行，而代码本身的可读性太差，我也就没兴趣替他改了。

306445391

收藏了，好好学习下

大树_zhao

正在学习VBA，也来凑个热闹

yiyiyicz

lee1892 发表于 2012-12-18 15:26
迭代（Iteration）与递归（Recursion）

在我们讲数据结构之前，先作一下思维训练。经常看到有人说什么递 ...

递归次数怎么计算啊？
比如4阶的，物料项有几百项的BOM展开计算，有什么方法来计算递归次数？
还有，递归要占用内存，怎么估计做一个BOM展开计算，大概要消耗多少内存？别弄不好崩溃了

yygpdkkk

虽然很多人看不懂(俺也是)，仍觉得此贴应加精。唉，委屈此贴了。

gshmxx

学习了{:soso_e179:}

lee1892

使用正确的数据结构的例子（二）

本贴附件： 地理信息的网格查找示例 By Lee1892.rar (155.94 KB, 下载次数: 471)

2013-3-11 12:54 上传

点击文件名下载附件

看到一个有些意思的帖子：[求助] 查找离基站最近(且距离不为0)的站点(求老师帮忙优化一下代码，提高效率)

该帖楼主有基站经纬度数据若干，另有一组工具站数据，要求对工具站查找距离最近且距离不为0的基站。

该帖中楼主采用大循环的方法，即对每个工具站逐个对比所有基站的距离，导致耗时过长。其主要原因除了循环次数过多外，根据两点经纬度计算距离占用时间较长是很重要的因素。

很显然逐个对比所有基站是不可取的，一个非常朴素的思路是按地理位置划分等距的正方形网格，这样只需要按网格对比较近的基站就可以了。实际上，这也是一种分而治之的思路。

我在解答中给出的数据定义如下：
[code=vb]Private Type BASE_INFO
    CellIDs()   As String
    CellName    As String
    Longitude   As Double
    Latitude    As Double
End Type

Private Type GRID_INFO
    BasesNum    As Long
    BasesInd()  As Long
End Type

...
Dim arrBases()  As BASE_INFO, arrGrids() As GRID_INFO[/code]

基站数组包含了该站点的基础信息，并使用数组元素的序号作为该基站的链接索引值。而网格数组则是按网格步长设置的一个二维数组，记录了每个网格内基站的数量和基站索引数组。

这样一来，在对工具站进行距离查找时，就可以按工具站所在网格为中心，逐圈向外查找比对基站距离。但还需要有个校核的过程，因为网格是正方形的，所以需要在查找到有基站的圈后，再对外圈计算对比一次。

附件代码中按经纬度进行网格划分，并设置使用相同的经纬度网格步长。但应该注意到经纬度差对应的距离是不同的。此例中经纬度的0.001度差的距离分别为111m和100m，属于可接受的误差范围。

应该注意并理解到网格步长对代码执行速度的影响，步长越小则网格的初始化时间越长，同时内存占用更多，但相应的查找到的基站数量就越少，距离计算次数也就越少。

如果尝试使用更小的步长，则会导致内存不足。这是因为网格数组需要的是连续的内存分配，而无论某个网格内是否有基站，都被分配了内存。实际上，还可以进一步调整代码，仅保留有基站的网格，并对其网格地址使用字典对象来索引，就可以实现更小步长的使用以及更快的网格初始化。比如网格数组可定义为一个一维数组，其数据定义可形如：[code=vb]Private Type GRID_INFO
    LatAddress As Long
    LonAddress As Long
    BasesNum As Long
    BasesInd() As Long
End Type[/code]



补充内容 (2013-4-15 11:04):
类似问题的帖子还有：
计算与小区距离最近的点，及点是否为相关点

补充内容 (2013-4-15 11:05):
[url=http://club.excelhome.net/thread-893926-1-1.html距离计算，寻找一定距离范围内的两个属性关系[/url]

lee1892

接43楼的讨论。按43楼最后提到的改进方法，修改了代码，使用一个一维数组保存含有基站的网格，并用一个字典对象对其索引。
本贴附件： 地理信息的网格查找示例_改进网格数组 By Lee1892.rar (159.77 KB, 下载次数: 297)

2013-3-12 12:46 上传

点击文件名下载附件

第二步的初始化网格数组就变成下面的一小段：
[code=vb]    nMaxLatGrid = Int((Int(dblMaxLat) - Int(dblMinLat) + 1) / dGridStep) + 1
    nMaxLonGrid = Int((Int(dblMaxLon) - Int(dblMinLon) + 1) / dGridStep) + 1
    ReDim arrWithBaseGrids(1 To nCount)
    Set dicWithBaseGrids = CreateObject("Scripting.Dictionary")
[/code]

而第三步的分配基站至网格就会改为如下：
[code=vb]
    For i = 1 To nCount
        With arrBases(i)
            nLatGrid = Int((.Latitude - Int(dblMinLat)) / dGridStep) + 1
            nLonGrid = Int((.Longitude - Int(dblMinLon)) / dGridStep) + 1
        End With
        sGridAddress = nLatGrid & "," & nLonGrid
        If Not dicWithBaseGrids.Exists(sGridAddress) Then
            nGridCount = nGridCount + 1
            dicWithBaseGrids(sGridAddress) = nGridCount
            With arrWithBaseGrids(nGridCount)
                .BasesNum = 1
                ReDim .BasesInd(1 To 1)
                .BasesInd(1) = i
                .LatAddress = nLatGrid
                .LonAddress = nLonGrid
            End With
        Else
            nGridInd = dicWithBaseGrids(sGridAddress)
            With arrWithBaseGrids(nGridInd)
                .BasesNum = .BasesNum + 1
                ReDim Preserve .BasesInd(1 To .BasesNum)
                .BasesInd(.BasesNum) = i
            End With
        End If
    Next
    ReDim Preserve arrWithBaseGrids(1 To nGridCount)
[/code]

如此一来，网格的步长就可以随意改小而不用担心造成内存不足的问题。

但这又带来另一个问题，如果将网格改的很小，会导致基站对于网格而言非常稀疏，从而使得在对工作站逐圈搜索时效率非常低。显然找到一个合适的网格步长应该是代码完成的工作。附件的代码采用了如下的方法，原因可自行思考分析：
[code=vb]
    ' 计算较合适的网格步长
    dGridStep = (dblMaxLat - dblMinLat) / Sqr(nCount)
    If (dblMaxLon - dblMinLon) / Sqr(nCount) < dGridStep Then
        dGridStep = (dblMaxLon - dblMinLon) / Sqr(nCount)
    End If
    i = 0
    Do Until Round(dGridStep, i) > 0
        i = i + 1
    Loop
    dGridStep = Round(dGridStep, i)
    'dGridStep = GRID_STEP
[/code]


后续的思考：如果希望使用较小的网格划分，但获得较快的执行速度该如何处理？应该是对逐圈搜索这一段代码进行优化，优化方法则应该根据基站分布的特点有针对性的改进。