数字のリストのチェックサム

Question

私は多数の整数リストを持っています。リストのどれかが重複しているかどうかチェックしたい。私はこれを行う良い方法は、チェックサムが一致するかどうかを要素チェックで要素を行うだけで、基本的なチェックサムを計算することだと思っていた。しかし、私は良いプロパティを持つチェックサムアルゴリズムを見つけることができません：

• 効果的に順序を検証します。
• すぐに計算できます。
• 小さな結果、たとえば短い整数を返します。
• かなり均一な分布をしており、異なるリストが一致する可能性が低くなります。

たとえば、次の5回の呼び出しで[0,65536]の範囲内の異なる番号を返した関数check_sumが理想的です。

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ヘッダのチェックサムアルゴリズムを見ました。

私はPythonで実装するつもりですが、どのようなフォーマットでもアルゴリズムやポインタを参考資料として使用します。

Answer 1

はhash()でチェックサムを計算します。

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

はあなたが持っているどのように多くの重複を知るために：

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

Answer 2

は、あなたが何かの手織りをしたい場合：

from collections import Counter 

counts = Counter(checksums) 

はユニークなリストをコンパイルするには、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]) 
)