精易论坛

标题: 极速统计数组重复并分类(9.12更新) [打印本页]

作者: birdmanxp    时间: 2015-9-11 21:54
标题: 极速统计数组重复并分类(9.12更新)
本帖最后由 birdmanxp 于 2015-9-12 10:53 编辑

之前看到有个定制帖
  1. 数组取每个成员重复次数,并分类列出  数组可呢个比较大 有10万成员左右
复制代码

感觉很有挑战意义,虽然有人已经接单完成了,但因为这种情况很典型,所以有必要跟易友交流互相促进
先讲下算法吧
主要里利用“节点”的特性优化速度,此法速度也许算不上最快的,但算法肯定是最简单的
节点特性1:节点类似与哈希表,当向节点内加入一个新属性时,返回成功,当向节点内加入一个已存在的同名属性时则返回失败,利用这个特性可以很容易判断数组成员是不是重复
节点特性2:虽然无法加入同名的属性,但却可以修同名属性的属性值,利用这点可以记录每个数组成员的重复次数
由此可见,只需要一次计次循环就能完成数组去重+分类统计重复次数,相对于嵌套多层循环比对的方法效率要高得多

根据反复测试的结果,发现一个重要的规律
当数组成员数一样时,统计耗时跟去重后的成员数成反比,也就是说同样为10万数组,去重后为1000个成员的耗时比去重后为100个成员耗时多8~10倍左右
为什么会有这种规律?应该是节点的另一个特性:加入新属性耗时修改已有的属性值要慢得多

以上为本人的一点愚见,欢迎有大神可以分享效率更高的算法。
9.12日重要更新
根据@猥琐小胖子和@ANJIANTEST大神的提示,增加了哈希表法,对于完全不重复的数组统计的效率要比节点法高几百倍(1秒内可以完成10万数组统计分类)。

旧版源码回复可见
新版源码回复可见





补充内容 (2015-10-5 19:29):
2015.10.5修复哈希表统计错误的bug,感谢@兮若残伤的反馈!

补充内容 (2015-10-5 19:38):
请到77楼下载最新修复的源码!

统计重复.rar

18.04 KB, 下载次数: 336, 下载积分: 精币 -2 枚


作者: oldlee    时间: 2015-9-11 21:56
沙发我的,前排围观大神
作者: ANJIANTEST    时间: 2015-9-11 22:00
来看看   你这个目测最大值如果是10w会慢很多
作者: 人辞    时间: 2015-9-11 22:04
看看、、、、
作者: ANJIANTEST    时间: 2015-9-11 22:15
思路都一样的,只是换成高效的hash表就是了.
作者: birdmanxp    时间: 2015-9-11 22:18
ANJIANTEST 发表于 2015-9-11 22:15
思路都一样的,只是换成高效的hash表就是了.

多谢指点,哈希表真不熟悉,我研究下
作者: 阿星Star    时间: 2015-9-11 22:27
看看思路   谢谢了

作者: 猥琐小胖子    时间: 2015-9-11 22:35
一直用第3个方法。之前用节点的筛选数组的数据好慢。还没10w那么多。 文本去重复3个方法.rar (25.34 KB, 下载次数: 17)