【源码】文本_哈希去重独立版,1000万条只需5秒

纯的不能再纯的源码,完全用的易语言代码的方式写的,效率挺高的,1000万只需5秒,不过说是这么说,但是单条文本太长的话就要慢一些,总之比一般的去重都要快很多吧,而且这个是独立为1个子程序的,不需要什么模块 DLL啥的,写了我几个小时,免费分享给你们吧!有啥问题bug啥的评论区留言!
将保存文本数据改成了保存文本指针,减少了内存开销!,修复了文本指针为0(也就是数组里面存在空文本的情况)又又又更新了一下,将保存文本指针改成保存文本下标,效率又可以提升不少!

.版本 2
.支持库 spec

.子程序 文本_哈希去重, 整数型, 公开, 如果测试速度,请编译后测试,调试的话申请释放内存会很慢,太大的数据可能直接卡死  
.参数 文本数组, 文本型, 数组
.局部变量 链表地址, 整数型
.局部变量 链表长度, 整数型
.局部变量 键数量, 整数型
.局部变量 预设内存大小, 整数型
.局部变量 预设内存指针, 整数型
.局部变量 申请内存记录, 整数型, , "0"
.局部变量 扩容触发点, 整数型
.局部变量 表位置, 整数型
.局部变量 链表节点, 整数型
.局部变量 节点地址, 整数型
.局部变量 文本地址, 整数型
.局部变量 文本长度, 整数型
.局部变量 哈希值, 整数型
.局部变量 是否重复, 逻辑型
.局部变量 a, 整数型
.局部变量 b, 整数型
.局部变量 c, 整数型
.局部变量 d, 整数型
.局部变量 e, 整数型
.局部变量 f, 整数型
.局部变量 i, 整数型
.局部变量 j, 整数型

' 完全采用易代码写的哈希表去重方式,未使用任何模块,效率还可以


.如果真 (取数组成员数 (文本数组) ≤ 1)
    返回 (取数组成员数 (文本数组))
.如果真结束
' 定义表初始长度
链表长度 = 16
' 申请表的起始地址内存
链表地址 = 申请内存 (左移 (链表长度, 2), 真)

' 如果数组很大的话,比如10000+,预先申请一片内存区域,这里默认给了10000,不要设置太小就行了,10000内本来就很快
.如果真 (取数组成员数 (文本数组) > 10000)
    预设内存大小 = 取数组成员数 (文本数组) × 4
    加入成员 (申请内存记录, 申请内存 (预设内存大小, 真))
    预设内存指针 = 申请内存记录 [1]
.如果真结束

' 定义扩容触发点,负载因子为0.75自动扩容
扩容触发点 = 链表长度 × 0.75
' 循环添加文本键
.计次循环首 (取数组成员数 (文本数组), i)
    ' 取文本长度如果有更快的版本,可自行替换
    文本地址 = 取变量数据地址 (文本数组 <i>)
    .如果真 (文本地址 = 0)
        到循环尾 ()
    .如果真结束
    文本长度 = 取文本长度 (文本数组 <i>)

    ' 取哈希值
    c = 文本长度 \ 4
    d = 文本长度 % 4
    a = 十六进制 (“811c9dc5”)
    b = 十六进制 (“01000193”)
    e = 文本地址
    .如果真 (c ≠ 0)
        .计次循环首 (c, j)
            f = 指针到整数 (e)
            a = 位异或 (a, f) × b
            e = e + 4
        .计次循环尾 ()
    .如果真结束
    .如果真 (d ≠ 0)
        f = 左移 (指针到整数 (e), (4 - d) × 8)
        a = 位异或 (a, f) × b
    .如果真结束
    哈希值 = 取绝对值 (a)


    ' 取哈希值的余数获取表位置
    表位置 = 哈希值 % (链表长度 - 1) + 1

    ' 起始地址+表位置*4 为哈希值获取到的位置,从当前位置获取节点地址
    链表节点 = 链表地址 + 左移 (表位置, 2)
    节点地址 = 指针到整数 (链表节点)

    ' 获取到节点地址开始遍历节点
    .判断循环首 (节点地址 ≠ 0)
        .如果真 (哈希值 = 指针到整数 (节点地址))  ' 节点首地址为哈希值 如果哈希值相同则继续判断长度
            .如果真 (文本长度 = 指针到整数 (节点地址 + 8))  ' 节点地址+8 为长度 如果长度相同,则对比数据
                .如果真 (文本数组 <i> = 文本数组 [指针到整数 (节点地址 + 12)])  ' 节点地址+12 为文本下标,如果速度更快的对比方式可自行替换
                    是否重复 = 真
                    跳出循环 ()
                    ' 对比结果如果完全相同,则表示数据重复,直接跳出去循环下一条
                .如果真结束

            .如果真结束

        .如果真结束
        链表节点 = 节点地址 + 4  ' 节点地址+4为下一节点地址存放处
        节点地址 = 指针到整数 (链表节点)  ' 读下一节点地址,继续循环,直到节点地址=0
    .判断循环尾 ()
    .如果真 (是否重复 = 真)
        是否重复 = 假
        到循环尾 ()
    .如果真结束

    ' 经过上面对比,节点地址肯定=0 所以申请一个新地址为节点地址
    .如果 (预设内存指针 = 0)
        节点地址 = 申请内存 (16, 真)  ' 节点为16字节长度
        加入成员 (申请内存记录, 节点地址)  ' 将申请的指针保存起来,以便后面释放
    .否则

        ' 如果在程序开始预设了内存,则这里分配之前申请好的内存并更新指针
        .如果真 (预设内存大小 < 16)
            预设内存大小 = 取数组成员数 (文本数组) × 4
            加入成员 (申请内存记录, 申请内存 (预设内存大小, 真))
            预设内存指针 = 申请内存记录 [取数组成员数 (申请内存记录)]
        .如果真结束
        节点地址 = 预设内存指针
        预设内存指针 = 预设内存指针 + 16
        预设内存大小 = 预设内存大小 - 16
    .如果结束

    写到内存 (节点地址, 链表节点, )  ' 将新申请的地址与上一节点连接上

    ' 以下为链表结构
    ' 0 哈希值
    ' 4 下一节点指针,由于是新申请的,所以没有下一节点,留空
    ' 8 保存长度,以便于后面对比
    ' 12 保存下标,用作后面对比
    写到内存 (哈希值, 节点地址, )
    写到内存 (文本长度, 节点地址 + 8, )

    ' 将键数量递增,以便触发扩容
    键数量 = 键数量 + 1
    .如果真 (键数量 ≠ i)
        ' 将未重复的数组指针交换到当前键数量下标,就是把他放到前面去
        交换变量 (文本数组 [键数量], 文本数组 <i>)
    .如果真结束
    写到内存 (键数量, 节点地址 + 12, )
    ' 下面为扩容程序
    .如果真 (键数量 ≥ 扩容触发点)
        j = 左移 (链表长度, 1)
        f = 申请内存 (左移 (j, 2), 真)
        .变量循环首 (链表地址, 链表地址 + 左移 (链表长度 - 1, 2), 4, c)
            e = 指针到整数 (c)
            .判断循环首 (e ≠ 0)
                哈希值 = 指针到整数 (e)
                表位置 = 哈希值 % (j - 1) + 1
                a = f + 左移 (表位置, 2)
                b = 指针到整数 (a)
                .判断循环首 (b ≠ 0)
                    a = b + 4
                    b = 指针到整数 (a)
                .判断循环尾 ()
                写到内存 (e, a, )
                c = e + 4
                e = 指针到整数 (c)
                写到内存 (0, c, )
            .判断循环尾 ()
        .变量循环尾 ()
        ' 释放旧链表
        释放内存 (链表地址)
        链表地址 = f
        链表长度 = j
        扩容触发点 = 链表长度 × 0.75
    .如果真结束

.计次循环尾 ()

' 搞定,释放之前申请的全部内存
.计次循环首 (取数组成员数 (申请内存记录), i)
    释放内存 (申请内存记录 <i>)
.计次循环尾 ()
' 最后释放链表地址
释放内存 (链表地址)

' 由于之前把不重复的都放到了数组前面,这里直接重定义数组为键数量就行了
重定义数组 (文本数组, 真, 键数量)
返回 (键数量)

 

回帖下载:

请登录后发表评论

    没有回复内容