Chinaunix

标题: [讨论]快速识别特殊数据重复的算法 [打印本页]

作者: nully 时间: 2007-04-02 19:32
标题: [讨论]快速识别特殊数据重复的算法
对于海量的整形数据，它的构造非常特殊：
1.最大为十位数
2.各个位的数字不会相同

也就是说，这些数据里最大的一个数是 9876543210

遍历这些数据，找出重复的数字

传统的，最快的建一个有9876543210'位'的状态表，这样占的空间太大
慢一点的，用普通哈希表，这样又怕时间上还达不到要求

能不能在数字特殊性上找到一些规率并得到更好的算法？

作者: ArXoR 时间: 2007-04-03 16:02
实际上状态空间就是一个全排列的空间,
状态数10! = 3628800.
整个信息量还是不大的, 可以构造一个perfect hash function的,
因为可以很快的确定某个排列是第几个排列,
也可以很快的构造第n个排列.

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)