Bagaimana cara meningkatkan efisiensi dengan pemrograman fungsional?

Saya baru-baru ini telah melalui panduan Pelajari Anda Haskell untuk Great Good dan sebagai praktik saya ingin menyelesaikan Project Euler Problem 5 dengan itu, yang menentukan:

Berapakah angka positif terkecil yang secara merata dapat dibagi oleh semua angka dari 1 hingga 20?

Saya memutuskan untuk terlebih dahulu menulis fungsi yang menentukan apakah angka yang diberikan dapat dibagi dengan angka-angka ini:

divisable x = all (\y -> x `mod` y == 0)[1..20]

Lalu saya menghitung yang terkecil menggunakan head:

sm = head [x | x <- [1..], divisable x]

Dan akhirnya menulis baris untuk menampilkan hasilnya:

main = putStrLn $ show $ sm

Sayangnya ini membutuhkan waktu sekitar 30 detik untuk menyelesaikannya. Melakukan hal yang sama dengan angka 1 hingga 10 menghasilkan hasil segera, tetapi sekali lagi hasilnya jauh lebih kecil daripada solusi untuk 1 hingga 20.

Saya menyelesaikannya sebelumnya di C dan di sana hasilnya selama 1 hingga 20 juga dihitung hampir secara instan. Ini membuat saya percaya bahwa saya salah mengerti bagaimana menafsirkan masalah ini untuk Haskell. Saya melihat melalui solusi orang lain dan menemukan ini:

main = putStrLn $ show $ foldl1 lcm [1..20]

Cukup adil, ini menggunakan fungsi bawaan, tetapi mengapa hasil akhirnya jauh lebih lambat saat melakukannya sendiri? Tutorial di luar sana memberi tahu Anda cara menggunakan Haskell, tapi saya tidak melihat banyak bantuan dengan mengubah algoritma menjadi kode cepat.

Pertama, Anda perlu memastikan bahwa Anda memiliki biner yang dioptimalkan, sebelum berpikir bahasa adalah masalahnya. Baca bab Profiling dan pengoptimalan di Real Wolrd Haskell. Perlu dicatat bahwa dalam sebagian besar kasus, sifat bahasa tingkat tinggi mengharuskan Anda setidaknya melakukan beberapa pertunjukan.

Namun, perhatikan bahwa solusi lain tidak lebih cepat karena menggunakan fungsi bawaan , tetapi hanya karena menggunakan algoritma yang jauh lebih cepat : untuk menemukan kelipatan paling umum dari serangkaian angka, Anda hanya perlu menemukan beberapa GCD. Bandingkan ini dengan solusi Anda, yang menggilir semua angka dari 1 hingga foldl lcm [1..20]. Jika Anda mencoba dengan 30, perbedaan antara runtime akan lebih besar.

Lihatlah kompleksitas: algoritma Anda memiliki O(ans*N)runtime, di manaans jawabannya dan Nmerupakan jumlah hingga Anda memeriksa keterpisahan (20 dalam kasus Anda).
Algoritma lain mengeksekusi Nwaktu lcm, namun lcm(a,b) = a*b/gcd(a,b), dan GCD memiliki kompleksitas O(log(max(a,b))). Oleh karena itu algoritma kedua memiliki kompleksitas O(N*log(ans)). Anda dapat menilai sendiri mana yang lebih cepat.

Jadi, untuk meringkas:
Masalah Anda adalah algoritma Anda, bukan bahasa.

Perhatikan bahwa ada bahasa khusus yang fungsional dan terfokus pada program matematika, seperti Mathematica, yang untuk masalah yang berfokus pada matematika mungkin lebih cepat daripada hampir semua hal lain. Ini memiliki perpustakaan fungsi yang sangat optimal, dan mendukung paradigma fungsional (diakui juga mendukung pemrograman imperatif).

Pikiran pertama saya adalah bahwa hanya angka yang dapat dibagi oleh semua bilangan prima <= 20 akan dapat dibagi dengan semua angka kurang dari 20. Jadi Anda hanya perlu mempertimbangkan angka yang merupakan kelipatan dari 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 . Solusi semacam itu memeriksa angka 1 / 9.699.690 sebanyak jumlah pendekatan brute force. Tetapi solusi Haskell cepat Anda lebih baik dari itu.

Jika saya memahami solusi "fast Haskell", ia menggunakan foldl1 untuk menerapkan fungsi lcm (multiple paling umum) ke daftar angka dari 1 hingga 20. Jadi itu akan berlaku lcm 1 2, menghasilkan 2. Kemudian lcm 2 3 menghasilkan 6 Lalu lcm 6 4 menghasilkan 12, dan seterusnya. Dengan cara ini, fungsi lcm hanya dipanggil 19 kali untuk menghasilkan jawaban Anda. Dalam notasi O Besar, itulah operasi O (n-1) untuk mencapai solusi.

Solusi Haskell lambat Anda menembus angka 1-20 untuk setiap angka dari 1 hingga solusi Anda. Jika kita memanggil solusi s, maka solusi Haskell lambat melakukan operasi O (s * n). Kita sudah tahu bahwa lebih dari 9 juta, sehingga mungkin menjelaskan kelambatannya. Bahkan jika semua pintasan dan mendapatkan rata-rata setengah jalan melalui daftar angka 1-20, itu masih hanya O (s * n / 2).

Memanggil headtidak menyelamatkan Anda dari melakukan perhitungan ini, mereka harus dilakukan untuk menghitung solusi pertama.

Terima kasih, ini pertanyaan yang menarik. Itu benar-benar memperluas pengetahuan Haskell saya. Saya tidak akan bisa menjawabnya sama sekali jika saya belum mempelajari algoritma musim gugur yang lalu.

Awalnya saya tidak berencana menulis jawaban. Tapi saya diberitahu setelah pengguna lain membuat klaim aneh bahwa hanya mengalikan pasangan primes pertama lebih mahal secara komputasi kemudian berulang kali mendaftar lcm. Jadi inilah dua algoritma, dan beberapa tolok ukur:

Algoritme saya:

Algoritma generasi perdana, memberi saya daftar bilangan prima yang tak terbatas.

isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = all ((/= 0) . mod n) (takeWhile ((<= n) . (^ 2)) primes)

toPrime :: Int -> Int
toPrime n 
    | isPrime n = n 
    | otherwise = toPrime (n + 1)

primes :: [Int]
primes = 2 : map (toPrime . (+ 1)) primes

Sekarang menggunakan daftar utama itu untuk menghitung hasilnya untuk beberapa N:

solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 $ takeWhile (<= n) (fromIntegral <$> primes)

Sekarang algoritma berbasis lcm lainnya, yang diakui cukup ringkas, sebagian besar karena saya menerapkan generasi utama dari awal (dan tidak menggunakan algoritma pemahaman daftar yang sangat ringkas karena kinerjanya yang buruk) sedangkan lcmhanya diimpor dari Prelude.

solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without `flip` on `lcm`

Sekarang untuk tolok ukur, kode yang saya gunakan untuk masing-masing sederhana: ( -prof -fprof-auto -O2lalu +RTS -p)

main :: IO ()
main = print $ solvePrime n
-- OR
main = print $ solveLcm n

Untuk n = 100,000, solvePrime:

total time = 0.04 secs
total alloc = 108,327,328 bytes

vs solveLcm:

total time = 0.12 secs
total alloc = 117,842,152 bytes

Untuk n = 1,000,000, solvePrime:

total time = 1.21 secs
total alloc = 8,846,768,456 bytes

vs solveLcm:

total time = 9.10 secs
total alloc = 8,963,508,416 bytes

Untuk n = 3,000,000, solvePrime:

total time = 8.99 secs
total alloc = 74,790,070,088 bytes

vs solveLcm:

total time = 86.42 secs
total alloc = 75,145,302,416 bytes

Saya pikir hasilnya berbicara sendiri.

Profiler menunjukkan bahwa generasi utama membutuhkan persentase run time yang nsemakin kecil seiring dengan peningkatan. Jadi ini bukan hambatannya, jadi kita bisa mengabaikannya untuk saat ini.

Ini berarti kita benar-benar membandingkan pemanggilan di lcmmana satu argumen beranjak dari 1 ke n, dan yang lainnya berjalan secara geometris dari 1 ke ans. Untuk menelepon *dengan situasi yang sama dan manfaat tambahan untuk melewati setiap nomor non-prima (asimtotik gratis, karena sifat yang lebih mahal dari *).

Dan diketahui bahwa *lebih cepat dari lcm, seperti yang lcmmembutuhkan aplikasi berulang mod, dan modsecara asimptot lebih lambat ( O(n^2)vs ~O(n^1.5)).

Jadi hasil di atas dan analisis algoritma singkat harus membuatnya sangat jelas algoritma mana yang lebih cepat.