Bazı Proje çözme Haskell şu anda tamamen bir acemi değilim yani) öğrenmek Sorunlar Euler süre Problem 13 geldim. (Naif) bu çözümü yazdım:

--Get Number of Divisors of n
numDivs :: Integer -> Integer
numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2) 1)], n `rem` x == 0]   2

--Generate a List of Triangular Values
triaList :: [Integer]
triaList =  [foldr ( ) 0 [1..n] | n <- [1..]]

--The same recursive
triaList2 = go 0 1
  where go cs n = (cs n):go (cs n) (n 1)

--Finds the first triangular Value with more than n Divisors
sol :: Integer -> Integer
sol n = head $ filter (\x -> numDivs(x)>n) triaList2

N için bu Çözüm=500 (sol 500) son derece yavaş (2 saatten fazla çalışan), bu çözüm çok yavaş neden bulmak için nasıl merak ettim. Hesaplama zamanı en çok harcama nerede olduğunu söyle ki tüm komutları ben yavaş olduğunu bilmek var mı? Basit bir profiler gibi bir şey.

Açık olmak istemiyorumiçindaha hızlı bir çözüm amabir şekildebu çözümü bulmak için. Nasıl eğer haskell bilgi sahibi olsaydın yapardın?

İki triaList fonksiyonları yazmaya çalıştım ama daha hızlı olduğu, bu yüzden benim sorunlar başlar, nereye kadar bu test etmek için bir yol buldu.

Teşekkürler

nasıl bu çözüm çok yavaş nedenini bulmak için. Hesaplama zamanı en çok harcama nerede olduğunu söyle ki tüm komutları ben yavaş olduğunu bilmek var mı?

Kesinlikle! DZD birçok mükemmel araçlar sağlar:

• runtime statistics
• time profiling
• heap profiling
• thread analysis
• core analysis.
• comparative benchmarking
• GC tuning

Zaman ve mekan profil kullanarak bir öğretici part of Real World Haskell.

GC İstatistikleri

Öncelikle, dzd-O2 ile derleme çok önemlidir. Ve modern bir DZD (örneğin DZD 6.12.bundan emin olabilirsin x)

Yapabileceğimiz ilk şey çöp toplama sorunu olup olmadığını kontrol edin. -S RTS ile programı çalıştırın

$ time ./A  RTS -s
./A  RTS -s 
749700
   9,961,432,992 bytes allocated in the heap
       2,463,072 bytes copied during GC
          29,200 bytes maximum residency (1 sample(s))
         187,336 bytes maximum slop
               **2 MB** total memory in use (0 MB lost due to fragmentation)

  Generation 0: 19002 collections,     0 parallel,  0.11s,  0.15s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   13.15s  ( 13.32s elapsed)
  GC    time    0.11s  (  0.15s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   13.26s  ( 13.47s elapsed)

  %GC time       **0.8%**  (1.1% elapsed)

  Alloc rate    757,764,753 bytes per MUT second

  Productivity  99.2% of total user, 97.6% of total elapsed

./A  RTS -s  13.26s user 0.05s system 98% cpu 13.479 total

Olan zaten bize pek çok bilgi verir: sadece 2M bir yığın var, ve GC zaman 0.8'ini kaplar. Hayır ayırma sorun olduğunu endişelenmenize gerek yok.

Zaman Profilleri

Programınız için profil ileriye doğru düz bir zaman:- prof-oto-derleme

 $ ghc -O2 --make A.hs -prof -auto-all
 [1 of 1] Compiling Main             ( A.hs, A.o )
 Linking A ...

Ve,=200 N:

$ time ./A  RTS -p                   
749700
./A  RTS -p  13.23s user 0.06s system 98% cpu 13.547 total

bir dosya, A. prof, içeren oluşturur:

    Sun Jul 18 10:08 2010 Time and Allocation Profiling Report  (Final)

       A  RTS -p -RTS

    total time  =     13.18 secs   (659 ticks @ 20 ms)
    total alloc = 4,904,116,696 bytes  (excludes profiling overheads)

COST CENTRE          MODULE         %time %alloc

numDivs            Main         100.0  100.0

Gösterentümzaman numDivs geçirdi, ve aynı zamanda tüm ayırmaları kaynağıdır.

Yığın Profilleri

Sen-ebilmek da almak bir yıkmak bu ayırma ile çalışan RTS -p -hy oluşturan A. hp, görünüm dönüştürme için bir postscript dosyası (hp2ps -c A. hp), üretimi

hangi yanlış bir şey var söyler bellek kullanımı: sabit uzayda ayırma.

Yani senin sorunun numDivs algoritmik karmaşıklık

toInteger $ length [ x | x<-[2.. ((n `quot` 2) 1)], n `rem` x == 0]   2

Koşu zaman 0 olan, tamir, ve diğer her şey kolaydır.

En iyi duruma getirme

Bu ifade Gözden geçireceğim yani stream fusion optimizasyon için iyi bir aday olduğunu, Data.Vector gibi yani kullanmak için:

numDivs n = fromIntegral $
    2   (U.length $
        U.filter (\x -> fromIntegral n `rem` x == 0) $
        (U.enumFromN 2 ((fromIntegral n `div` 2)   1) :: U.Vector Int))

Gereksiz bir yığın ayırma ile tek bir döngü içine sigorta gerekir. Liste versiyonu daha iyi karmaşıklığı (sabit faktörler) sahip olacaktır. Optimizasyon sonra Ara kod incelemek dzd-core aracı (gelişmiş kullanıcılar için) kullanabilirsiniz.

Bu test, O2 --Z. hs olun dzd

$ time ./Z     
749700
./Z  3.73s user 0.01s system 99% cpu 3.753 total

N süre=150 algoritma değiştirmeden 3.5 x tarafından düşürüldü.

Sonuç

Senin sorunun numDivs. Koşu zaman 0 değildir ve korkunç bir karmaşıklık var.NumDivs düşünün, ve nasıl, her N için, örneğin, [2 .. ndiv 2 1] N kat oluşturma. Değerleri değiştirmek değil, çünkü o memoizing deneyin.

Daha hızlı olan, ölçmek için, zaman çalışan alt mikrosaniye gelişmeler hakkında istatistiksel olarak sağlam bilgi verecek criterion, kullanmayı düşünün.

Gündemin

NumDivs çalışan zaman 0 olduğundan, programın diğer bölümlerini dokunaklı çok fazla fark etmeyecek ancak, pedagojik amaçlar için de kullananlar akışı füzyon yazabiliriz.

Ayrıca trialList yeniden yazmak ve füzyon güveniyor trialList2 elle yazmak döngü çevirmek için elimizden bir "olan" fonksiyonu (aka scanl): . önek tarama

triaList = U.scanl ( ) 0 (U.enumFrom 1 top)
    where
       top = 10^6

Sol için aynı şekilde:

sol :: Int -> Int
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList

Aynı toplam çalışma süresi ile, ama biraz daha temiz kod.