C++有效比较整数序列(按相对顺序)

Question

如果能帮助我在 C++ 中有效地实现比较算法，我将不胜感激。我的程序得到一个由整数序列行组成的输入，我需要找出哪些序列是重复的。但是有些序列可能会移到一边，它应该还是相等的。我的意思是，例如序列 {0, 1, 22, 5, 9} 和 {22, 5, 9, 0, 1} 应该相等。这些序列或重复序列的数量可能有一定的大小。

我似乎想不出任何在某种程度上有效的方法(将每一行与其余所有行进行比较需要太多时间)，所以我希望有人能提供帮助。提前致谢!

Answer 1

我能想到的一个解决方案是计算一个不依赖于旋转的散列。例如:

unsigned long long hash(const std::vector<int>& seq) {
    unsigned long long result;
    for (int i=0,n=seq.size(),j=n-1; i<n; j=i++) {
        result ^= seq[i] * 69069ULL + seq[j];
    }
    return result;
}

然后您可以创建一个 std::map 将哈希码映射到序列中的索引列表，因此只有在哈希相同时才需要进行全面检查。