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).W jaki sposób std :: set wolniej niż std :: map?
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;
}
Czy próbowałeś już czegoś samemu, np. Samemu mierząc czas? a nawet profilowanie? – PlasmaHH
@PlasmaHH: Wierzę, że dałem wystarczający dowód, że jeden jest wolniejszy od drugiego. Interesuje mnie, jak to jest możliwe. –
@PlasmaHH: Uważam, że jest to całkowicie odpowiednie pytanie. –