数字列表的校验和

Question

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

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

例如，函数 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 校验和算法，该算法 returns 大小合适但不检查顺序，所以不是我要找的。

我将在 python 中实现它，但任何格式都适用于算法，或指向一个好的参考的指针 material。

Answer 1

计算校验和 hash():

checksums = \
    list(
        map(
            lambda l:
                hash(tuple(l)),
            list_of_lists
        )
    )

要知道你有多少重复：

from collections import Counter

counts = Counter(checksums)

要编译一个独特的列表：

unique_list = list(dict(zip(checksums, list_of_lists)).values())

Answer 2

如果您想要简单的东西，可以使用 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])
)

Answer 3

应该是mod256？

 def check_sum(l):
    sum1 = sum2 = 0
    for v in l:
        sum1 = (sum1 + v) % 256
        sum2 = (sum2 + sum1) % 256
    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])
)

数字列表的校验和

Checksum for a list of numbers

python

algorithm

checksum