|
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用 · 内置多项VBA编程加强工具 ★ 免费下载 ★ ★ 使用手册★
本帖最后由 三坛老窖 于 2017-10-1 19:45 编辑
混迹EH将近7年,从中受益良多。
每当实际工作中碰到自己难以解决的问题,在EH中一搜,总能找到较为满意的解决方案。
随着泡坛子时间的增长,自我感觉自己用在EH中学到的招数解决实际问题的能力也在增长。
虽未发过求助帖,然在坛中确实吸取了不少的养分。
是故常怀忐忑之心,总想着写个帖子,与坛友们分享点实用的或有价值的东西,以回报EH。
奈何一直没有找到合适的题目,故而至今仍然是白丁一枚。
前不久,在一个贴之中,帮人解决一个循环凑数的问题,其中用到字典,发现当数据量稍大时,VBScript字典就有些力不从心了。
联想到几年前,灰袍法师有个帖子,号召大家用哈希原理创建自己的字典,当年初看时,感觉是高深莫测,再看后更是一头雾水。
好在还有些印象:在数据量较大时,借助哈希表可大大的提高查找速度。
花了些时间,终于整明白了哈希原理。
再在坛中一搜,发现除灰袍法师的号召外,好像没有哪位大侠写过基于哈希原理的字典。
再对VBScript字典进行测试,发现其查找机制并非使用哈希原理的(至今没有查到VBScript字典的内在查找机制,但基本可以肯定不是哈希查找,据我推断,可能是链表形式的二分查找树之类的查找机制。在这一点上,包括灰袍法师在内的众多大侠,都存在着对VBScript字典的认识错误)。
又花了些时间,自制了一个基于哈希查找的字典,暂且命名为:老窖字典。
其功能完全兼容VBScript字典,即使用VBScript字典的代码,只要将字典对象的引用改为老窖字典即可。
与VBScript字典性能比较:
1:时间方面:
当数据量(字典条目数,下同)在10万以内时,每存/取/查一个数据,VBScript字典略快,但也差异不大;
当数据量大于10万时,随着数据量的增大,老窖字典渐显优势;
当数据量达到100万时,每存/取/查一个数据,老窖字典所耗时间是VBScript字典的1/25;
当数据量达到200万时,每存/取/查一个数据,老窖字典所耗时间是VBScript字典的1/50;
总之,字典保存数据量越大,每存/取/查一个数据所耗时间,老窖字典相比VBScript字典优势越明显。
VBScript字典的存/取/查一个数据的时间复杂性是:O(n) (n为当时字典已装载的数据量)
老窖字典的存/取/查一个数据的时间复杂性是:O(1) (与字典已装载的数据量无关)
2、空间方面:
老窖字典是基于哈希查找的,所以有一个哈希表所占有空间的冗余,另外为了使在字典扩容后加快重置哈希表的速度,在字典条目上附加了一个哈希码的字段(也作删除标记用),冗余百分比与哈希表尺寸与字典尺寸之比有关,默认情况下,哈希表尺寸与字典尺寸之比取1.618,按此计算冗余百分比为:(4+4×1.618)/(16+16+4+4×1.618)= 24.66%。
VBScript字典,未知
本想从哈希原理开始,到字典内部的数据结构、各功能的实现过程等等作一番展开介绍,奈何本人表述能力有限(上面的文字,几乎用上了吃奶的劲才挤出来的,特别敬佩和羡慕坛中的某几位大侠,噼里啪啦几下,就能整出一篇高质量的帖子,把一个问题解剖的一清二楚),故而就此打住,直接上附件!
-------------------------------------------------------
老窖字典.rar
(1.24 MB, 下载次数: 1130)
-------------------------------------------------------
附注: 若在使用过程中发现老窖字典存在Bug,望能跟贴反馈,老窖将十分感激!
若在使用过程中有什么疑问的,欢迎跟贴提交,老窖将尽力解答。
字典代码封装在一个类中,其中有较为规范的注释,若诸位大侠有兴趣探讨其中的实现过程,以优化字典的性能,将十分的欢迎。
补充内容 (2018-2-7 16:11):
升级版在26楼
补充内容 (2018-4-8 15:03):
修正了一个在Item中保存对象的BUG,在46楼。
补充内容 (2018-4-8 15:04):
修正了一个在Item中保存对象的BUG,在46楼。
补充内容 (2018-4-8 15:05):
修正了在Item中保存对象的BUG,在46楼。 |
评分
-
14
查看全部评分
-
|