c++ - 如何进一步优化这个简单的算法？

Question

注意:这是一个编程挑战

---

此挑战需要使用 std::set。

输入

• 一个数字n
• n 行，每个 j 和 k

示例输入:

5
1 4
2 1
1 6
3 4
1 2

j 用于操作:1插入k，2删除k(如果有k)，3找到k

对于 j == 3，如果 k 在 std 中，则输出 Yes 或 No::设置。

---

我制作了不同版本的算法，但都太慢了。我尝试了不同的 std 函数，但 std::find 似乎是最快的，但仍然太慢。实现我自己的会更糟，所以也许我错过了库中的一个函数。我真的不知道如何进一步优化它。目前我有这个:

int main()
{
    std::set<int> set{};
    int Q = 0;
    std::cin >> Q;

    int type = 0;
    int x = 0;
    for (int i = 0; i < Q; ++i)
    {
        std::cin >> type;
        std::cin >> x;

        if (type == 1)
            set.insert(x);
        else if (type == 2)
            set.erase(x);
        else if (type == 3)
            std::cout << (std::find(std::begin(set), std::end(set), x) != std::end(set) ? "Yes" : "No") << '\n';
            //Condition may be std::find, std::count or std::binary_search
    }

    return 0;
}

---

挑战要求它在 2 秒内运行。以下是我的结果:

Function              Time           % over
std::find          -> 7.410s         370.50%
std::count         -> 7.881s         394.05%
std::binary_search -> 14.050s        702.50%

如您所见，我的算法比要求的算法慢 3 倍。瓶颈显然是那些功能:

Function               % of total time 
std::find          ->  77.61%
std::count         ->  80.80%
std::binary_search ->  87.59%

但目前我没有比使用 std::find 或类似函数更好的主意了。有人有办法/想法进一步优化我的代码吗？还是我遗漏了一些明显的瓶颈？

Answer 1

您想使用 set.find() 而不是 std::find(set.begin(),set.end())。

set.find() 将使用集合的内部结构在 O(log(n)) 时间内定位键。而 std::find 是线性搜索，无论使用何种容器类型，都需要 O(n) 时间。