Cảnh báo cảnh báo: liên quan đến Problem 14 từ Project Euler.Tại sao thuật toán haskell đơn giản này lại chậm?
Mã sau mất khoảng 15 giây để chạy. Tôi có một giải pháp Java không đệ quy chạy trong 1s. Tôi nghĩ rằng tôi sẽ có thể nhận được mã này gần gũi hơn với điều đó.
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])
Tôi đã lược tả với +RHS -p và nhận thấy rằng bộ nhớ được phân bổ lớn và phát triển khi đầu vào tăng. Đối với n = 100,000 1gb được cấp phát (!), Cho n = 1,000,000 13gb (!!) được phân bổ.
Sau đó, một lần nữa, -sstderr cho thấy mặc dù nhiều byte được phân bổ, tổng dung lượng bộ nhớ là 1mb và năng suất là 95% +, vì vậy có thể 13gb là cá trích đỏ.
tôi có thể nghĩ ra một vài khả năng:
Something là không chặt chẽ như nó cần phải được. Tôi đã phát hiện
foldl1', nhưng có lẽ tôi cần phải làm nhiều hơn? Có thể đánh dấucollatznhư nghiêm ngặt (Điều đó thậm chí có ý nghĩa?collatzkhông đuôi-gọi tối ưu hóa. Tôi nghĩ rằng nó phải được nhưng đừng biết một cách để xác nhận.Trình biên dịch không được thực hiện một số tối ưu hóa tôi nghĩ rằng nó nên - ví dụ chỉ có hai kết quả
collatzcần phải được trong bộ nhớ cùng một lúc (tối đa và hiện tại)
mọi góp ý
?Đây là khá nhiều bản sao của Why is this Haskell expression so slow?, mặc dù tôi sẽ lưu ý rằng giải pháp Java nhanh không phải thực hiện bất kỳ ghi nhớ nào. Có cách nào để tăng tốc độ này mà không cần phải sử dụng nó?
Để tham khảo, đây là đầu ra của tôi profiling:
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
Và -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
Và giải pháp Java (không phải của tôi, lấy từ các diễn đàn Project Euler với memoization loại bỏ):
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);
}
}
Thật đáng ngạc nhiên rằng GHC không tối ưu hóa (quot n 2) đến (rshift n 1) giống như bất kỳ trình biên dịch C tự tôn trọng nào được mong đợi sẽ làm. Có lý do gì không? –
@ solrize: Nó làm tôi ngạc nhiên. – ehird