पृष्ठभूमि: मैंने पहली बार कई वर्षों पहले स्कूल में सी ++ और जावा सीखा था, लेकिन पिछले 9 या उससे अधिक वर्षों में मैंने अधिक प्रोग्रामिंग नहीं की है क्योंकि मेरे पिछले करियर की आवश्यकता नहीं थी।प्रोजेक्ट यूलर # 14: ब्रूट फोर्स की तुलना में मेरा ट्रीमैप एल्गोरिदम धीमा क्यों है?
मैंने अपने प्रोग्रामिंग पर ब्रश करने के लिए प्रोजेक्ट यूलर को देखने का फैसला किया और समस्या हल की 14, जो लंबे समय तक कोलात्ज़ अनुक्रम के साथ एक और एक मिलियन के बीच पूर्णांक खोजने के लिए कहता है। (कोलात्ज़ अनुक्रम, प्रारंभिक संख्या के साथ आगे बढ़ता है, 3 से संख्या को गुणा करता है और यदि यह अजीब है, या यदि यह भी है तो संख्या को जोड़ना। प्रक्रिया तब तक जारी रहती है जब तक कि संख्या तक पहुंच न हो।)
मैंने पहले हल किया ब्रूट फोर्स का उपयोग कर समस्या, जैसा कि नीचे दिए गए कोड में दिखाया गया है।
int n;
long temp; // long is necessary since some Collatz sequences go outside scope of int
int[] n_length = new int[1000000];
for(n = 0; n < 1000000; n++){
temp = n + 1;
n_length[n] = 1;
while (temp > 1){
n_length[n]++;
if (temp % 2 == 0) temp = temp/2;
else temp = 3*temp + 1;
}
}
int max = 0;
int max_index = 0;
for (int i = 0; i < 1000000; i++){
if (n_length[i] > max){
max = n_length[i];
max_index = i;
}
}
System.out.println("The number with the longest Collatz sequence is " + (max_index + 1));
मैंने सोचा कि यह दृष्टिकोण अक्षम होगा, क्योंकि यह आवश्यक से अधिक बार एल्गोरिदम चलाता है। किसी भी संख्या जो पिछले नंबर के कोलात्ज़ अनुक्रम का हिस्सा है, प्रभावी रूप से इसके अनुक्रम को पहले ही निर्धारित कर लेगा, और इसलिए आप प्रत्येक एकल संख्या के अनुक्रम की गणना को प्रत्येक बार एक कोलेट्स अनुक्रम में प्राप्त करते हैं।
मैंने तय किया कि जैसे ही यह कोलात्ज़ अनुक्रम में आता है, प्रत्येक मानचित्र को मानचित्र में स्टोर करना बेहतर होगा, इसलिए आपको केवल इसकी गणना करना होगा। ऐसा करने के लिए, मैंने एक वृक्ष मैप का उपयोग किया, जिसमें कुंजियों और सहयोगी कोलात्ज़ अनुक्रम लंबाई के रूप में उपयोग की जाने वाली संख्याओं के साथ, और प्रत्येक संख्या को कोलात्ज़ अनुक्रम में आने पर मानचित्र में प्रत्येक नंबर डालने के लिए एक पुनरावर्ती फ़ंक्शन का उपयोग किया जाता था। इतनी के रूप में मैं पाश के लिए के माध्यम से पुनरावृति मैं जल्दी से देख सकते हैं कि कुंजियां पहले से ही डाला गया है और फोन करने से बचने के बाद से यह स्वचालित रूप से प्रवेश पर कुंजी सॉर्ट करता (कोड नीचे देखें।)
public static TreeMap<Long, Integer> tm = new TreeMap<Long, Integer>();
public static void main(String[] args) {
tm.put((long)1, 1);
int maxVal = 1;
long keyWithMaxVal = 1;
int maybeMax;
for (long i = 2; i <= 1000000; i++){
if(!(tm.containsKey(i))){
maybeMax = addKey(i);
if (maybeMax >= maxVal){
maxVal = maybeMax;
keyWithMaxVal = i;
}
}
}
System.out.println("The number with the longest Collatz sequence is " + keyWithMaxVal + " with length " + maxVal);
}
public static int addKey(long key){
while (!(tm.containsKey(key))){
if (key % 2 == 0){
tm.put(key, 1 +addKey(key/2));
}
else{
tm.put(key, 1 + addKey(3*key + 1));
}
}
return tm.get(key);
}
मैं एक ट्री-मैप का इस्तेमाल किया, जब तक मुझे नहीं करना है तब तक कुंजी जोड़ने के लिए addKey विधि। मैंने सोचा कि यह एल्गोरिदम बहुत तेज होगा।
हालांकि, जब मैं वास्तव में कोड चलाता था, तो मुझे आश्चर्य हुआ कि ब्रूट फोर्स एल्गोरिदम तत्काल उत्तर के साथ आया था, जबकि रिकर्सिव ट्रीएप एल्गोरिदम ने लगभग 6 सेकंड तक अधिक समय लगाया था। जब मैंने अपने कार्यक्रमों को एक मिलियन की बजाय 5 मिलियन तक जाने के लिए संशोधित किया, तो अंतर और भी स्पष्ट हो गया। मैंने यह सुनिश्चित करने के लिए प्रत्येक प्रोग्राम में कुछ कोड जोड़ा है कि दूसरा प्रोग्राम पहले से कम काम कर रहा था, और वास्तव में मैंने यह निर्धारित किया कि प्रत्येक कुंजी के लिए केवल ऐडकी विधि को बुलाया जा रहा था, जबकि समय लूप को फिर से करने की आवश्यकता थी पहले कार्यक्रम में सभी संख्याओं की लंबाई के योग के बराबर था Collatz अनुक्रम (यानी दूसरी एल्गोरिदम में विधि कॉल की संख्या से अधिक अक्सर)।
तो पहला एल्गोरिदम दूसरे की तुलना में इतना तेज़ क्यों है? क्या ऐसा इसलिए है क्योंकि पहले एल्गोरिदम में प्राइमेटिव की सरणी को दूसरे में रैपर ऑब्जेक्ट्स के ट्रीमैप की तुलना में कम संसाधनों की आवश्यकता होती है? क्या नक्शा खोज रहा है यह जांचने के लिए कि क्या एक कुंजी पहले से ही धीमी है (अनुमानित लॉग नहीं होना चाहिए?)? क्या रिकर्सिव विधियां हैं जिनकी बड़ी संख्या में विधि कॉल धीमी गति से धीमी होती है? या क्या कुछ और है जो मैं देख रहा हूं
स्रोत:
* क्या रिकर्सिव विधियां हैं जिनकी बड़ी संख्या में विधि कॉल धीमी गति से धीमी होती है? * आम तौर पर: हाँ। रिकर्सन अक्सर लिखना और समझना आसान होता है, लेकिन उन्हें लूप में बदलने से प्रदर्शन में काफी वृद्धि हो सकती है। लेकिन मुझे नहीं लगता कि यह निष्पादन समय में वृद्धि के लिए पूर्ण कारण है। – Turing85
हालांकि यह समस्या गतिशील प्रोग्रामिंग (आपका दूसरा समाधान) का उपयोग करके सबसे अच्छी तरह हल हो जाती है, ऐसा लगता है कि आपका रिकर्सिव समाधान ठीक वही नहीं कर रहा है जो आप चाहते हैं। हैश मानचित्र के बजाय पेड़ मानचित्र का उपयोग क्यों करें? आप लॉग समय के बजाय अपने मानचित्र में निरंतर समय लुकअप प्राप्त कर सकते हैं। –
हम्म ... हैश मैप पर स्विच करने से थोड़ा सुधार हुआ, लेकिन यह अभी भी पहले कार्यक्रम की तुलना में काफी धीमा है। (मैं अभ्यास से थोड़ी दूर हूं, जैसा कि मैंने अपने प्रश्न के शीर्ष पर समझाया है, इसलिए मुझे कुछ विवरण याद नहीं हो सकते हैं जैसे हैश मैप निरंतर लुकअप समय है।) – nobody