为什么std::unordered_set operator==() 的复杂度是N^2？

Question

我有两个 v1 和 v2 类型的向量 std::vector<std::string>。两个向量都有唯一的值，如果值比较相等但与向量中值出现的顺序无关，则应该比较相等。

我假设两组类型 std::unordered_set 会是更好的选择，但我照原样接受，所以两个向量。

尽管如此，我认为对于所需的顺序不敏感比较，我将通过复制到两个 std::unordered_set 来使用 std::unordered_set 中的 operator==。很像这样:

bool oi_compare1(std::vector<std::string> const&v1,
                 std::vector<std::string> const&v2)
{
    std::unordered_set<std::string> tmp1(v1.begin(),v1.end());
    std::unordered_set<std::string> tmp2(v2.begin(),v2.end());
    return tmp1 == tmp2;
}

在进行性能分析时，我注意到这个函数耗费了大量时间，所以我检查了文档并在此处看到了 O(n*n) 的复杂性。我很困惑，我期待 O(n*log(n))，例如对于我提出的以下幼稚解决方案：

bool oi_compare2(std::vector<std::string> const&v1,
                 std::vector<std::string> const&v2)
{
    if(v1.size() != v2.size())
        return false;
    auto tmp = v2;
    size_t const size = tmp.size();
    for(size_t i = 0; i < size; ++i)
    {
        bool flag = false;
        for(size_t j = i; j < size; ++j)
            if(v1[i] == tmp[j]){
                flag = true;
                std::swap(tmp[i],tmp[j]);
                break;
            }
        if(!flag)
            return false;
    }
    return true;
}

为什么 std::unordered_set 的 O(n*n) 复杂性，是否有内置函数可用于不区分顺序的比较？

编辑---- 基准

#include <unordered_set>
#include <chrono>
#include <iostream>
#include <vector>

bool oi_compare1(std::vector<std::string> const&v1,
        std::vector<std::string> const&v2)
{
    std::unordered_set<std::string> tmp1(v1.begin(),v1.end());
    std::unordered_set<std::string> tmp2(v2.begin(),v2.end());
    return tmp1 == tmp2;
}
bool oi_compare2(std::vector<std::string> const&v1,
                std::vector<std::string> const&v2)
{
    if(v1.size() != v2.size())
        return false;
    auto tmp = v2;
    size_t const size = tmp.size();
    for(size_t i = 0; i < size; ++i)
    {
        bool flag = false;
        for(size_t j = i; j < size; ++j)
            if(v1[i] == tmp[j]){
                flag = true;
                std::swap(tmp[i],tmp[j]);
                break;
            }
        if(!flag)
            return false;
    }
    return true;
}

int main()
{
    std::vector<std::string> s1{"1","2","3"};
    std::vector<std::string> s2{"1","3","2"};
    std::cout << std::boolalpha;
    for(size_t i = 0; i < 15; ++i)
    {
        auto tmp1 = s1;
        for(auto &iter : tmp1)
            iter = std::to_string(i)+iter;
        s1.insert(s1.end(),tmp1.begin(),tmp1.end());
        s2.insert(s2.end(),tmp1.begin(),tmp1.end());
    }
    std::cout << "size1 " << s1.size() << std::endl;
    std::cout << "size2 " << s2.size() << std::endl;

    for(auto && c : {oi_compare1,oi_compare2})
    {
        auto start = std::chrono::steady_clock::now();
        bool flag = true;
        for(size_t i = 0; i < 10; ++i)
            flag = flag && c(s1,s2);
        std::cout << "ms=" << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count() << " flag=" << flag << std::endl;
    }
    return 0;
}

给予

size1 98304
size2 98304
ms=844 flag=true
ms=31 flag=true

--> 天真的方法更快。

对于所有复杂度为 O(N*N) 的专家... 让我来看看这种天真的方法。我在那里有两个循环。第一个循环是运行从 i=0 到大小 N。内部循环从 j=i 调用!!!!!!到 N。在口语中，这意味着我调用了 N 次内循环。但是由于 j = i !!!! 的起始索引，内循环的复杂度是 log(n)。如果您仍然不相信我从基准计算复杂度，您将看到...

编辑2--- 在 WANDBOX 上直播 https://wandbox.org/permlink/v26oxnR2GVDb9M6y

Answer 1

由于 unordered_set 是使用 hashmap 构建的，比较 lhs==rhs 的逻辑将是：

检查 lhs 和 rhs 的大小，如果不相等，return false
对于lhs中的每一项，在rhs中查找并比较

对于hashmap，在最坏情况下，在rhs 中单次查找一个项目的时间复杂度为O(n)。所以最坏情况下的时间复杂度将是 O(n^2)。但是通常你会得到 O(n) 的时间复杂度。

Answer 2

很遗憾地告诉你，你的 operator== 基准有问题。

oi_compare1 接受 2 个向量，需要构建 2 个完整的 unordered_set 实例，然后调用 operator== 并再次销毁完整的一堆。

oi_compare2 也接受 2 个向量，并立即将它们用于大小比较。仅复制 1 个实例（v2 到 tmp），这对于向量来说性能更高。

运算符==

查看文档：https://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp 我们可以看到预期的复杂性：

Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.

编辑有一个简单的算法，您可以遍历 unordered_set 并在另一个中进行简单查找。如果没有散列冲突，它会在它自己的内部桶中找到每个元素并比较它是否相等，因为散列是不够的。

假设您没有散列冲突，unordered_set 的每个元素都有一个稳定的存储顺序。可以遍历内部桶并比较元素 2×2（第一个元素与第二个元素的第一个元素，第二个元素与第二个元素的第二个......）。这很好地给出了 O(N). 当你有不同大小的桶存储值时，或者当桶的分配使用不同的计算来处理时，这不起作用有碰撞。

假设你运气不好，每个元素都生成相同的散列。（称为 hash flooding）你得到一个没有顺序的元素列表。要进行比较，您必须检查每个元素是否存在于另一个元素中，导致 O(N*N).

如果您将哈希设置为始终 return 相同的数字，那么最后一个很容易重现。以与另一组相反的顺序构建一组。

为什么std::unordered_set operator==() 的复杂度是N^2？

Why is the complexity of std::unordered_set operator==() N^2?

c++

time-complexity

comparison-operators

unordered-set

运算符==