Wie kann dieser einfache Algorithmus weiter optimiert werden?

Question

Hinweis: Dies ist eine Programmieraufgabe

---

Diese Herausforderung erfordert die Verwendung von std::set.

Eingangs

• Eine Anzahl n
• n Linien mit jeder j und k

Probeneingabe:

5 
1 4 
2 1 
1 6 
3 4 
1 2 

j ist für den Betrieb: 1k, 2 einfügen k löschen (wenn es eine k ist), 3k

Für j == 3, Ausgabe Yes oder No finden, wenn k im std::set ist.

---

Ich habe verschiedene Versionen des Algorithmus gemacht, aber alle sind viel zu langsam. Ich versuchte verschiedene std Funktionen, aber std::find scheint der schnellste, aber immer noch zu langsam. Die Implementierung meiner eigenen wäre noch schlimmer, vielleicht habe ich eine Funktion aus der Bibliothek verpasst. Ich habe wirklich keine Ahnung, wie ich es weiter optimieren kann. Im Moment habe ich dies:

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; 
} 

---

Die Herausforderung erfordert es weniger als 2 Sekunden laufen. Hier sind die Ergebnisse von mir:

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

Wie Sie meinem Algorithmus sehen kann, ist 3x langsamer als die erforderliche Algorithmus. Die Engpässe sind eindeutig jene Funktionen:

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

Aber momentan habe ich keine bessere Idee, als std::find oder ähnliche Funktionen zu verwenden. Hat jemand eine Möglichkeit, meinen Code weiter zu optimieren? Oder gibt es einige offensichtliche Engpässe, die ich vermisse?

Answer 1

Sie möchten set.find() und nicht std::find(set.begin(),set.end()) verwenden.

set.find() verwenden die interne Struktur des Sets, um den Schlüssel in O (log (n)) Zeit zu finden. Dagegen ist std::find eine lineare Suche, die O (n) Zeit benötigt, egal welcher Containertyp verwendet wird.