如何让这个匹配算法运行得更快呢？

Question

我有两个指向数据结构X的指针列表，算法非常简单：

它循环遍历第一个列表 A 并尝试在列表 B 中查找第一个匹配元素。要求是每个列表中至少有 50k 个元素：

#include <iostream>
#include <memory>
#include <chrono>
#include <vector>
#include <algorithm>
#include <string>

struct X {
    std::string field_1;
    std::string field_2;
    std::string field_3;
    std::string field_4;

    X(std::string f1, std::string f2, std::string f3, std::string f4)
        : field_1(f1)
        , field_2(f2)
        , field_3(f3)
        , field_4(f4)
    {};

    bool equal(const std::shared_ptr<X>& x) {
        return  (x->field_1 == field_1) &&
                (x->field_2 == field_2) &&
                (x->field_3 == field_3) &&
                (x->field_4 == field_4);
    };

    X *match = nullptr;
};
typedef std::shared_ptr<X> X_ptr;


class Timer
{
public:
    Timer(std::string name) : beg_(clock_::now()), name_(name) {}

    ~Timer() {
        std::cout << "Elapsed(" << name_ << "): " << elapsed() << std::endl;
    }

    void reset() { beg_ = clock_::now(); }
    double elapsed() const {
        return std::chrono::duration_cast<second_>
            (clock_::now() - beg_).count();
    }

private:
    typedef std::chrono::high_resolution_clock clock_;
    typedef std::chrono::duration<double, std::ratio<1> > second_;
    std::chrono::time_point<clock_> beg_;

    std::string name_;
};


std::string random_string(size_t length)
{
    auto randchar = []() -> char
    {
        const char charset[] =
            "0123456789"
            "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        const size_t max_index = (sizeof(charset) - 1);
        return charset[rand() % max_index];
    };
    std::string str(length, 0);
    std::generate_n(str.begin(), length, randchar);
    return str;
}

int main()
{
    Timer t("main");

    std::vector <X_ptr> list_A;
    std::vector <X_ptr> list_B;

    const int MAX_ELEM = 50000;

    list_A.reserve(MAX_ELEM);
    list_B.reserve(MAX_ELEM);

    {
        Timer t("insert");

        for (int i = 0; i < MAX_ELEM; i++) {
            list_A.push_back(X_ptr(new X{ random_string(2), random_string(2), random_string(2), random_string(2) }));
            list_B.push_back(X_ptr(new X{ random_string(2), random_string(2), random_string(2), random_string(2) }));
        }
    }

    {
        Timer t("match");

        std::for_each(list_A.begin(), list_A.end(), [list_B](X_ptr& a) {
            auto found_b = std::find_if(list_B.begin(), list_B.end(), [a](const X_ptr& b) {
                return a->equal(b);
            });

            if (found_b != list_B.end()) {
                a->match = found_b->get();

                std::cout << "match OK \n";
            }
        });
    }
}

在我的机器上，程序运行速度非常慢：

Elapsed(insert): 0.05566
Elapsed(match): 98.3739
Elapsed(main): 98.452

如果您能想到任何其他方法来优化它以使其运行得更快，我将不胜感激。

Answer 1

您使用的是向量，因此每次查找 list_B 都需要 O(n)，其中 n 是 B 中的元素数量。这意味着如果 m 是 list_A 中的元素数量，则总算法为 O(m*n)。因此，如果 m 和 na 大小相似，则算法为 O(n^2)。对于任何大的 n 来说这都太慢了。要解决此问题，请将 list_B 转换为 unordered_map（您可以将其作为此算法的一部分，因为转换时间复杂度为 O(n)），其中映射键中的元素是列表 B 中的元素，值可以是任何值，例如 0。然后，您可以在地图上使用 find() 在 O(1) 时间内执行地图查找。因此你的算法变成了 O(n)，比 O(n^2) 更好。

例如

       std::unordered_map< X_ptr, int > value_map;
       Time r t("match");

        std::for_each(list_B.begin(), list_B.end(), [&](X_ptr& b) {
                value_map[b] = 0;
        });

       std::for_each(list_A.begin(), list_A.end(), [value_map](X_ptr& a) {
            auto found_b = value_map.find( a );

            if ( found_b != value_map.end() )
            {
                a->match = found_b->first.get();

                std::cout << "match OK \n";
            }
        });
    }

您的版本：

Elapsed(insert): 0.0758608
Elapsed(match): 182.899
Elapsed(main): 182.991

新版本：

Elapsed(insert): 0.0719907
Elapsed(match): 0.0388562
Elapsed(main): 0.130884