3

我们使用的第 3 方库本质上是地图/字典。它没有提供任何相等性测试两个对象的方法，我们需要它。

更具体地说，如果满足以下条件，则认为两个映射 S1 和 S2 相等：

  1. S1 中的每个键都是 S2 中的键
  2. S2 中的每个键都是 S1 中的键
  3. 对于 S1 中的每个键 K，S1[K] == S2[K]

请注意，每个映射中的内部排序是不相关的，并且可能不依赖，因此无法直接比较内部结构/成员。我们确实有办法比较键和值是否相等。

执行此操作的最简洁算法是什么？伪 C++ 很好，因为 set 类上的确切 API 与我可以翻译的 std::map 足够接近。

4

4 回答 4

8

比较尺寸

  • 如果大小相等

    • 迭代第一组中的键和每个键：

      • 检查密钥是否存在于第二组中

      • 检查键的元素是否相等

  • 如果至少一个元素不相等，第一个集合中的一个键在第二个集合中不存在或大小不相等，则集合不相等。

于 2013-06-21T11:12:54.680 回答
0

只要正确知道集合中存储的最大值，此方法就有效。取一个大小为 的数组maximum value+1并将其初始化为0。然后遍历第一组和increment'key'位置的数组值对应的value。

现在遍历第二组和decrement数组中索引处的key值value。

最后检查是否所有数组值都是zero. 如果不是，那么它们是unequal，否则它们是equal。

时间复杂度：O(N)

记忆：O(max_value)

于 2013-06-21T11:16:04.513 回答
0

std::map::operator==假设您的地图 API 具有迭代器（或索引）、已排序、不包含重复项，并且还将其键和映射类型存储为嵌套 typedef，您可以及时实现相同的语义O(N)：

#include <functional> // less
#include <algorithm>  // includes

// O(N) complexity
template<class MyMap, class KeyCmp = std::less<typename MyMap::key_type, class TCmp = std::equal<typename MyMap::mapped_type> >
bool set_equality(MyMap const& lhs, MyMap const& rhs, KeyCmp keycmp, TCmp tcmp) 
{
    typedef typename MyMap::value_type Pair;

    return 
        lhs.size() == rhs.size() && 
        std::includes(
            lhs.begin(), lhs.end(), 
            rhs.begin(), rhs.end(), 
            [](Pair const& p1, Pair const& p2){
            return keycmp(p1.first, p2.first) && tcmp(p1.second, p2.second);
        })
    ;
}
于 2013-06-21T11:30:29.293 回答
0

我认为要回答的一个主要问题是在该字典结构中进行一次查找的成本是多少。例如，如果您有一个哈希图的 O(1)，那么像 utnapistim 建议的比较循环的复杂度将是 O(n) * O(1) = O(n)。如果基础字典是 std::map，则您将进行 O(log n) 查找，使其总体为 O(n * log n)。如果您的 dict 是在未排序的数组或列表之上实现的，那么您将进行 O(n) 查找，使其总体上为 O(n^2)。

我提到这些的原因是您还可以对两个字典进行排序并比较结果。对它们进行排序是 O(n * log n)，就像 std::map 一样，所以在不知道查找复杂度的情况下，您无法决定对序列进行排序是更昂贵还是更便宜。

还有一个方面我想提一下，那就是字典的排序。你说你不能在那里假设任何东西，但我知道只有一个常见的结构不能保证相等的内容意味着相等的顺序、未排序的数组或链表。但是，它作为字典的性能很差，因为查找是 O(n)，所以不太可能有人选择它作为底层容器。写这篇文章，我想知道如果哈希图有不同的桶大小和历史，我是否能保证，我真的不确定。我可以肯定的是，最好的算法取决于字典的查找复杂性，所以我会尝试更多地了解这一点。即使是测量也比什么都不知道要好。

于 2013-06-21T16:18:44.273 回答