In che modo std :: set è più lento di std :: map?

Question

Stavo cercando di risolvere this problem from acm.timus.ru che fondamentalmente vuole che io produca il numero di sottostringhe diverse di una determinata stringa (lunghezza massima 5000).

Le soluzioni che sto per presentare sono disperatamente inefficienti e condannate per il tempo limite superato il verdetto dati i vincoli. Tuttavia, l'unico modo in cui queste due soluzioni differiscono (almeno per quanto posso vedere/comprendere) è che si utilizza std::map<long long, bool>, mentre l'altro utilizza std::set <long long> (vedere l'inizio dell'ultimo ciclo per. può controllare con qualsiasi strumento diff). La soluzione della mappa risulta in "Limite temporale superato nel test 3", mentre la soluzione impostata risulta in "Limite temporale superato nel test 2", il che significa che il test 2 è tale che la soluzione mappa funziona più rapidamente rispetto alla soluzione impostata. Questo è il caso se scelgo il compilatore Microsoft Visual Studio 2010. Se scelgo GCC, entrambe le soluzioni risultano in TLE nel test 3.

Non sto chiedendo come risolvere il problema in modo efficiente. Quello che sto chiedendo è come si può spiegare che l'utilizzo di std::map può apparentemente essere più efficiente rispetto all'utilizzo di std::set. Non riesco a vedere i meccanismi di questo fenomeno e spero che qualcuno possa avere qualche intuizione.

Code1 (usa carta, 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 (usa insieme, 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

Le differenze effettive che vedo (dimmi se ho perso qualcosa) sono che nel caso mappa si fa

hash_ans[key] = true; 

mentre nel caso insieme si fa

hash_ans.insert(key); 

In entrambi i casi, un elemento è inserito, a meno che non esista già, in cui non fa nulla. In entrambi i casi, la ricerca deve individuare l'elemento corrispondente e inserirlo in caso di errore. In effetti ogni implementazione là fuori, i contenitori useranno un albero, rendendo la ricerca altrettanto costosa. Ancor più, lo standard C++ richiede effettivamente set::insert() e map::operator[]() di essere O (log n) in complessità, quindi la complessità di entrambe le implementazioni dovrebbe essere la stessa.

Ora, quale potrebbe essere la ragione per cui uno si comporta meglio? Una differenza è che in un caso un nodo dell'albero sottostante contiene uno string, mentre nell'altro è un pair<string const, bool>. Dato che la coppia contiene una stringa, deve essere più grande e mettere più pressione sull'interfaccia RAM della macchina, quindi questo non spiega la velocità. Quello che potrebbe fare è ingrandire la dimensione del nodo in modo che altri nodi vengano spinti fuori dalla linea della cache, il che può essere negativo per le prestazioni nel sistema multi-core.

In sintesi, ci sono alcune cose che mi piacerebbe provare:

1. utilizzare gli stessi dati nel set
   farei questo con struct data: string {bool b}; cioè il paniere la stringa in una struttura che dovrebbe avere un simile layout binario come elementi della mappa. Come comparatore, utilizzare less<string>, in modo che solo la stringa partecipi effettivamente ai confronti.

2. usa inserto() sulla mappa
   io non credo che questo dovrebbe essere un problema, ma l'inserto potrebbe incorrere in una copia della tesi, anche se nessun inserto avviene alla fine. Spero che non sia così, quindi non sono troppo sicuro che questo cambierà qualcosa.

3. disattiva debug
   La maggior parte delle implementazioni dispone di una modalità diagnostica, in cui gli iteratori sono convalidati. Puoi usarlo per rilevare errori in cui C++ dice solo "comportamento non definito", alza le spalle e si blocca su di te. Questa modalità spesso non soddisfa le garanzie di complessità e ha sempre un sovraccarico.

4. leggere il codice
   Se le implementazioni per set e mappa hanno diversi livelli di qualità e ottimizzazione, ciò potrebbe spiegare le differenze. Sotto il cofano, mi aspetterei che entrambe le mappe siano costruite sullo stesso tipo di albero, quindi non c'è molta speranza neanche qui.

Answer 2

Un set è solo un po 'più veloce di una mappa in questo caso Suppongo. Ancora non penso che dovresti fare un caso tanto quanto TLE 2 o TLE 3 non è davvero un grosso problema. Può accadere se si è soddisfatti del limite di tempo che la stessa soluzione limita i tempi del test 2 su un dato invio e la prossima volta del limite di tempo sul test 3. Ho alcune soluzioni che superano i test solo al limite di tempo e scommetto se Io li ripresento loro falliranno.

Questo particolare problema ho risolto utilizzando un albero Ukonen Sufix.

Answer 3

Dipende dagli algoritmi di implementazione utilizzati. Di solito gli insiemi sono implementati usando le mappe solo usando il campo chiave. In tal caso ci sarebbe un leggero overhead per l'utilizzo di un set rispetto a una mappa.