palm_mute (![[info]](http://p-stat.livejournal.com/img/userinfo.gif){kind=small} palm_mute) wrote,@ 2007-07-06 12:59:00 |
|
| Entry tags: | continuations, haskell, ocaml |
К вопросу об эффективности композиции
Хотелось бы написать о чем-то возвышенном - например, о delimited continuations и инверсии парсеров, а еще раскритиковать трансформеры монад по ходу дела. Но, к сожалению, я пока мало в этом разбираюсь, потому напишу об обычных списках и функциях.
Как известно, добавлять элементы в конец списка в Haskell и других функциональных языках неэффективно. Поэтому, если эту операцию требуется делать в цикле, применяются различные трюки - накапливать в обратном порядке, а затем разворачивать, или более элегантно - представлять недостроенные списки в виде функций.
type PartialList a = [a]-> [a]
Подход известный, используется в стандартной библиотеке (см. тип ShowS и связанные с ним функции) и не ограничивается списками - Conal Elliot недавно писал об общем случае.
Конкатенация частичных списков - это просто композиция функций:
emptyPartialList = id addElem :: a -> PartialList a addElem x = (x:) toList :: PartialList a -> [a] toList p = p [] -- test = [1,2,3] test = toList $ emptyPartialList . addElem 1 . addElem 2 . addElem 3
Возникает вопрос о границах применимости данного подхода. Если формировать во внутреннем цикле длинные частичные списки - скажем, 20000 элементов - они будут представлены композицией 20000 крошечных функций. Насколько такое представление (не-)эффективно? Я измерил и был удивлен - значительно эффективнее, чем можно было ожидать. Приведенная ниже реализация функции inits разрывает библиотечную реализацию в тряпки:
myInits xs = loop xs emptyPartialList
where loop [] prefix = [toList prefix]
loop (x:xs) prefix = (toList prefix) : loop xs (prefix . addElem x)
Код теста:
test :: ([Int]->[[Int]]) -> Int -> Int
test initsf n = sum $ map sum $ initsf $ take n $ cycle [1,-1]
measure expr = do
t0 <- getClockTime
r <- return $! expr
t1 <- getClockTime
return (r, diffClockTimes t1 t0)
tests initsf = do
putStrLn "n\t\tresult\t\ttime"
putStrLn "============================================"
mapM_ printTiming [2000, 5000, 10000, 15000, 20000, 25000, 30000]
where printTiming n = do
(r, td) <- measure (test initsf n)
printf "%d\t\t%d\t\t%s\n" n r (timeDiffToString td)
main = do
putStrLn "Data.List.inits:"
tests inits
putStrLn "myInits"
tests myInits
Результаты:
Data.List.inits: n result time ============================================ 2000 1000 1 sec 5000 2500 1 sec 10000 5000 6 secs 15000 7500 32 secs 20000 10000 74 secs 25000 12500 129 secs 30000 15000 196 secs myInits n result time ============================================ 2000 1000 5000 2500 10000 5000 1 sec 15000 7500 2 secs 20000 10000 4 secs 25000 12500 6 secs 30000 15000 9 secs
Для полноты картины проверил, насколько хорошо Окамл справляется с десятками тысяч замыканий - оказалось, значительно хуже, чем Haskell:
n result time ============================================ 2000 1000 0.046000 sec(s) 5000 2500 0.500000 sec(s) 10000 5000 3.125000 sec(s) 15000 7500 8.781000 sec(s) 20000 10000 18.641000 sec(s) 25000 12500 32.905000 sec(s) 30000 15000 52.906000 sec(s)
Полный код теста на Окамле:
type 'a partial_list = 'a list -> 'a list
let empty_partial_list = fun x -> x
let append prefix x = fun xs -> prefix (x::xs)
let to_list p = p []
let iter_inits f xs =
let rec loop lst prefix = match lst with
| [] -> f (to_list prefix)
| x::xs -> begin f (to_list prefix); loop xs (append prefix x) end
in
loop xs empty_partial_list
let rec cycle = 1::-1::cycle
let sum = List.fold_left (+) 0
let rec take n lst = match (n, lst) with
| (0, _) -> []
| (_, []) -> []
| (n, x::xs) -> x :: take (n-1) xs
let test n =
let ret = ref 0 in
let process lst = ret := !ret + sum lst
in (iter_inits process (take n cycle); !ret)
let measure f =
let t0 = Sys.time () in
let r = f () in
let t1 = Sys.time () in
(r, t1 -. t0)
let main () =
let print_timing n =
let (r, td) = measure (fun () -> test n) in
begin
Printf.printf "%d\t\t%d\t\t%f sec(s)\n" n r td;
flush stdout
end
in
begin
print_endline "n\t\tresult\t\ttime";
print_endline "============================================";
List.iter print_timing [2000; 5000; 10000; 15000; 20000; 25000; 30000]
end
let _ = main ()
На сегодня все. Надо поработать и почитать диссертацию Анджея Филински "Declarative Continuations and Categorical Duality" - глядишь, будет чего написать и по более интересным вопросам.
