Tại sao chương trình phân tích văn bản đơn giản này lại quá chậm?

Question

Đây là mã của tôi để đếm dòng và dòng chữ:

import System.IO 
import Data.List 
main = do 
     hSetBinaryMode stdin True 
     interact $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n") 
        . foldl' (\(w,l) r-> w `seq` l `seq` (w+length r ,succ l)) (0,0) 
        . lines 

này mất khoảng 10 giây để chạy trên một tập tin của khoảng 100 MB. Tôi so sánh nó với các chương trình tương tự trong Lua (9s), awk (20s), và wc -l -c (0.6s).

Tại sao mã này quá chậm? Điều gì có thể là vấn đề?

Answer 1

I/O với String được biết là nhanh hơn Haskell. Các byte đọc từ tay cầm nói chung phải được chuyển đổi thành các điểm mã Unicode, và sau đó một danh sách liên kết được xây dựng từ những điểm đó. Đó là rất nhiều công việc gây ra rất nhiều phân bổ. Trong trường hợp này, việc chuyển đổi sang các điểm mã đơn giản hơn một chút, vì bạn đặt stdin thành chế độ nhị phân, nhưng việc xây dựng danh sách các ký tự liên kết vẫn mất nhiều thời gian.

Một yếu tố nhỏ khác là số lượng dòng của bạn đang sử dụng Integer, nhưng đó là nhỏ và chỉ đóng vai trò quan trọng khi I/O tăng tốc.

Nếu bạn cần nhanh I/O, bạn phải sử dụng loại phù hợp hơn cho điều đó. Một khả năng được sử dụng ByteString, ví dụ

import Data.List 
import qualified Data.ByteString.Lazy.Char8 as C 
main = do 
     txt <- C.getContents 
     putStrLn $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n"). foldl' (\(w,l) r-> w `seq` l `seq` (w+C.length r ,succ l)) (0,0) . C.lines $ txt 

hiện công việc trên một tập tin 94MB trong 0.12s trên hộp của tôi (wc -l -c mất 0.06s), trong khi bản gốc sử dụng String mất 4.4s. Nó có thể được tối ưu hóa hơn nữa,

{-# LANGUAGE BangPatterns #-} 
import Data.List 
import qualified Data.ByteString.Lazy.Char8 as C 
main = do 
     txt <- C.getContents 
     putStrLn $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n"). loop 0 0 . C.lines $ txt 

loop :: Int -> Int -> [C.ByteString] -> (Int,Int) 
loop !w !l (ln:lns) = loop (w + fromIntegral (C.length ln)) (l+1) lns 
loop w l _ = (w,l) 

chỉ mất 0.08s, đó là đủ đàng hoàng cho tôi để ngăn chặn tối ưu hóa có (một sự thay đổi tương tự cho phiên bản String mang lại thời gian xuống 3.6s cho điều đó).