W jaki sposób std :: set wolniej niż std :: map?

Question

Próbowałem rozwiązać this problem from acm.timus.ru, który zasadniczo chce, żebym wyprowadził liczbę różnych podciągów danego ciągu znaków (maksymalna długość 5000).

Rozwiązania, które przedstawię, są rozpaczliwie nieefektywne i skazane na przekroczenie limitu czasu z uwagi na ograniczenia. Jednak jedynym sposobem, w jaki te dwa rozwiązania różnią się (przynajmniej tak daleko, jak to widzę/rozumiem) jest to, że używa się std::map<long long, bool>, podczas gdy drugi używa std::set <long long> (patrz początek ostatniej pętli for. Reszta jest identyczna, można sprawdzić za pomocą dowolnego narzędzia diff). Rozwiązanie mapy skutkuje "przekroczeniem limitu czasowego w teście 3", podczas gdy ustawione rozwiązanie powoduje "przekroczenie limitu czasu w teście 2", co oznacza, że ​​test 2 jest taki, że rozwiązanie mapy działa szybciej na nim niż ustawione rozwiązanie. Dzieje się tak, jeśli wybiorę kompilator Microsoft Visual Studio 2010. Jeśli wybiorę GCC, oba rozwiązania powodują TLE w teście 3.

Nie pytam, jak skutecznie rozwiązać problem. Pytam: : jak wyjaśnić, że używanie std::map może być bardziej wydajne niż używanie std::set. Po prostu nie widzę mechaniki tego zjawiska i mam nadzieję, że ktoś może mieć jakiekolwiek spostrzeżenia.

Kod1 (wykorzystuje mapy, TLE 3):

#include <iostream> 
#include <map> 
#include <string> 
#include <vector> 

using namespace std; 

int main() 
{ 
    string s; 
    cin >> s; 
    vector <long long> p; 
    p.push_back(1); 
    for (int i = 1; i < s.size(); i++) 
     p.push_back(31 * p[i - 1]); 
    vector <long long> hash_temp; 
    hash_temp.push_back((s[0] - 'a' + 1) * p[0]); 
    for (int i = 1; i < s.size(); i++) 
     hash_temp.push_back((s[i] - 'a' + 1) * p[i] + hash_temp[i - 1]); 
    int n = s.size(); 
    int answer = 0; 
    for (int i = 1; i <= n; i++) 
    { 
     map <long long, bool> hash_ans; 
     for (int j = 0; j < n - i + 1; j++) 
     { 
     if (j == 0) 
      hash_ans[hash_temp[j + i - 1] * p[n - j - 1]] = true; 
     else 
      hash_ans[(hash_temp[j + i - 1] - hash_temp[j - 1]) * p[n - j - 1]] = true; 
     } 
     answer += hash_ans.size(); 
    } 
    cout << answer; 
} 

code2 (wykorzystuje zestaw, TLE 2):

#include <iostream> 
#include <string> 
#include <vector> 
#include <set> 

using namespace std; 

int main() 
{ 
    string s; 
    cin >> s; 
    vector <long long> p; 
    p.push_back(1); 
    for (int i = 1; i < s.size(); i++) 
     p.push_back(31 * p[i - 1]); 
    vector <long long> hash_temp; 
    hash_temp.push_back((s[0] - 'a' + 1) * p[0]); 
    for (int i = 1; i < s.size(); i++) 
     hash_temp.push_back((s[i] - 'a' + 1) * p[i] + hash_temp[i - 1]); 
    int n = s.size(); 
    int answer = 0; 
    for (int i = 1; i <= n; i++) 
    { 
     set <long long> hash_ans; 
     for (int j = 0; j < n - i + 1; j++) 
     { 
     if (j == 0) 
      hash_ans.insert(hash_temp[j + i - 1] * p[n - j - 1]); 
     else 
      hash_ans.insert((hash_temp[j + i - 1] - hash_temp[j - 1]) * p[n - j - 1]); 
     } 
     answer += hash_ans.size(); 
    } 
    cout << answer; 
} 

Answer 1

Rzeczywiste różnice widzę (powiedz mi, jeśli brakowało mi niczego) jest to, że w przypadku map robić

hash_ans[key] = true; 

natomiast w zbiorze przypadku zrobić

hash_ans.insert(key); 

W obu przypadkach, element jest wstawiany, chyba że już istnieje, w którym nic nie robi. W obu przypadkach wyszukiwanie musi zlokalizować odpowiedni element i wstawić go po awarii. W efektywnie każdej implementacji pojemniki będą używać drzewa, co sprawia, że ​​wyszukiwanie jest równie kosztowne. Co więcej, standard C++ faktycznie wymaga set::insert() i map::operator[](), aby uzyskać złożoność O (log n), więc złożoność obu implementacji powinna być taka sama.

Jaki jest powód, dla którego lepiej się spisuje? Jedną z różnic jest to, że w jednym przypadku węzeł drzewa podstawowego zawiera string, podczas gdy w drugim jest to pair<string const, bool>. Ponieważ para zawiera ciąg, musi być większy i wywierać większy nacisk na interfejs RAM komputera, więc nie wyjaśnia to przyspieszenia. To, co można zrobić, to powiększyć rozmiar węzła, tak aby inne węzły zostały odepchnięte z linii pamięci podręcznej, co może być szkodliwe dla wydajności w systemie wielordzeniowym.

Podsumowując, istnieje kilka rzeczy chciałbym spróbować:

1. użyć tych samych danych w zbiorze
   zrobiłbym to z struct data: string {bool b}; czyli pakiet ciąg w struktury, które powinny mieć podobny układ binarny jako elementy mapy. Jako kompilator używaj less<string>, aby tylko ciąg rzeczywiście uczestniczył w porównaniach.

2. stosowanie wkładki() na mapie
   nie sądzę, powinno to być problemem, ale wkładka mogłaby ponieść kopii argumentu, nawet jeśli nie ma wkładki odbywa się w końcu. Mam nadzieję, że tak się nie stanie, więc nie jestem zbyt pewny, że to wszystko zmieni.

3. wyłączyć debugowanie
   Większość wdrożeń ma tryb diagnostyczny, w którym sprawdzane są iteratory. Możesz użyć tego do złapania błędów, w których C++ mówi tylko "niezdefiniowane zachowanie", wzrusza ramionami i załamuje się na tobie. Ten tryb często nie spełnia gwarancji złożoności i zawsze ma pewne koszty ogólne.

4. przeczytaj kod
   Jeśli implementacje dla zestawu i mapy mają różne poziomy jakości i optymalizacji, może to wyjaśnić różnice. Pod maską spodziewałbym się, że zarówno mapa, jak i zestaw będą zbudowane na tym samym typie drzewa, więc nie mam tu zbyt wiele nadziei.

Answer 2

Zestaw to tylko nieco szybciej niż mapa w tym przypadku Zgaduję. Wciąż nie sądzę, że powinieneś tak twierdzić, że TLE 2 lub TLE 3 nie jest tak naprawdę wielką sprawą. Może się zdarzyć, jeśli jesteś clsoe do limitu czasu, który to sam czas rozwiązania ogranicza się do testu 2 na danym zgłoszeniu i następnym razem gdy limit czasowy na test 3. Mam kilka rozwiązań przechodzących testy tylko na czas i zakładam się, jeśli Powtórzę je, ale im się nie uda.

Ten szczególny problem rozwiązałem, używając drzewa Ukonen Sufix.

Answer 3

To zależy od zastosowanych algorytmów implementacji. Zwykle zestawy są realizowane za pomocą map tylko za pomocą pola klucza. W takim przypadku wystąpiłby niewielki narzut związany z używaniem zestawu w przeciwieństwie do mapy.