この単純なアルゴリズムをさらに最適化するには？

Question

注：これはプログラミングチャレンジです

---

この挑戦は std::setの使用を必要とします。各 jと k

サンプル入力と

入力

• 数n
• n行：

  5 
  1 4 
  2 1 
  1 6 
  3 4 
  1 2 
  

  j操作するためのものである：1kがstd::setにある場合、出力Yes又はNoをj == 3ためk

  を見つける3、（kがある場合）kを削除するk、2を挿入します。

  ---

  私はアルゴリズムのバージョンを変えましたが、すべてが遅すぎます。私は別の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）時間を必要とする線形検索です。