python - 数字列表的校验和

Question

我有大量整数列表。我想检查是否有任何列表重复。我在想这样做的一个好方法是计算一个基本的校验和，然后只在校验和一致的情况下逐个元素地检查。但是我找不到具有良好特性的校验和算法，即:

• 有效地验证订单；
• 计算速度快；
• 返回一个小的结果，例如短整型；
• 分布相当均匀，不同列表重合的可能性很小。

例如，函数 check_sum 为以下 5 次调用返回范围 [0,65536] 中的不同数字将是理想的。

check_sum([1,2,3,4,5])
check_sum([1,2,3,5,4])
check_sum([5,4,3,2,1])
check_sum([1,2,3,4,4])

我查看了 IPv4 header 校验和算法，它返回大小正确的结果但不检查顺序，所以不是我要找的。

我将在 python 中实现它，但任何格式都适用于算法，或指向好的引用资料的指针。

Answer 1

如果您想要简单的东西，可以使用 Fletcher 校验和的版本。

def check_sum(l):
    sum1 = sum2 = 0
    for v in l:
        sum1 = (sum1 + v) % 255
        sum2 = (sum2 + sum1) % 255
    return sum1*256 + sum2

print(
    check_sum([1,2,3,4,5]),
    check_sum([1,2,3,5,4]),
    check_sum([5,4,3,2,1]),
    check_sum([1,2,3,4,4])
)