精易论坛
标题: 折腾了一个相当高效的数组去重算法 [打印本页]
作者: SAHI9099 时间: 2019-7-29 11:55
标题: 折腾了一个相当高效的数组去重算法
本帖最后由 SAHI9099 于 2019-7-29 12:58 编辑
原型是不带零的无符号整数型去重算法，原理超简单也因为原理的问题，限制了数组元素的范围必须在1~2147483647之间，并且需要大致知道元素的最大值
1亿随机数组的去重速度
思路完全是我自己想出来的，经过了五次调整和改进。。
所以我刚才又改了一次，那么现在是第六次，优化了内存占用
算法原型
| 变量名 | 类 型 | 静态 | 数组 | 备 注 |
| arr | 整数型 | | 0 |
| i | 整数型 | | |
| k | 整数型 | | |
如果真 (是否为空 (最大值
))
最大值 ＝ 2147483647
如果 (最大值 ＜ 1
或 最大值 ＞ 2147483647
)
返回 (假)
重定义数组 (arr, 假, 最大值
)
计次循环首 (取数组成员数 (数组
), i
)如果真 (arr
[数组
[i
]] ＝ 0
)arr
[数组
[i
]] ＝ 1
k ＝ k ＋ 1
数组
[k
] ＝ 数组
[i
]
计次循环尾 ()[/i][/i][/i][i][i][i]重定义数组 (数组, 真, k
)[/i][/i][/i][i][i][i]返回 (真)
萌新不会发帖大佬多多担待
补充内容 (2019-7-30 10:38):
对了，函数里的arr变量可以改为字节型数组，内存占用比整数型数组要小
补充内容 (2019-7-30 10:53):
还有利用原理的特性可以直接给下边接排序 大概是 计次循环 取数组成员数arr 然后判断为1则k++再把i写到原数组的k位置
作者: SAHI9099 时间: 2019-7-29 11:59
好像挂了两张图
内存占用
一亿数组的速度
作者: SAHI9099 时间: 2019-7-29 12:08
那个。。原型发错图了，上边那个并不能正常使用
|
| 数组去重 | 逻辑型 | |
|
| 数组 | 整数型 | | | |
接收数组 | 整数型 | | | | 最大值 | 整数型 | | | |
| 变量名 | 类 型 | 静态 | 数组 | 备 注 |
| arr | 整数型 | | 0 |
| i | 整数型 | | |
| 数组上限 | 整数型 | | |
如果真 (是否为空 (最大值
))
最大值 ＝ 2147483647
如果 (最大值 ＜ 1
或 最大值 ＞ 2147483647
)返回 (假)重定义数组 (arr, 假, 最大值
)
重定义数组 (接收数组, 假,
取数组成员数 (数组
))
计次循环首 (取数组成员数 (数组
), i
)如果真 (arr
[数组
[i
]] ＝ 0
)arr
[数组
[i
]] ＝ 1
数组上限 ＝ 数组上限 ＋ 1
接收数组
[数组上限
] ＝ 数组
[i
]计次循环尾 ()重定义数组 (接收数组, 真, 数组上限
)返回 (真)
作者: SAHI9099 时间: 2019-7-29 12:20
帖子已经修改过了，这个怎么删掉啊
作者: SAHI9099 时间: 2019-7-29 14:12
这是另一个思路，通用型的。不过效率嘛就有点GG了，占用时间的是给bin连续赋值
| 变量名 | 类 型 | 静态 | 数组 | 备 注 |
| bin | 字节集 | | |
| temp | 字节集 | | |
| i | 整数型 | | |
| k | 整数型 | | |
计次循环首 (取数组成员数 (数组
), i
)temp ＝
{ 0
} ＋
到字节集 (数组
[i
]) ＋
{ 0
}如果真 (寻找字节集 (bin, temp,
) ＝ -1
)bin ＝ bin ＋ temp
k ＝ k ＋ 1
数组
[k
] ＝ 数组
[i
]计次循环尾 ()重定义数组 (数组, 真, k
)返回 (0
)
作者: sampo 时间: 2019-7-29 16:45
什么情况？这么多楼那个是真的？
作者: 消除某种情绪 时间: 2019-7-29 19:07
打死不做白嫖党！
作者: huaidan2015 时间: 2019-7-29 22:51
so 到底下哪个？？
作者: kyo9766 时间: 2019-7-30 08:53
各位看官，可能都有点懵了。。。
作者: 血舞神州 时间: 2019-7-30 09:35
谢谢分享·
作者: SAHI9099 时间: 2019-7-30 11:52
本帖最后由 SAHI9099 于 2019-7-30 12:00 编辑
第七次改进，嗯。。再次优化内存占用问题这下就可以快速去重类似于手机号的长整数型数组了
| 变量名 | 类 型 | 静态 | 数组 | 备 注 |
| i | 整数型 | | |
| k | 整数型 | | |
| arr | 字节型 | | 0 |
| min | 整数型 | | |
| max | 整数型 | | |
如果 (取数组成员数 (数组
) ＝ 0
)返回 (假)连续赋值 (数组
[1
], min, max
)计次循环首 (取数组成员数 (数组
), i
)如果真 (数组
[i
] ＜ min
)min ＝ 数组
[i
]如果真 (数组
[i
] ＞ max
)max ＝ 数组
[i
]计次循环尾 ()如果真 (max － min ＞ 1000000000
)返回 (假)min ＝ min － 1重定义数组 (arr, 假, max － min
)计次循环首 (取数组成员数 (数组
), i
)如果真 (arr
[数组
[i
] － min
] ＝ 0
)arr
[数组
[i
] － min
] ＝ 1
k ＝ k ＋ 1
数组
[k
] ＝ 数组
[i
]计次循环尾 ()重定义数组 (数组, 真, k
)返回 (真)
作者: 外星星人 时间: 2019-7-30 14:00
感谢分享
作者: 1051496412 时间: 2019-7-30 14:25
原理类似桶排序，感谢分享
作者: wuqingg 时间: 2019-7-30 18:24
支持开源，感谢分享！
作者: 名字没想好 时间: 2019-7-30 21:07
提示: 作者被禁止或删除 内容自动屏蔽
作者: 毛超 时间: 2019-7-31 09:36
感谢分享！！！！！！！！！！
作者: 沧海生烟 时间: 2019-8-1 18:23
你这个测试时 第一次慢 第二次以后，要比第一次快6-7倍？这是什么情况
作者: 沧海生烟 时间: 2019-8-1 18:24
第一次比精易的 慢3倍左右 第二次后的每次，比精易的快2倍多点
作者: 283688410 时间: 2019-8-1 20:17
好东西要支持，谢谢楼主分享
作者: SAHI9099 时间: 2019-8-2 02:08
这个算法是我给我的软件量身定做的感觉不错就发上来了，具体应用场景还是要看你的数组长啥样，比如{1，99999999，99999999，10000000}这种的你完全可以使用别的算法，使用上述算法就是浪费内存了
| 欢迎光临 精易论坛 (https://125.confly.eu.org/) |
Powered by Discuz! X3.4 |