基于哈希查找的老窖字典

aman1516

三坛老窖 发表于 2017-10-2 00:03
看你的提问，估计你也是在琢磨一维下料问题。
“若每个数据前面方案用过之后，后面不能再用”
这个可以 ...

老师高明，猜对了大半，其实也是关于一维下料，但又不是，我最终的结果，是设定一定范围内的的目标值（例如3000~6000（材料长度）.每步长100为一个目标值（规格））然后用大量数据测试，循环按算法跑出每一个目标值的“最小余料”，通过对比，最终确定“最小余料”的那一个目标值就是最适宜材料规格。我要的是优化选料方案，并不是一种或两种规格材料的开料优化方案。
香川老师的背包算法早有拜读，但与我的要求也有所不同。

三坛老窖

wzsy2_mrf 发表于 2017-10-1 11:41
一旦超过10万，就直接用sql好了，我想微软也是这么考虑的。

计算机的内存是有限的，当内存不足以装载程序运行所需的相关数据时，就需要考虑将其存放在硬盘等外存中，为提高对外存中数据的存取效率，才有了数据库，进而有了SQL。显而易见，用数据库+SQL的好处是不受空间限制（外存容量可视为无穷大），但就效率而言，远不如使用内存存放数据。所以，只有当你的应用所需的存储空间用内存不能解决时，不得已才使用数据库+SQL。
微软是很牛，我们都是在其提供的平台上工作的，但也别把它神话了，它不可能把每种应用情景都考虑到，要不它还提供VBA开发平台干嘛。
一楼附件中的两个应用实例，凑数的那个显然不适合用SQL来解决的，提取不重复数据的那个，倒是可用SQL，但效率比用字典就差远了。

wl-w.l

必须赞一个！！！

zbaigao

在学校学过点数据结构皮毛的我，看到了哈希字典的vb实现，还是很佩服的

ivccav

这么好的贴，应该让更多人看到

三坛老窖

主楼不让编辑了，升级版的字典只能发这儿了。
----------------------------------------------------------
老窖字典v5.rar (55.48 KB, 下载次数: 148)

2018-2-7 14:54 上传

点击文件名下载附件

----------------------------------------------------------

升级内容：
1、导入了Zamyi发掘的API hash函数
2、碰撞处理由线性探测法改为链接法

升级后，因为使用了性能极佳的API hash函数，字典性能也相应的提升了一大截，使用这个API函数后，在小数据量（10万以下）的情况下，速度也不输给VBScript字典；碰撞处理改为链接法，使得字典的存、取、删逻辑更为清晰，代码也更为简洁，相比线性探测法，从我对100万随机数据存入字典，所显示的指标来看速度也应有所提升（未测试比较）。
100随机数据存入字典的指标值（字典尺寸100万，刚好存满）
哈希表占位比%：62%
平均查找次数：1.50次
最大查找次数：8-9次

这三个指标值，比较有意思，当字典尺寸（字典装满）变大，哈希表占位比收敛于61.8%，平均查找次数收敛于1.5，最大查找次数应该是：系数*ln(n)，以上只是我的推测，看是否有坛友能从理论上证明我的推测成立与否。

灰袍法师在某个帖中曾说过，一个设计良好的hash查找，平均查找次数是1.7次，看来我这个能达到优秀了，呵呵……

lxw6

三坛老窖 发表于 2018-2-7 16:06
主楼不让编辑了，升级版的字典只能发这儿了。
-------------------------------------------------------- ...

1. 支持字典的嵌套吗？
2. 支持64位excel吗？我看好像没有写兼容语句：
#if VBA6 AND WIN64 THEN

#else

#endif

三坛老窖

lxw6 发表于 2018-3-20 23:10
1. 支持字典的嵌套吗？
2. 支持64位excel吗？我看好像没有写兼容语句：
#if VBA6 AND WIN64 THEN

1. 支持字典的嵌套吗？
答：支持。除不能用对象做关键字外，所有VBScript字典支持的功能，都支持。
（答错了！上面的字典不支持字典嵌套）
2. 支持64位excel吗？...
答：我没有试过，估计不支持。如果你是64位系统，你可自己改一下代码，应该没有难度的。

lxw6

三坛老窖 发表于 2018-3-21 21:25
1. 支持字典的嵌套吗？
答：支持。除不能用对象做关键字外，所有VBScript字典支持的功能，都支持。

我使用excel2016 64位测试的，支持！
不过，速度没有你宣传的快。可能跟测试方法有关。
我是两列数匹配。从1000000开始顺序往下排。下面是测试结果：
前面是VBScripit字典耗时，后面是老窖字典耗时。
1. 1万数据：0.1s，0.2s
2. 5万数据：0.3s,0.8s
3. 10万数据：0.9s,1.5s
4. 20万数据：3.4s,3,1s
4. 50万数据：23.5s,7.3s
5. 100万数据：105s,14.8s
只有超过20万时才有明显优势。

三坛老窖

lxw6 发表于 2018-3-21 22:05
我使用excel2016 64位测试的，支持！
不过，速度没有你宣传的快。可能跟测试方法有关。
我是两列数匹配 ...

应该不会这么慢呀？能把你的测试代码发上来看一下吗？
目前能想到是，可能是你代码中没有设置字典尺寸，如果没有设置，则在存入条目时，字典会不断的扩容，这会严重影响字典的速度。