面试题：C++ find 多条件查找性能优化与高阶应用

Question

给定一个 std::list<std::map<std::string, std::vector<int>>> 这样复杂的数据结构，其中外层 list 表示不同的分组，每个分组内是一个 map，map 的键是字符串，值是一个整数 vector。要求使用 C++ STL 的 find 算法，在这个复杂结构中查找满足以下条件的第一个 map：该 map 至少有一个键值对，且其对应 vector 中的所有元素之和大于100，同时 vector 中存在一个元素是5的倍数。请提供高效的实现代码，并分析实现的时间复杂度，说明优化点在哪里。

Answer 1

#include <iostream>
#include <list>
#include <map>
#include <vector>
#include <algorithm>
#include <numeric>

bool checkMap(const std::map<std::string, std::vector<int>>& m) {
    for (const auto& pair : m) {
        const auto& vec = pair.second;
        int sum = std::accumulate(vec.begin(), vec.end(), 0);
        bool hasMultipleOf5 = std::any_of(vec.begin(), vec.end(), [](int num) { return num % 5 == 0; });
        if (sum > 100 && hasMultipleOf5) {
            return true;
        }
    }
    return false;
}

auto findSatisfyingMap(std::list<std::map<std::string, std::vector<int>>>& data) {
    return std::find_if(data.begin(), data.end(), checkMap);
}

时间复杂度分析

1. 对于 checkMap 函数，假设每个 map 平均有 M 个键值对，每个 vector 的平均大小为 N。
   • 遍历 map 的时间复杂度为 O(M)。
   • 对于每个 vector，std::accumulate 的时间复杂度为 O(N)，std::any_of 的时间复杂度也为 O(N)。
   • 所以 checkMap 函数的时间复杂度为 O(M * N)。
2. 对于 findSatisfyingMap 函数，假设 list 的大小为 L。
   • std::find_if 最坏情况下需要遍历整个 list，每次调用 checkMap。
   • 所以 findSatisfyingMap 的时间复杂度为 O(L * M * N)。

优化点

1. 提前终止：在 checkMap 函数中，一旦找到一个满足条件的键值对就可以立即返回 true，不需要继续检查其他键值对。这样在某些情况下可以减少不必要的计算，平均时间复杂度可能会有所降低。例如：

bool checkMap(const std::map<std::string, std::vector<int>>& m) {
    for (const auto& pair : m) {
        const auto& vec = pair.second;
        int sum = std::accumulate(vec.begin(), vec.end(), 0);
        bool hasMultipleOf5 = std::any_of(vec.begin(), vec.end(), [](int num) { return num % 5 == 0; });
        if (sum > 100 && hasMultipleOf5) {
            return true;
        }
    }
    return false;
}

2. 并行计算：如果硬件支持，可以考虑对 vector 的计算进行并行化。例如，使用 C++ 的并行算法库（如 execution 头文件中的并行策略）来并行计算 std::accumulate 和 std::any_of，这样对于较大的 N 可以显著提高计算速度。不过这会增加代码的复杂性。