判断两个列表是否包含相同的数字项，而无需排序

Question

我有两个列表，需要确定它们是否包含相同的值，但不需要排序（即值的顺序无关紧要）。

我知道对它们进行排序可以解决问题，但这是一个性能关键的部分。

项目值在[-2，63]范围内，并且我们总是比较相同大小的列表，但列表大小范围为[1,8]。

示例列表：

A = (0,   0, 4, 23, 10)
B = (23, 10, 0,  4,  0)
C = (0,   0, 4, 27, 10)

A == B is true
A == C is false

---

我认为一个可能的解决方案是比较两个列表的乘积（将所有值相乘），但这种解决方案存在问题。如何处理零和负数。一种解决方法是在乘法之前给每个值加上4。以下是我目前拥有的代码。

bool equal(int A[], int B[], int size)
{
    int sumA = 1;
    int sumB = 1;

    for (int i = 0; i < size; i++) {
        sumA *= A[i] + 4;
        sumB *= B[i] + 4;
    }
    return (sumA == sumB)
}

但是，无论列表的顺序/内容如何，这总是有效的吗？换句话说，以下数学公式是否正确？所以我真正想问的是以下内容（除非有其他解决问题的方法）：

给定2个相等大小的列表。如果列表的乘积（将所有值相乘）相等，则只要值为大于0的整数，列表包含相同的值。

- Justin

---

乘法不起作用 [1, 12] == [3, 4] - Anon

判断它们是否相同将需要与排序相同的算法时间。你可能能够使用O(n)的算法，但如果可以的话，你也可以以同样快的速度进行排序。正如@Anon所说，乘法绝对行不通。 - JoshD

Answer 1

假设您提前知道范围，可以使用计数排序的变体。只需扫描每个数组并跟踪每个整数出现的次数即可。

Procedure Compare-Lists(A, B, min, max)
  domain := max - min
  Count := new int[domain]
  for i in A:
    Count[i - min] += 1
  for i in B:
    Count[i - min] -= 1
    if Count[i - min] < 0:
      // Something was in B but not A
      return "Different"
  for i in A:
    if Count[i - min] > 0:
      // Something was in A but not B
      return "Different"
  return "Same"

这是一个线性的O(len(A) + len(B))算法。

- Josh Lee

---

请注意，如果Count变为负数，您可以在B部分提前停止。 - schnaader

扫描两次每个数组？听起来很合理。实际上，你可以只是循环遍历 A、B，然后再遍历一遍 A。 - Josh Lee

运行时间是O(2*len(A)+len(B))对吧？而内存则为O(n)。那么我认为仅排序会更快一些？ - Justin

@Justin 当你知道有66个可能值中的8个元素时，大O符号有点无关紧要。但是，排序可能会更快。 - Josh Lee

@Justin：这也是我的想法（我在问题下发表了评论）。但正如@jleedev所指出的那样，由于项目数量很少，大O复杂度变得不那么相关。 - JoshD

Answer 2

您可以使用质数来实现此操作。为前66个质数保留一个质数表，并使用数组的元素（偏移+2）索引到质数表中。

然后，数组的标识仅是由数组中表示的质数的乘积。

不幸的是，必须用至少67位表示该乘积：

- 第66个质数是317，317的8次方=101,970,394,089,246,452,641 - log2（101,970,394,089,246,452,641）= 66.47（向上取整）是67位

以下是使用示例伪代码（假设存在int128数据类型）：

int primes[] = 
{
      2,   3,   5,   7,  11,  13,  17,  19,  23,  29,
     31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
     73,  79,  83,  89,  97, 101, 103, 107, 109, 113,
    127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
    179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
    233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
    283, 293, 307, 311, 313, 317
};

// Assumes:
// Each xs[i] is [-2, 63]
// length is [1, 8]
int128 identity(int xs[], int length)
{
    int128 product = 1;

    for (int i = 0; i < length; ++i)
    {
        product *= primes[xs[i] + 2];
    }

    return product;
}

bool equal(int a[], int b[], int size)
{
    return identity(a, size) == identity(b, size);
}

您可以尝试在GCC上使用long double来存储乘积，因为它被定义为80位数据类型，但我不确定浮点数乘法误差是否会导致列表之间的冲突。 我还没有验证过这一点。

---

我的先前解决方案不起作用，请参见下面的注释。

对于每个列表：

• 计算所有元素的和
• 计算所有元素的乘积
• 存储列表的长度（在您的情况下，由于两个列表的长度保证相同，因此可以完全忽略它）

在计算总和和乘积时，需要将每个元素调整为+3，因此您的范围现在是[1, 66]。

（总和，乘积，长度）元组是列表的标识符。任何具有相同标识符的列表都是相等的。

您可以将此（总和，乘积，长度）元组适配到单个64位数字中：

• 对于乘积：66⁸ = 360,040,606,269,696，log₂(360,040,606,269,696) = 48.36（向上取整）即 49位
• 对于总和：66 * 8 = 528，log₂(528) = 9.04（向上取整）即 10位
• 长度在[1,8]范围内，log₂(8) = 3位
• 49 + 10 + 3 = 表示标识符的62位

然后，您可以进行直接的64位比较来确定相等性。

运行时间与数组大小成线性关系，每个数组仅需单次通过。 内存使用量为O(1)。

示例代码：

#include <cstdint>
#include <stdlib.h>

// Assumes:
// Each xs[i] is [-2, 63]
// length is [1, 8]
uint64_t identity(int xs[], int length)
{
    uint64_t product = 1;
    uint64_t sum = 0;

    for (int i = 0; i < length; ++i)
    {
        int element = xs[i] + 3;
        product *= element;
        sum += element;
    }

    return (uint64_t)length << 59 | (sum << 49) | product;
}

bool equal(int a[], int b[], int size)
{
    return identity(a, size) == identity(b, size);
}

void main()
{
    int a[] = { 23, 0, -2,  6,  3, 23, -1 };
    int b[] = { 0, -1,  6, 23, 23, -2,  3 };

    printf("%d\n", equal(a, b, _countof(a)));
}

- Chris Schmich

---

这样行不通。你可以自己看出来，166=229且1+6+6=2+2+9。因此，你的算法会将列表{-2,3,3,-2,-2,-2,-2,-2}和{-1,-1,6,-2,-2,-2,-2,-2}判定为相等。 - Eugene Smith

@user434507：你说得完全正确，我马上会发布另一种解决方案。 - Chris Schmich

Answer 3

由于只有66个可能的数字，可以创建一个位向量（3个32位字或2个64位字），并进行比较。您只需使用移位和加法即可完成所有操作。由于直到最后才需要比较（以查找它们是否相等），因此可以快速运行，因为不会有太多的分支。

- Gabe

Answer 4

给定两个相等长度的列表。如果这两个列表中所有值的乘积相等，那么这两个列表所包含的值也是相同的，只要这些值都是大于0的整数。

不是的。请考虑以下这些列表：

(9, 9)
(3, 27)

它们的大小相同，元素的乘积也相同。

- Greg

---

如果产品不同，则列表也不同。 - EvilTeach

@EvilTeach - 是的，但如果产品相同，您就不知道列表是否相同。 - Greg

Answer 5

先复制第一个列表。然后循环遍历第二个列表，并在执行时从副本中删除每个项目。如果您通过第二个列表并找到了副本中的所有元素，则这些列表具有相同的元素。这是很多循环，但由于列表中仅有最多8个元素，因此使用不同类型的集合不会获得性能提升。

如果您有更多的项目，则可以为副本使用Dictionary/Hashtable。保留值的唯一键以及它们在第一个列表中被发现的次数。这将为您在较大的列表上提供性能提升。

- Samuel Neff

Answer 6

你需要多快地处理8个整数？在任何现代处理器上排序8件事情几乎不需要时间。

最简单的方法是使用一个大小为66的数组，其中索引0表示值-2。然后你只需要增加这两个数组的计数，然后之后再迭代它们就可以了。

- Anon

---

我担心的不是单个案例，而是因为我需要它来处理10万个以上的列表。 - Justin

Answer 7

如果您的列表只有8个项目，那么排序几乎不会影响性能。如果您想在不排序的情况下完成此操作，可以使用哈希表。

1. 迭代第一个数组，并对数组中的每个值N，Hash(N) = 1。
2. 迭代第二个数组，并对每个值M，Hash(M) = Hash(M) + 1。
3. 迭代哈希表并找到所有键K，使得Hash(K) = 2。

- Sagar V