比较两个未排序的 std::vector

Question

比较两个未排序的最佳方法是什么std::vector

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {2, 3, 4, 5, 1};

我目前正在做的是

const auto is_similar = v1.size() == v2.size() && std::is_permutation(v1.begin(), v1.end(), v2.begin());

只有当两个向量的大小相等并且包含相同的元素时，这两个向量才相似

什么是更好的方法

两个小 std::vectors（大小小于 50 个元素）
两大std::vectors

Answer 1

What would be a better approach

删除 v1.size() == v2.size() && 表达式并将结束迭代器传递给 std::is_permutation.

你标记了C++11，但对于那些可以使用C++20的人，我建议如下：

std::ranges::is_permutation(v1, v2)

如果你可以修改向量，那么对它们进行排序和比较相等性会渐近地更快。如果您不能修改，那么如果您能负担得起存储成本，则可以创建一个排序的副本。

Answer 2

std::is_permutation 对于大数组来说似乎非常非常慢。对于类似数组的 64 K 个元素，它需要大约 5 秒才能给出答案。对于这种大小的数组，常规排序需要 0.007 秒。下面我的代码中提供了时间安排。

我建议做以下事情 - 计算与元素顺序无关的元素的任何简单（快速）哈希函数。如果两个数组的散列不相等则它们不相似，换句话说两个数组作为集合不相等。仅当哈希值相同时才进行常规排序并比较数组是否相等。

我的回答中建议的内容适用于大型数组，以加快计算速度，对于微型数组可能 std::is_permutation 就足够了。尽管此答案中的所有内容也适用于小型阵列。

在下面的代码中实现了三个函数SimilarProd()、SimilarSort()、SimilarIsPermutation()，其中第一个使用了我关于先计算散列函数然后排序的建议。

作为与位置无关的哈希函数，我将所有元素的常规乘积（乘法）移位（添加到）某个固定的随机 64 位值。由于良好的 auto-vectorization capabilities of modern compilers (like CLang and GCC) which use SIMD 指令可以促进计算，这种应用于整数数组的计算将非常快地计算出来。

在下面的代码中，我对相似函数的所有三个实现进行了计时。看起来，如果数组 64 K 的大小相似（同一组数字），std::is_permutation() 需要 5 秒，而散列方法和排序方法都需要 0.007 】秒。对于不相似的数组 std::is_permutation 非常快，低于 0.00005 秒，而排序也是 0.007 秒，散列快 100x 倍，0.00008 秒。

所以结论是 std::is_permutation 对于大型相似数组非常慢，对于不相似数组非常快。排序方法对于相似和不相似的速度相同。虽然哈希方法对于相似的速度很快，而对于不相似的速度非常快。对于不相似的数组，哈希方法的速度与 std::is_permutation 大致相同，但对于相似的数组来说，这是一个明显的胜利。

因此，在三种方法中，哈希方法明显胜出。

请参阅下面代码后的时序。

更新。为了对比刚刚又增加了一种方法SimilarMap()。使用 std::unordered_map 计算数组中每个整数的出现次数。它似乎比排序慢一点。所以还是Hash+Sort的方式是最快的。尽管对于非常大的数组，这种映射计数方法应该优于排序速度。

Try it online!

#include <cstdint>
#include <array>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <unordered_map>

bool SimilarProd(std::vector<int> const & a, std::vector<int> const & b) {
    using std::size_t;
    using u64 = uint64_t;
    if (a.size() != b.size())
        return false;
    u64 constexpr randv = 0x6A7BE8CD0708EC4CULL;
    size_t constexpr num_words = 8;
    std::array<u64, num_words> prodA = {}, prodB = {};
    std::fill(prodA.begin(), prodA.end(), 1);
    std::fill(prodB.begin(), prodB.end(), 1);
    for (size_t i = 0; i < a.size() - a.size() % num_words; i += num_words)
        for (size_t j = 0; j < num_words; ++j) {
            prodA[j] *= (randv + u64(a[i + j])) | 1;
            prodB[j] *= (randv + u64(b[i + j])) | 1;
        }
    for (size_t i = a.size() - a.size() % num_words; i < a.size(); ++i) {
        prodA[0] *= (randv + u64(a[i])) | 1;
        prodB[0] *= (randv + u64(b[i])) | 1;
    }
    for (size_t i = 1; i < num_words; ++i) {
        prodA[0] *= prodA[i];
        prodB[0] *= prodB[i];
    }
    if (prodA[0] != prodB[0])
        return false;
    auto a2 = a, b2 = b;
    std::sort(a2.begin(), a2.end());
    std::sort(b2.begin(), b2.end());
    return a2 == b2;
}

bool SimilarSort(std::vector<int> a, std::vector<int> b) {
    if (a.size() != b.size())
        return false;
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    return a == b;
}

bool SimilarIsPermutation(std::vector<int> const & a, std::vector<int> const & b) {
    return a.size() == b.size() && std::is_permutation(a.begin(), a.end(), b.begin());
}

bool SimilarMap(std::vector<int> const & a, std::vector<int> const & b) {
    if (a.size() != b.size())
        return false;
    std::unordered_map<int, int> m;
    for (auto x: a)
        ++m[x];
    for (auto x: b)
        --m[x];
    for (auto const & p: m)
        if (p.second != 0)
            return false;
    return true;
}

void Test() {
    using std::size_t;
    auto TimeCur = []{ return std::chrono::high_resolution_clock::now(); };
    auto const gtb = TimeCur();
    auto Time = [&]{ return std::chrono::duration_cast<
        std::chrono::microseconds>(TimeCur() - gtb).count() / 1000000.0; };
    std::mt19937_64 rng{123};
    auto RandV = [&](size_t n) {
        std::vector<int> v(n);
        for (size_t i = 0; i < v.size(); ++i)
            v[i] = rng() % (1 << 30);
        return v;
    };
    size_t constexpr n = 1 << 16;
    auto a = RandV(n), b = a, c = RandV(n);
    std::shuffle(b.begin(), b.end(), rng);

    std::cout << std::boolalpha << std::fixed;
    double tb = 0;

    tb = Time();    std::cout << "Prod "
        << SimilarProd(a, b) << " time " << (Time() - tb) << std::endl;
    tb = Time();    std::cout << "Sort "
        << SimilarSort(a, b) << " time " << (Time() - tb) << std::endl;
    tb = Time();    std::cout << "IsPermutation "
        << SimilarIsPermutation(a, b) << " time " << (Time() - tb) << std::endl;
    tb = Time();    std::cout << "Map "
        << SimilarMap(a, b) << " time " << (Time() - tb) << std::endl;


    tb = Time();    std::cout << "Prod "
        << SimilarProd(a, c) << " time " << (Time() - tb) << std::endl;
    tb = Time();    std::cout << "Sort "
        << SimilarSort(a, c) << " time " << (Time() - tb) << std::endl;
    tb = Time();    std::cout << "IsPermutation "
        << SimilarIsPermutation(a, c) << " time " << (Time() - tb) << std::endl;
    tb = Time();    std::cout << "Map "
        << SimilarMap(a, c) << " time " << (Time() - tb) << std::endl;
}

int main() {
    Test();
}

输出：


Prod true time 0.009208
Sort true time 0.008080
IsPermutation true time 4.436632
Map true time 0.010382

Prod false time 0.000082
Sort false time 0.008750
IsPermutation false time 0.000036
Map false time 0.016390

比较两个未排序的 std::vector

Compare two unsorted std::vector

c++

vector

c++11