Осваиваю Haskell. Решил написать утилиту для обработки файлов данных. Консольная программа получает на входе файл из строк вида:
1 2 3
7 8 4
9 5 1
т.е. в каждой строке по вектору. Длина векторов во всех строках одинаковая. На выходе должен быть вектор из средних значений, то есть:
11 11.67 7,33
Программу я написал быстро, даже сам удивился. Приводить её здесь не стану, всё очевидно. Но она, собака, при обработке больших файлов (в несколько Мб) отжирает сотни Мб памяти и при этом работает очень долго.
Я сходил на IRC#haskell взять помощи у зала. Тамошние гуру подкинули несколько интересных решений, но все они:
— не работают в постоянном объёме памяти;
— тормозят!
Теми же гуру было дано решение, использующее mutable arrays и прочие императивные штучки, но я ведь не за этим сюда пришёл? Императивности мне хватает в C++, кстати утилита с нужной функциональностью, написанная на C++, совершенно неоптимально, проглатывает файлы за долю секунды и требует минимума ОЗУ.
Где-то я видел, что Haskell рекомендуют для быстрого написания как раз подобных утилит (всяких фильтров и пр.). Быстро получается, убедился, но производительность — хуже, чем на Бейсике.
Для каких задач применим Haskell по-Вашему? Я ищу высокоуровневый язык для реализации матмоделей из области физики, думал, что Haskell — самое то, но что-то не выходит...
Re: [haskell] вычисление средних значений векторов
Здравствуйте, Oboltus, Вы писали:
O>Программу я написал быстро, даже сам удивился. Приводить её здесь не стану, всё очевидно. Но она, собака, при обработке больших файлов (в несколько Мб) отжирает сотни Мб памяти и при этом работает очень долго.
Про то как на Хаскеле писать (более-менее) шустрые программы даже без императивщины на этом форуме обсуждалось не раз. Правда, в ветках не по теме. А вообще-то почти любое обсуждение Хаскеля на RSDN затрагивает этот вопрос.
O>Для каких задач применим Haskell по-Вашему? Я ищу высокоуровневый язык для реализации матмоделей из области физики, думал, что Haskell — самое то, но что-то не выходит...
Модели моделям рознь. Некоторые на Хаскель ложатся просто идеально. По моим ощущениям — так или иначе связанные с (или сводящиеся к) обработкой сигналов/потоков. Там рулят бесконечные списки и стрелки.
А сам я писал одну моделирующую программу по физике на OCaml. С него начинал ФП вообще.
Re: [haskell] вычисление средних значений векторов
Интересно все же иметь некоторый материал для обсуждения, а не разводить пустой флейм. Например начать с показа самой быстрой функциональной версии, где уже убраны простейшие грабли (типа s/foldl/foldl'/).
Re: [haskell] вычисление средних значений векторов
Есть такая фигня -- на больших объемах данных, если результат нужен только в конце, накапливается огроменная невычисленная цепочка ленивых thunk-ов.
Иногда компиляция с -O2 помогает, но чаще всего приходится делать strict annotation-ы.
Нужно их обычно мало, но надо еще найти, куда их вставить. Например:
{-# LANGUAGE BangPatterns #-}
import Data.List
seqList [] = []
seqList a@(x:xs) = x `seq` seqList xs `seq` a
avgVec = avg . foldl' sum (0, [0,0..]) . map (map read . words) . lines
where sum (!count, !a) b = (count+1, seqList $ zipWith (+) a b)
avg (count, a) = map (/count) a
test n = avgVec $ unlines (take n $ repeat "1 2 3")
Здесь, кроме достаточно очевидных !count и !a, есть еще и foldl' и seqList, до которых допереть можно не сразу.
Это все, конечно, минус, но он вытекает из огромного плюса хаскелла -- ленивости. Представь, что у тебя не просто сумма, а какое-нибудь сложное вычисление, которое может на каком-то этапе остановиться (поиск решения, например). Благодаря ленивости ты, вообще не запариваясь, работаешь с бесконечным списком (или огромным файлом) и отваливаешься когда надо.
Если кроме данных, необходимых для принятия решения об окончания прохода по списку, возвращаются еще какие-то данные, то придется добавлять strict annotation-ы, чтобы они считались по ходу, а не в конце.
В целом, правила добавления strict annotation-ов не столь сложны (да и редко это нужно, чаще от них только тормоза появляются). По мне, увеличение скорости разработки за счет более высокого уровня языка с лихвой окупают необходимость иногда добавлять strict-ы.
Re[2]: [haskell] вычисление средних значений векторов
Данный пример как бы говорит нам, что Хаскель станет мэйнстримом не раньше, чем произойдет одно из двух событий:
а) анализатор строгости научится решать подобные вопросы автоматически, или
б) машину тьюринга таки реализуют до конца — с бесконечной лентой.
Re[2]: [haskell] вычисление средних значений векторов
N>Интересно все же иметь некоторый материал для обсуждения, а не разводить пустой флейм. Например начать с показа самой быстрой функциональной версии, где уже убраны простейшие грабли (типа s/foldl/foldl'/).
zipWith' f (a:as) (b:bs) =
let v = f a b
in v `seq` v : zipWith' f as bs
meanvec :: [[Double]] -> [Double]
meanvec xs =
let (total, n) = foldl' (\(s, n) x -> (zipWith' (+) x s, n + 1)) (repeat 0, 0) xs
in map (/n) total
Re[2]: [haskell] вычисление средних значений векторов
Здравствуйте, vshabanov, Вы писали: V>Здесь, кроме достаточно очевидных !count и !a, есть еще и foldl' и seqList, до которых допереть можно не сразу.
Декларативность тоже не на высоте. То есть, решения "в лоб" на Хаскелле работаю так же плохо, как на любом другом ЯП.
Хотя прогресс по сравнению с C++ виден.
Re[3]: [haskell] вычисление средних значений векторов
От:
Аноним
Дата:
30.03.09 09:46
Оценка:
Здравствуйте, Oboltus, Вы писали:
O>Здравствуйте, vshabanov, Вы писали: V>>Здесь, кроме достаточно очевидных !count и !a, есть еще и foldl' и seqList, до которых допереть можно не сразу.
O>Декларативность тоже не на высоте. То есть, решения "в лоб" на Хаскелле работаю так же плохо, как на любом другом ЯП. O>Хотя прогресс по сравнению с C++ виден.
Не далее как на выходных делал примерно то же самое, читал из файла 300Мб циферок (с простенькой обработкой данных). Уложился в полминуты и константную память (около 30 мб).
Советы такие:
— компилируем с -O2;
— используем ленивые ByteStrings;
— преобразуем их в циферки с помощью readInt и readDouble (вторая из пакета bytestring-lexing);
— бездумно вставлять тут и там seq и ! не стоит, зря потратите кучу времени.
— если хотите больше советов, выкладывайте код целиком.
Из условия не совсем ясно среднее считается по строчкам или столбцам?
Re: [haskell] вычисление средних значений векторов
Здравствуйте, Oboltus, Вы писали:
O>Для каких задач применим Haskell по-Вашему? Я ищу высокоуровневый язык для реализации матмоделей из области физики, думал, что Haskell — самое то, но что-то не выходит...
Хаскель для работы с мат. данными не предназначен. Используй солидные векторные языки (Q например):
Здравствуйте, Quintanar, Вы писали: Q>Хаскель для работы с мат. данными не предназначен. Используй солидные векторные языки (Q например):
А для чего тогда? ФП-подход очень даже математичен, на первый взгляд.
Re[3]: [haskell] вычисление средних значений векторов
От:
Аноним
Дата:
31.03.09 06:47
Оценка:
Здравствуйте, Oboltus, Вы писали:
O>Здравствуйте, Quintanar, Вы писали: Q>>Хаскель для работы с мат. данными не предназначен. Используй солидные векторные языки (Q например):
O>А для чего тогда? ФП-подход очень даже математичен, на первый взгляд.
Хаскель для всего предназначен, он общего назначения язык.
Просто, как и везде, есть свои подводные камни.
Пока не придумали языка чтобы код и декларативный был, и на все случаи жизни подходил.
Re[3]: [haskell] вычисление средних значений векторов
O>zipWith' f (a:as) (b:bs) =
O> let v = f a b
O> in v `seq` v : zipWith' f as bs
O>meanvec :: [[Double]] -> [Double]
O>meanvec xs =
O> let (total, n) = foldl' (\(s, n) x -> (zipWith' (+) x s, n + 1)) (repeat 0, 0) xs
O> in map (/n) total
O>
Попробуйте стандартный паттерн с аккумуляторами. Что-то вроде (тут еще длина вектора задается явно):
meanvec :: Int -> [[Double]] -> [Double]
meanvec vlen xs =
let
init = replicate vlen 0
(total, n) = go xs 0 init
in map (/n) total
where go [] n acc = (acc, n)
go (x:xs) n acc = go xs (n+1) $ zipWith (+) x acc
Re: [haskell] вычисление средних значений векторов
Здравствуйте, Oboltus, Вы писали:
O>Программу я написал быстро, даже сам удивился. Приводить её здесь не стану, всё очевидно. Но она, собака, при обработке больших файлов (в несколько Мб) отжирает сотни Мб памяти и при этом работает очень долго.
Давайте по-порядку...
Генерируем тестовые файлики (массив (rows x cols) заполненный числами и записанный в файл)
genData rows cols = [ [r*1.0..r+cols-1] | r <- [1..rows]]
genFile rows cols file = writeFile file $ unlines [intercalate " " $ map show line | line <- genData rows cols]
Т.к. мы часто будем работать с массивами хранящимися в файлах напишем:
-- читает двумерный массив из файла
readArray2 :: String -> IO [[Double]]
readArray2 file = do
str <- readFile file
return [map read $ split ' ' line | line <- lines str]
-- записывает массив в файл
writeArray :: String -> [Double] -> IO ()
writeArray file arr = writeFile file (intercalate " " $ map show arr)
-- обрабатывает inFile функцией fun и записывает результат в outFile
process inFile outFile fun = readArray2 inFile >>= return . fun >>= writeArray outFile
Наш framework закончился. Теперь рассмотрим нашу обработку массива.
Т.к. вычисления среднего в стандартной библиотеке нет (вроде), добавим его.
-- вычисляет среднее значение массива
avg :: [Double] -> Double
avg xs = sum xs / fromIntegral (length xs)
-- непосредственно обработка
fun :: [[Double]] -> [Double]
fun as = [avg line | line <- as]
Теперь осталось это все запустить. Названия файлов берем из командной строки.
main = do
args <- getArgs
let (inFile : outFile : _) = args
process inFile outFile fun
Получаем вот что: small — 2 Мб / 6 сек, big — 3 Мб / 100 сек
Работает, действительно, долго. Однако с памятью все в порядке — не зависит от размера файла.
Для справки. Эти файлы обрабатываются на java соответственно за 0,2 и 3,2 сек. Т.е. раз так в 30 быстрее.
Основная причина медленной работы — тормознутость функции read и show. Ускорим read/show.
Используем код взятый с haskell.org http://www.haskell.org/haskellwiki/Examples/Read_Double. Короче, заменим read и show для double на функции из библиотеки С.
Я добавил заголовок модуля (иморт и экспорт). Файл QuickDouble.hs
{-# OPTIONS -ffi #-}module QuickDouble (
readDouble,
showDouble
) where
import Data.ByteString.Lazy.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B
import qualified Data.ByteString as BS
import qualified Data.ByteString.Lazy.Char8 as L
import qualified Data.ByteString.Internal as BS
import Foreign
import Foreign.C.Types
import System.IO.Unsafe
------------------------------------------------------------------------
--
-- read a Double from a lazy ByteString
-- 'read' should be a pure operation, right??
--
readDouble :: ByteString -> Double
readDouble ls = unsafePerformIO $ B.useAsCString s $ \cstr ->
realToFrac `fmap` c_strtod cstr nullPtr
where
s = B.concat . L.toChunks $ ls
foreign import ccall unsafe "static stdlib.h strtod" c_strtod
:: Ptr CChar -> Ptr (Ptr CChar) -> IO CDouble
------------------------------------------------------------------------
--
-- show a Double into a lazy bytestring
--
showDouble :: Double -> ByteString
showDouble d = L.fromChunks . return . unsafePerformIO . BS.createAndTrim lim $ \p ->
B.useAsCString fmt $ \cfmt -> do
n <- c_printf_double (castPtr p) (fromIntegral lim) cfmt (realToFrac d)
return (min lim (fromIntegral n)) -- snprintf might truncatewhere
lim = 100 -- n.b.
fmt = B.pack "%f"
foreign import ccall unsafe "static stdio.h snprintf"
c_printf_double :: Ptr CChar -> CSize -> Ptr CChar -> CDouble -> IO CInt
Ну и заменим строки на ByteString. Теперь две функции нашей библиотеки будут выглядеть так.
import qualified Data.ByteString.Lazy.Char8 as B
import QuickDouble -- наш новоиспеченный модуль
-- читает двуменрный массив из файла
readArray2 :: String -> IO [[Double]]
readArray2 file = do
str <- B.readFile file
return [map readDouble $ B.split ' ' line | line <- B.lines str]
-- записывает массив в файл
writeArray :: String -> [Double] -> IO ()
writeArray file arr = B.writeFile file (B.intercalate (B.pack " ") $ map showDouble arr)
Видно как мало в них всего поменялось. И все остальное осталось без изменений!
Запускаем...
Получаем вот что: small — 2 Мб / 0,3 сек, big — 2 Мб / 5 сек.
Ускорение в 20 раз! За счет ByteString на память почти никакого влияния размер файла не оказывает.
Конечно, все равно получилось медленнее, чем даже на Java (раза в 1,5). Но что еще сделать, я не знаю Будем надеяться, что этой скорости будет достаточно. Ведь самое главное что теперь есть:
Все, забыли про файлы! Акцентируем внимание на обработке.
Ну и еще.
-- Функцию avg можно ускорить (процентов на 10)
avg xs = avg' xs 0 0
where avg' [] sum count = sum / count
avg' (p:ps) sum count = avg2' ps (sum+p) (count+1)
-- разделяет список на основе заданного разделителя
-- этой функции в библиотеке нет, зато есть в интернете. А для ByteString - в библиотеке есть
split _ [] = [ [] ]
split delim (c:cs)
| c == delim = [] : rest
| otherwise = (c : head rest) : tail rest
where
rest = split delim cs
O>Где-то я видел, что Haskell рекомендуют для быстрого написания как раз подобных утилит (всяких фильтров и пр.). Быстро получается, убедился, но производительность — хуже, чем на Бейсике.
Как видно выше, это неправда. Haskell достаточно быстр и гибок. Хотя, память жрет...
O>Для каких задач применим Haskell по-Вашему? Я ищу высокоуровневый язык для реализации матмоделей из области физики, думал, что Haskell — самое то, но что-то не выходит...
Это действительно самое то, если необходимы эксперименты. Т.е. сейчас такая обработка, а может сделаем такую? затем такую ... Т.е. если гибкость очень важна.
... << RSDN@Home 1.2.0 alpha 4 rev. 1136>>
Best regards, Буравчик
Re[2]: [haskell] вычисление средних значений векторов
Здравствуйте, Beam, Вы писали:
B>Т.к. мы часто будем работать с массивами хранящимися в файлах напишем: B>
B>-- обрабатывает inFile функцией fun и записывает результат в outFile
B>process inFile outFile fun = readArray2 inFile >>= return . fun >>= writeArray outFile
B>
Для полноты библиотеки, можно добавить:
-- работа с файлами
process (inFun,inFile) procFun (outFun,outFile) = inFun inFile >>= return . fun >>= outFun outFile
-- осталось создать
readArray = ... - читаем одномерный массив
readArray2 = ... - читаем двухмерный массив
readArray3 = ... - читаем трехмерный массив
writeArray = ... - то же для записи массивов
writeArray2 = ...
writeArray3 = ...
-- используем
proc3Dto1D = ...
process (readArray3, "3D.txt") proc3Dto1D (writeArray, "1D.txt")
... << RSDN@Home 1.2.0 alpha 4 rev. 1136>>
Best regards, Буравчик
Re[2]: [haskell] вычисление средних значений векторов
Здравствуйте, Oboltus, Вы писали:
O>P.S. А разве стандартная функция words не заменяет самописную split?
Да уж. В данном контексте заменяет. Что-то я не подумал про нее:
split ' ' == words
intercalate " " = unwords