集合是VBA/VB内置的一个类,类数据结构用的是平衡二叉树和双向链表,关键字用二叉树实现快速插入/删除和查询,二叉树的查找本质是二分查找,查找,插入和'删除的效率都是O(logn),集合的索引位置用的双向链表,时间复杂度是 O(n). 所以,集合操作当涉及索引位置的时候,时间都是比较感人的. 另外,集合还有不能查询关键字是否存在,关键字和位置索引不能互查,Item属性是只读等缺点.
跳表,是一个增加了向前指针的链表,全称叫做跳跃表,简称跳表.跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找.跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。跳表的查询,插入和删除的时间复杂度都是O(logn).
本类CollectionEx使用跳表数据结构模拟VBA的集合Collection,关键字用一个单向跳表,位置索引用一个双向跳表, 实现快速插入/删除以及查询.相对VBA的集合,增加了查询关键字,关键字和位置索引互查,Item属性可读写,以及增加For...Each和Do...Loop两种枚举迭代功能.
两个集合进行比较,所有涉及位置索引的操作,增加,删除还有查询,CollectionEx都比Collection快出好多倍,数据越多,快得越明显. 如果是涉及关键字的操作,还是VBA/VB的集合快,快的倍数恒定,因为二叉树和跳表的时间复杂度都是O(logn),VB的集合用的C语言编写,这是语言本身的速度差异造成的. 如果对速度有高要求,可以考虑用哈希表来处理关键字, 那么关键字的操作应该会比集合快,等有时间再重新编写一个吧.
|
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2022-7-16 14:41
楼主
