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

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::set中，则输出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%

如您所见，我的算法比所需算法慢三倍。瓶颈显然在于这些函数：

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

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

- Rakete1111

---

那一长串的 if 语句真的需要一个合适的 switch。 - tadman

@tadman 谢谢，我会尝试的。 - Rakete1111

与类相关联的find方法通常针对涉及的容器进行了优化。通用的find方法能够操作可以产生迭代器的任何东西，但速度可能较慢。 - tadman

已经为识别程序中哪个部分过慢而点赞。即使在理解问题后，这种情况下的解决方案是显而易见的，但像这样进行性能分析绝对是正确的方法。 - Peter Cordes

是的！只是这个问题在我的“新问题”中显示，所以我认为它很新...不用担心.... - LoPiTaL

Answer 1

你应该使用 set.find() 而不是 std::find(set.begin(), set.end())。 set.find() 会使用集合的内部结构以 O(log(n)) 的时间定位键值，而 std::find 是一个线性搜索，无论使用什么类型的容器，都需要 O(n) 的时间。

- Vaughn Cato