何时地图比两个向量更好？

Question

一个 map 对其所有元素进行二分查找，这具有对数复杂度——这意味着对于一个足够小的对象集合，map 的性能会比两个进行线性搜索的向量更差。

那么，对象（键）池应该有多大，才能使 map 开始表现得比两个向量更好呢？

编辑：问题的更一般版本是：为了使二分查找的性能优于线性搜索，对象池应该有多大？

我使用字符串作为键，值是指针，但我的特定用例可能并不重要。我更想了解如何正确使用这两个工具。

- Paul Manta

---

为什么您认为您需要在向量上执行线性搜索？如果它们已经排序，只需调用binary_search或lower_bound即可获得O(log N)的搜索。 - Matthieu M.

如果这对你很重要，有足够的变量需要你自己计时。另外请注意，您可以在排序向量上执行二进制搜索。 - Mark Ransom

复杂度只描述渐近行为。任何给定的实现都会有不同的具体运行时间，因为复杂度保证对各种常数的数量级没有说明。因此，没有比在目标环境上搭建一个简单的测试框架并对其进行分析更好的解决方案了。 - Kerrek SB

@Paul：我会说这取决于你要衡量什么。比较函数的成本与将元素加载到CPU缓存中的成本有何不同（这取决于元素的大小和您特定的架构）。测量通常取决于硬件，所以很难预见 :x - Matthieu M.

问题实际上不应该是关于搜索，因为搜索已排序的向量（就像地图一样）非常快。问题实际上应该是关于维护排序向量的成本。 - Martin York

Answer 1

如果您允许我这么说，大多数答案听起来像是在各种方式地说“我不知道”，而没有真正承认他们不知道。虽然我基本上同意他们给出的建议，但他们似乎都没有直接回答你提出的问题：什么是盈亏平衡点。

公平地说，当我读到这个问题时，我也不太清楚。对于一个足够小的集合，线性搜索可能会更快；对于一个足够大的集合，二分搜索肯定会更快。然而，我从来没有真正去调查过盈亏平衡点的任何信息。然而，您的问题让我感到好奇，所以我决定写一些代码，以至少得到一些想法。

这段代码绝对是一个非常快速的hack（有很多重复，目前只支持一种类型的键等），但至少它可以给出一些期望值：

#include <set>
#include <vector>
#include <string>
#include <time.h>
#include <iostream>
#include <algorithm>

int main() {   

    static const int reps = 100000;

    std::vector<int> data_vector;
    std::set<int> data_set;
    std::vector<int> search_keys;

    for (int size=10; size<100; size += 10) {
        data_vector.clear();
        data_set.clear();
        search_keys.clear();

        int num_keys = size / 10;   
        for (int i=0; i<size; i++) {
            int key = rand();

            if (i % num_keys == 0)
                search_keys.push_back(key);

            data_set.insert(key);
            data_vector.push_back(key);
        }

        // Search for a few keys that probably aren't present.
        for (int i=0; i<10; i++)
            search_keys.push_back(rand());

        long total_linear =0, total_binary = 0;

        clock_t start_linear = clock();
        for (int k=0; k<reps; k++) {
            for (int j=0; j<search_keys.size(); j++) {
                std::vector<int>::iterator pos = std::find(data_vector.begin(), data_vector.end(), search_keys[j]);
                if (pos != data_vector.end())
                    total_linear += *pos;
            }
        }
        clock_t stop_linear = clock();                      

        clock_t start_binary = clock();
        for (int k=0; k<reps; k++) {
            for (int j=0; j<search_keys.size(); j++) {
                std::set<int>::iterator pos = data_set.find(search_keys[j]);
                if (pos != data_set.end())
                    total_binary += *pos;
            }
        }
        clock_t stop_binary = clock();

        std::cout << "\nignore: " << total_linear << " ignore also: " << total_binary << "\n";

        std::cout << "For size = " << size << "\n";
        std::cout << "\tLinear search time = " << stop_linear - start_linear << "\n";
        std::cout << "\tBinary search time = " << stop_binary - start_binary << "\n";
    }
    return 0;
}

这是在我的机器上运行时得到的结果：

ignore: 669830816 ignore also: 669830816
For size = 10
        Linear search time = 37
        Binary search time = 45

ignore: 966398112 ignore also: 966398112
For size = 20
        Linear search time = 60
        Binary search time = 47

ignore: 389263520 ignore also: 389263520
For size = 30
        Linear search time = 83
        Binary search time = 63

ignore: -1561901888 ignore also: -1561901888
For size = 40
        Linear search time = 106
        Binary search time = 65

ignore: -1741869184 ignore also: -1741869184
For size = 50
        Linear search time = 127
        Binary search time = 69

ignore: 1130798112 ignore also: 1130798112
For size = 60
        Linear search time = 155
        Binary search time = 75

ignore: -1949669184 ignore also: -1949669184
For size = 70
        Linear search time = 173
        Binary search time = 83

ignore: -1991069184 ignore also: -1991069184
For size = 80
        Linear search time = 195
        Binary search time = 90

ignore: 1750998112 ignore also: 1750998112
For size = 90
        Linear search time = 217
        Binary search time = 79

显然这并不是唯一可能的测试（甚至远非最佳测试），但对我来说，即使有一点硬数据也比没有好。

编辑：值得注意的是，我认为使用两个向量（或者一个成对的向量）的代码与使用set或map的代码一样简洁。显然，你需要把它的代码放到自己的一个小类中，但我完全没有理由认为它不能像 map 一样向外界呈现 完全相同 的接口。事实上，我可能会直接称之为“tiny_map”（或者类似的名称）。

面向对象编程（在泛型编程中仍然存在一定程度上）的基本观点之一是将接口与实现分离。在这种情况下，你谈论的只是纯粹的实现细节，根本不需要影响接口。事实上，如果我正在编写一个标准库，我会考虑将其作为“小型映射优化”纳入其中——类似于常见的小字符串优化。基本上，只需在映射对象本身中分配10个（或更多）value_type 对象的数组，并在映射较小时使用它们，当映射增长到足以证明需要时，则将数据移动到树中。唯一真正的问题是人们是否经常使用 tiny maps，以此来证明这项工作是值得的。

- Jerry Coffin

---

我把采纳答案改成了你的。我发现很惊讶的是，在80到90个对象中，二分查找实际上减少了执行时间。那里发生了什么？0_o - Paul Manta

@Paul：有点难猜测。由于只有10毫秒，很可能是更或少的偶然事件（基本上是一个时间片）。也有可能我得到的确切数字序列最终产生了稍微更好平衡的树（R-B和AVL树可以防止树过度失衡，但一个树仍然可以比另一个树略微更好）。也有可能它恰好把我搜索的关键字放得更靠近根节点。 - Jerry Coffin

你误解了 - 我并不是说“我不知道”，而是说我无法知道。这是很大的区别。这完全取决于你的编译器、编译器库、机器以及你正在使用的类型等因素。对于建议隐藏实现，我给予+1。另外，为了计时，我在Windows中使用QueryPerformanceCounter，因为它没有粒度问题。 - Mark Ransom

我的意思是，尽管你无法知道每种可能情况的精确数据，但只需要得到足够的硬数据，就能做出相对明智的决策。 - Jerry Coffin

Answer 2

< p > map 的代码将比两个 vector 的代码更加简洁，这应该是您的首要关注点。只有确定在您自己的应用程序中，map 的性能是一个问题时，才应该担心它们之间的区别，并且此时您应该自行进行基准测试。 < /p >

- Mark Ransom

---

如果 map 的性能存在问题，我的第一步将是将其替换为 unordered_map，或者使用 boost pool allocator 替换其分配器。这两种方法都可以极大地提高性能，并且仍然比两个向量简单得多。 - Mooing Duck

Answer 3

地图永远无法与排序后的向量搜索速度相匹敌，因为向量内存更好地压缩，并且内存访问更加直接。

然而，这只是其中一半的故事。一旦您开始修改容器，基于节点的容器（不需要移动其元素以适应中间插入）就会获得理论上的优势。与搜索类似，更好的高速缓存局部性仍然为小数量的元素提供了矢量的优势。

确切的测量很难提供，并且取决于特定的优化、上下文使用和机器，因此我建议只按功能进行操作。地图具有通过键搜索的自然接口，因此使用它将使您的生活更轻松。

如果你真的发现自己在测量并且需要从用例中真正挤出性能，那么你可能需要更专业的数据结构。查找B树。

- Matthieu M.