c++ - std::map::find 的效率与值的数据大小有关吗？

Question

我用了 std::map<std::pair<int, int>, class B>保存一张栅格 map 的信息，B类包含大约10000 Bytes的数据。我发现40000次大概需要10ms find操作，虽然 map 只有四个键值。当我将 B 类的数据大小减少到 2500 字节时，成本也减少到大约 3.5 毫秒。我知道find操作的时间复杂度是O(log(N))，这是什么原因造成的？

Answer 1

我很好奇，尝试了一个简单的测试。测试代码如下(使用VS2015编译)。

这是我在发布版本中运行代码时得到的(优化):

Value10k: 0.126498 ms
Value2k: 0.121991 ms

这是调试版本的输出:

Value10k: 120.187 ms
Value2k: 95.5364 ms

在发布版本中差异可以忽略不计；在调试版本中似乎存在一些差异(尽管对于性能数据，我倾向于更喜欢发布版本)。

我不知道 map::find 的实现细节方法。无论如何，请注意大 O 符号只是故事的一部分。另一个需要考虑性能的重要方面是数据的缓存友好性、数据局部性等。

我什至不知道你的 B 类是否正在进行一些昂贵的复制操作。

无论如何，我建议衡量您的代码性能，并与其他变体进行比较，例如使用 unique_ptr<B>或 shared_ptr<B>为了您的 map 的值(value)。

---

可编译的测试代码如下:

#include <iostream>
#include <map>
#include <windows.h>
using namespace std;

template <int DimT>
struct Value
{
    char Data[DimT];
};

typedef Value<10000> Value10k;
typedef Value<2000> Value2k;


long long Counter() 
{
    LARGE_INTEGER li;
    QueryPerformanceCounter(&li);
    return li.QuadPart;
}

long long Frequency() 
{
    LARGE_INTEGER li;
    QueryPerformanceFrequency(&li);
    return li.QuadPart;
}

void PrintTime(const long long start, const long long finish, const char * const msg)
{
    cout << msg << ": " << (finish - start) * 1000.0 / Frequency() << " ms\n";
}

bool IsEven(int n)
{
    return (n % 2) == 0;
}

int main() 
{
    map<pair<int, int>, Value10k> m1;
    m1[make_pair(0, 0)] = Value10k{};
    m1[make_pair(0, 1)] = Value10k{};
    m1[make_pair(1, 0)] = Value10k{};
    m1[make_pair(1, 1)] = Value10k{};

    constexpr int searchCount = 40000;

    auto start = Counter();
    for (int i = 0; i < searchCount; i++)
    {
        int x{};
        int y{};
        if (IsEven(i))
        {
            x = 0;
            y = 1;
        }
        else
        {
            x = 1;
            y = 0;
        }
        auto search = m1.find(make_pair(x, y));
    }
    auto finish = Counter();
    PrintTime(start, finish, "Value10k");


    map<pair<int, int>, Value2k> m2;
    m2[make_pair(0, 0)] = Value2k{};
    m2[make_pair(0, 1)] = Value2k{};
    m2[make_pair(1, 0)] = Value2k{};
    m2[make_pair(1, 1)] = Value2k{};

    start = Counter();
    for (int i = 0; i < searchCount; i++)
    {
        int x{};
        int y{};
        if (IsEven(i))
        {
            x = 0;
            y = 1;
        }
        else
        {
            x = 1;
            y = 0;
        }
        auto search = m2.find(make_pair(x, y));
    }
    finish = Counter();
    PrintTime(start, finish, "Value2k");
}