मैं this problem from acm.timus.ru को हल करने की कोशिश कर रहा था जो मूल रूप से मुझे एक दिए गए स्ट्रिंग (अधिकतम लंबाई 5000) के विभिन्न सबस्ट्रिंग्स की संख्या आउटपुट करना चाहता है।std :: std :: map से धीमा सेट कैसे है?
समाधान मैं पेश करने के लिए के बारे में हूँ सख्त अक्षम और समय सीमा पार कर की कमी को देखते हुए फैसले के लिए बर्बाद कर रहे हैं। हालांकि, एक ही रास्ता है, जिसमें इन दो समाधान अलग (कम से कम जहाँ तक मैं देख सकता हूँ/समझता हूँ), एक std::map<long long, bool> का उपयोग करता है, अन्य का उपयोग करता है, जबकि std::set <long long> (पाश के लिए पिछले की शुरुआत देखते हैं। बाकी समान है आप किसी भी diff उपकरण द्वारा जांच सकते हैं)। नक्शा समाधान के परिणामस्वरूप "टेस्ट 3 पर समय सीमा समाप्त हो गई", जबकि सेट समाधान का परिणाम "परीक्षण सीमा पर समाप्त समय सीमा" में होता है, जिसका अर्थ है कि टेस्ट 2 ऐसा है कि नक्शा समाधान सेट समाधान की तुलना में तेज़ी से काम करता है। यह मामला है अगर मैं माइक्रोसॉफ्ट विजुअल स्टूडियो 2010 कंपाइलर चुनता हूं। अगर मैं जीसीसी चुनते हैं, तो दोनों समाधान परीक्षण 3.
पर टीएलई में परिणाम मैं कैसे कुशलतापूर्वक समस्या को हल करने के लिए नहीं कह रहा हूँ। मैं क्या पूछ रहा हूं यह है कि कोई कैसे समझा सकता है कि std::map का उपयोग std::set का उपयोग करने से अधिक कुशल हो सकता है। मैं बस इस घटना के यांत्रिकी को देखने में असफल रहा हूं और उम्मीद करता हूं कि किसी के पास कोई अंतर्दृष्टि हो सकती है।
#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 (, सेट का उपयोग करता टीएलई 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;
}
क्या आपने स्वयं को कुछ समय की तरह खुद की कोशिश की है? या यहां तक कि प्रोफाइलिंग भी? – PlasmaHH
@PlasmaHH: मेरा मानना है कि मैंने पर्याप्त सबूत दिया है कि एक दूसरे की तुलना में धीमा है। मुझे दिलचस्पी है कि यह कैसे संभव है –
@PlasmaHH: मेरा मानना है कि यह एक बिल्कुल पर्याप्त सवाल है। –