比较两个未排序的 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::vector （大小远低于 50 个元素）
• 两个大的 std::vector

Answer 1

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

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

我的答案中建议的内容适用于大型数组，以提高计算速度，对于小型数组， std::is_permutation 可能就足够了。尽管这个答案中的所有内容也适用于小型数组。

在下面的代码中，实现了三个函数SimilarProd()，，，，第一个使用我的建议，即先计算哈希函数，然后排序。SimilarSort()SimilarIsPermutation()

作为与位置无关的哈希函数，我采用了所有元素的正则乘积（乘法），这些元素被移位（添加）了某个固定的随机 64 位值。由于现代编译器（如 CLang 和 GCC）具有良好的自动向量化功能，使用SIMD指令来提高计算量，因此应用于整数数组的这种计算速度会非常快。

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

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

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

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

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

在线尝试一下！

#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