स्पोइलर चेतावनी: यह प्रोजेक्ट यूलर से Problem 14 से संबंधित है।यह सरल हैकेल एल्गोरिदम इतना धीमा क्यों है?
निम्नलिखित कोड को चलाने के लिए लगभग 15s लगते हैं। मेरे पास एक गैर-रिकर्सिव जावा समाधान है जो 1 एस में चलता है। मुझे लगता है कि मुझे इस कोड को बहुत करीब मिलना चाहिए।
import Data.List
collatz a 1 = a
collatz a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
main = do
print ((foldl1' max) . map (collatz 1) $ [1..1000000])
मैं +RHS -p साथ प्रोफाइल और पाया है कि आबंटित स्मृति बड़ी है, और के रूप में इनपुट बढ़ता बढ़ता है। n = 100,000 1 जीबी आवंटित (!) के लिए n = 1,000,000 13 जीबी (!!) आवंटित किया गया है।
फिर फिर, -sstderr दिखाता है कि हालांकि कई बाइट आवंटित किए गए थे, कुल स्मृति उपयोग 1 एमबी था, और उत्पादकता 95% + थी, इसलिए शायद 13 जीबी लाल हेरिंग है।
मैं कुछ संभावनाओं के बारे में सोच सकते हैं:
कुछ के रूप में सख्त रूप में यह करने की जरूरत नहीं है। मैंने पहले से ही
foldl1'खोजा है, लेकिन शायद मुझे और करने की आवश्यकता है? यह संभव चिह्नित करने के लिएcollatzके रूप में सख्त (यह है कि कोई मतलब है?collatzहै पूंछ-कॉल के अनुकूलन नहीं। मैं यह होना चाहिए लगता है लेकिन पुष्टि करने के लिए एक तरह से पता नहीं है है।संकलक कुछ अनुकूलन नहीं कर रहा है मुझे लगता है कि यह होना चाहिए - उदाहरण के के लिए केवल
collatzके दो परिणाम किसी भी एक समय (अधिकतम और वर्तमान)
कोई सुझाव पर स्मृति में होने की जरूरत है
?यह Why is this Haskell expression so slow? का एक डुप्लिकेट है, हालांकि मुझे लगता है कि तेज़ जावा समाधान को कोई भी ज्ञापन करने की आवश्यकता नहीं है। क्या इसका उपयोग करने के बिना इसे गति देने के कोई तरीके हैं?
Wed Dec 28 09:33 2011 Time and Allocation Profiling Report (Final)
scratch +RTS -p -hc -RTS
total time = 5.12 secs (256 ticks @ 20 ms)
total alloc = 13,229,705,716 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
collatz Main 99.6 99.4
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF Main 208 10 0.0 0.0 100.0 100.0
collatz Main 215 1 0.0 0.0 0.0 0.0
main Main 214 1 0.4 0.6 100.0 100.0
collatz Main 216 0 99.6 99.4 99.6 99.4
CAF GHC.IO.Handle.FD 145 2 0.0 0.0 0.0 0.0
CAF System.Posix.Internals 144 1 0.0 0.0 0.0 0.0
CAF GHC.Conc 128 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.Internals 119 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv 113 5 0.0 0.0 0.0 0.0
और -sstderr:
./scratch +RTS -sstderr
525
21,085,474,908 bytes allocated in the heap
87,799,504 bytes copied during GC
9,420 bytes maximum residency (1 sample(s))
12,824 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 40219 collections, 0 parallel, 0.40s, 0.51s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 35.38s (36.37s elapsed)
GC time 0.40s ( 0.51s elapsed)
RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 35.79s (36.88s elapsed) %GC time 1.1% (1.4% elapsed) Alloc rate 595,897,095 bytes per MUT second
Productivity 98.9% of total user, 95.9% of total elapsed
और जावा समाधान (मेरा नहीं, परियोजना यूलर मंचों से लिया Memoization के साथ हटा दिया):
संदर्भ के लिए, मेरी रूपरेखा उत्पादन होता है
public class Collatz {
public int getChainLength(int n)
{
long num = n;
int count = 1;
while(num > 1)
{
num = (num%2 == 0) ? num >> 1 : 3*num+1;
count++;
}
return count;
}
public static void main(String[] args) {
Collatz obj = new Collatz();
long tic = System.currentTimeMillis();
int max = 0, len = 0, index = 0;
for(int i = 3; i < 1000000; i++)
{
len = obj.getChainLength(i);
if(len > max)
{
max = len;
index = i;
}
}
long toc = System.currentTimeMillis();
System.out.println(toc-tic);
System.out.println("Index: " + index + ", length = " + max);
}
}
यह आश्चर्यजनक है कि जीएचसी किसी भी आत्म-सम्मानित सी कंपाइलर की अपेक्षा करने की अपेक्षा नहीं करेगा (उद्धरण एन 2) (rshift n 1)। क्या कोई कारण है? –
@ सोर्सिज: यह मुझे भी हैरान कर दिया। – ehird