无序映射的向量，搜索映射太慢

Question

我写了一个小程序，创建了一个包含两百万个带有一些示例数据的映射向量，然后查询一些值。

我知道此时我可以使用数据库，但我只是在玩弄性能优化。

代码：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <string>
#include <chrono>

using namespace std;

static int NUM_OF_MAPS = 2 * 1000 * 1000;
void buildVector(vector<unordered_map <string, int>> &maps);
void find(string key, int value, vector<unordered_map <string, int>> &maps);

int main() {
    auto startPrg = chrono::steady_clock::now();

    vector<unordered_map <string, int>> maps;
    buildVector(maps);

    for (int i = 0; i < 10; i++) {
        string s(1, 'a'+ i);
        find(s, i, maps);
    }

    auto endPrg = chrono::steady_clock::now();
    cout << "program duration: " << chrono::duration_cast<chrono::microseconds>(endPrg - startPrg).count() / 1000.0 << " ms" << endl;
    return 0;
}

void find(string key, int value, vector<unordered_map <string, int>> &maps) {
    auto start = chrono::steady_clock::now();

    int matches = 0;
    for (unordered_map <string, int> &map : maps) {
        unordered_map<string,int>::const_iterator got = map.find(key);

        if (got != map.end() && got->second == value) {
            matches++;
        }
    }

    auto end = chrono::steady_clock::now();
    cout << matches << " matches for " << key << " = " << value << " in " << chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0 << " ms" << endl;
}

void buildVector(vector<unordered_map <string, int>> &maps) {
    auto start = chrono::steady_clock::now();
    maps.reserve(NUM_OF_MAPS);

    int entryCounter = 0;
    unordered_map <string, int> map;
    for (int i = 0; i < NUM_OF_MAPS; i++) {
        map["a"] = entryCounter++;
        map["b"] = entryCounter++;
        map["c"] = entryCounter++;
        map["d"] = entryCounter++;
        map["e"] = entryCounter++;
        map["f"] = entryCounter++;
        maps.push_back(map);
        entryCounter %= 100;
    }

    auto end = chrono::steady_clock::now();
    cout << "build vector: " << chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0 << " ms (" << maps.size() << ")" << endl;
}

输出：

build vector: 697.381 ms (2000000)
40000 matches for a = 0 in 67.873 ms
40000 matches for b = 1 in 64.176 ms
40000 matches for c = 2 in 60.484 ms
40000 matches for d = 3 in 68.102 ms
40000 matches for e = 4 in 62.71 ms
40000 matches for f = 5 in 65.723 ms
0 matches for g = 6 in 64.407 ms
0 matches for h = 7 in 45.401 ms
0 matches for i = 8 in 65.307 ms
0 matches for j = 9 in 64.371 ms
program duration: 1326.42 ms

为了比较速度，我也用Java实现了同样的功能，并获得了以下结果：

build vector: 2536.971578 ms (2000000)
40000 matches for a = 0 in 59.293339 ms
40000 matches for b = 1 in 56.306123 ms
40000 matches for c = 2 in 53.503208 ms
40000 matches for d = 3 in 51.174979 ms
40000 matches for e = 4 in 50.967731 ms
40000 matches for f = 5 in 53.68969 ms
0 matches for g = 6 in 41.927401 ms
0 matches for h = 7 in 36.160645 ms
0 matches for i = 8 in 33.535616 ms
0 matches for j = 9 in 36.56883 ms
program duration: 3016.979919 ms

C++在创建数据方面速度要快得多，但在查询方面非常慢（与Java相比）。是否有办法让C ++在这一部分也能打败Java？

Java代码:

static int NUM_OF_MAPS = 2 * 1000 * 1000;

public static void run() {
    long startPrg = System.nanoTime();

    List<Map<String,Integer>> maps = new ArrayList<>(NUM_OF_MAPS);
    buildVector(maps);

    for (int i = 0; i < 10; i++) {
        String s = String.valueOf((char)('a' + i));
        find(s, i, maps);
    }

    long endPrg = System.nanoTime();
    System.out.println("program duration: " + (endPrg - startPrg) / 1000000.0 + " ms");
}


static void find(String key, Integer value, List<Map<String,Integer>> maps) {
    long start = System.nanoTime();

    int matches = 0;
    for (Map<String,Integer> map : maps) {
        Integer got = map.get(key);

        if (got != null && got.equals(value)) {
            matches++;
        }
    }

    long end = System.nanoTime();
    System.out.println(matches + " matches for " + key + " = " + value + " in " + (end - start) / 1000000.0 + " ms");
}

static void buildVector(List<Map<String,Integer>> maps) {
    long start = System.nanoTime();

    int entryCounter = 0;
    Map<String,Integer> map = new HashMap<>();
    for (int i = 0; i < NUM_OF_MAPS; i++) {
        map.put("a", entryCounter++);
        map.put("b", entryCounter++);
        map.put("c", entryCounter++);
        map.put("d", entryCounter++);
        map.put("e", entryCounter++);
        map.put("f", entryCounter++);
        maps.add(new HashMap<>(map));
        entryCounter %= 100;
    }

    long end = System.nanoTime();
    System.out.println("build vector: " + (end - start) / 1000000.0 + " ms (" + maps.size() + ")");
}

编辑：抱歉，我复制了Java代码两次，而不是C++代码。

- ue7m

---

你启用了优化吗？ - nwp

有很多原因导致不同编程语言的性能差异，但C++特别适合进行多种方式的优化 - 如安全、速度或空间优化。了解您用于基准测试的编译器/标志将非常有用。 - Josh Greifer

g++ -O3 -Wall -c -fmessage-length=0 -MMD -MP -MF"src/Benches.d" -MT"src/Benches.o" -o "src/Benches.o" "../src/Benches.cpp" - ue7m

find 不必要地复制了一个 std::string。不确定这是否会影响性能。 - nwp

@nwp 我怀疑这一点，因为只有10个对find的调用，而且字符串很小。 - Caleth

Answer 1

这段代码的C++版本并不太慢。Java版本在哈希方面进行了更好的优化。

• 在C++中, unordered_map 负责计算哈希值。所以，每个容器在执行 unordered_map<string,int>::const_iterator got = map.find(key) 时会对字符串进行哈希。
• 在Java中，HashMap 依赖对象的 hashCode 方法。问题是，String类只能在初始化和修改字符串时计算哈希值。

就 hash(string) -> int 计算而言，在C++中，您在查找方法中的复杂度为 O(NUM_OF_MAPS)，而在Java中为 O(1)。

- UmNyobe

---

PS: 在每个字符串前添加一个前缀并注意区别。C++中的查找时间会变差，而Java中的时间不会有太大变化。 - UmNyobe

可能会很有趣的是，C++20将添加重载到find()，允许传递预先计算的哈希。因此，在OP的find中的for循环将能够每个字符串计算一次哈希值。 - spectras

@UmNyobe 可能就是这样。我用其他地图实现（如robin_map）进行了一些测试，得到了更好的结果（也比Java的更好）。 - ue7m

Answer 2

补充UmNyobe的回答，你可以通过创建自己的字符串类型来提高性能，该类型缓存计算出的哈希值：

class hashed_string : public std::string
{
public:
  hashed_string( const std::string& str )
  : std::string( str ), hash( std::hash( str ) )
  {
  }

  size_t getHash() { return hash; }

private:
  size_t hash;
};

namespace std
{
    template<> struct hash< hashed_string >
    {
        typedef hashed_string argument_type;
        typedef std::size_t result_type;
        result_type operator()(argument_type const& s) const noexcept
        {
          return s.getHash();
        }
    };
}

你需要扩展 hashed_string 的实现，以防止修改基础字符串或在字符串被修改时重新计算哈希值。通过将字符串作为成员而不是基类来实现可能更容易。

- Alan Birtles

---

这完全是错误的：你允许通过std::string引用操纵hashed_string，但是std::string没有虚方法。不要继承std类型，而是像你在答案的最后一句建议的那样进行包装。 - spectras