7

我有一个大小为 4、9、16 或 25 的数组（根据输入），数组中的数字相同但减一（如果数组大小为 9，则数组中的最大元素为8）数字以0开头， 我想做一些算法来为数组生成某种校验和，这样我就可以比较两个数组是否相等，而无需遍历整个数组并逐个检查每个元素。

我在哪里可以得到这样的信息？我需要一些尽可能简单的东西。谢谢你。

编辑：只是为了清楚我想要什么：

-数组中的所有数字都是不同的，因此[0,1,1,2]无效，因为存在重复元素（1）

- 数字的位置很重要，因此 [0,1,2,3] 与 [3,2,1,0] 不同

- 数组将包含数字 0，因此也应考虑到这一点。

编辑：

好的，我尝试在这里实现弗莱彻的算法： http ://en.wikipedia.org/wiki/Fletcher%27s_checksum#Straightforward

int fletcher(int array[], int size){
  int i;
  int sum1=0;
  int sum2=0;
  for(i=0;i<size;i++){
    sum1=(sum1+array[i])%255;
    sum2=(sum2+sum1)%255;
  }
  return (sum2 << 8) | sum1;
}

老实说，我不知道返回线是做什么的，但不幸的是，该算法不起作用。对于数组 [2,1,3,0] 和 [1,3,2,0] 我得到相同的校验和。

编辑2：

好的，这是另一个，阿德勒校验和 http://en.wikipedia.org/wiki/Adler-32#Example_implementation

#define MOD 65521;

unsigned long adler(int array[], int size){
  int i;
  unsigned long a=1;
  unsigned long b=0;
  for(i=0;i<size;i++){
    a=(a+array[i])%MOD;
    b=(b+a)%MOD;
  }
  return (b <<16) | a;
}

这也行不通。数组 [2,0,3,1] 和 [1,3,0,2] 生成相同的校验和。我在这里失去了希望，有什么想法吗？

4

5 回答 5

5

让我们以您的 25 个整数数组为例。你解释说它可以包含唯一整数 0 到 24 的任何排列。根据这个页面，有 25！（25 个阶乘）可能的排列，即 15511210043330985984000000。远远超过 32 位整数可以包含的内容。

结论是，无论你怎么努力，都会发生碰撞。

现在，这是一个解释位置的简单算法：

int checksum(int[] array, int size) {
  int c = 0;
  for(int i = 0; i < size; i++) {
    c += array[i];
    c = c << 3 | c >> (32 - 3); // rotate a little
    c ^= 0xFFFFFFFF; // invert just for fun
  }
  return c;
}
于 2012-06-05T10:17:15.783 回答
1

我认为您想要的是以下线程的答案：

快速排列 -> 数字 -> 排列映射算法

您只需将排列映射到的数字作为校验和。由于每个排列只有一个校验和，因此不可能有更小的无冲突校验和。

于 2012-06-05T08:10:36.130 回答
1

加权和的校验和怎么样？让我们以 [0,1,2,3] 为例。首先选择种子和限制，我们选择种子为 7，限制为 10000007。

a[4] = {0, 1, 2, 3}
limit = 10000007, seed = 7
result = 0
result = ((result + a[0]) * seed) % limit = ((0 + 0) * 7)) % 10000007 = 0
result = ((result + a[1]) * seed) % limit = ((0 + 1) * 7)) % 10000007 = 7
result = ((result + a[2]) * seed) % limit = ((7 + 2) * 7)) % 10000007 = 63
result = ((result + a[3]) * seed) % limit = ((63 + 3) * 7)) % 10000007 = 462

对于 [0, 1, 2, 3]，您的校验和为 462。参考是http://www.codeabbey.com/index/wiki/checksum

于 2015-05-15T08:21:43.100 回答
0

据我了解，您的数组包含从 0 到N-1. 一种有用的校验和是数组在其字典顺序中的排名。这是什么意思 ？鉴于0, 1, 2 您有可能的排列

  1: 0, 1, 2
  2: 0, 2, 1
  3: 1, 0, 2
  4: 1, 2, 0
  5: 2, 0, 1
  6: 2, 1, 0

校验和将是第一个数字，并在您创建数组时计算。中提出了解决方案

按字典顺序在排列列表中查找给定排列的索引

这可能会有所帮助，尽管最好的算法似乎具有二次复杂度。要将其提高到线性复杂度，您应该事先缓存阶乘的值。

优势？零碰撞。

编辑：计算 该值就像多项式的评估，其中阶乘用于单项式而不是幂。所以函数是

f(x0,....,xn-1) = X0 * (0!) + X1 * (1!) + X2 * (2!) +...+ Xn-1 * (n-1!)

这个想法是使用每个值来获得排列的子范围，并使用足够的值来确定唯一的排列。

现在用于实现（如多项式之一）：

  1. 预计算 0!.... 到 n-1！在程序开始时
  2. 每次设置数组时，您都使用 f(elements) 来计算其校验和
  3. 您使用此校验和在 O(1) 中进行比较
于 2012-06-05T08:47:55.803 回答
0

对于从 1 到 N 的 N 个唯一整数的数组，只需将元素相加将始终为 N*(N+1)/2。因此，唯一的区别在于排序。如果通过“校验和”暗示您可以容忍一些冲突，那么一种方法是将连续数字之间的差异相加。例如，{1,2,3,4} 的 delta 校验和为 1+1+1=3，但 {4,3,2,1} 的 delta 校验和为 -1+-1+-1= -3。

没有对碰撞率或计算复杂性给出要求，但如果上述不适合，那么我建议使用与位置相关的校验和

于 2012-06-05T06:39:01.773 回答