[haskell] вычисление средних значений векторов
От: Oboltus  
Дата: 27.03.09 19:37
Оценка:
Осваиваю 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] вычисление средних значений векторов
От: Code Digger Грузия  
Дата: 27.03.09 20:44
Оценка:
Здравствуйте, Oboltus, Вы писали:

O>Программу я написал быстро, даже сам удивился. Приводить её здесь не стану, всё очевидно. Но она, собака, при обработке больших файлов (в несколько Мб) отжирает сотни Мб памяти и при этом работает очень долго.


Про то как на Хаскеле писать (более-менее) шустрые программы даже без императивщины на этом форуме обсуждалось не раз. Правда, в ветках не по теме. А вообще-то почти любое обсуждение Хаскеля на RSDN затрагивает этот вопрос.


O>Для каких задач применим Haskell по-Вашему? Я ищу высокоуровневый язык для реализации матмоделей из области физики, думал, что Haskell — самое то, но что-то не выходит...


Модели моделям рознь. Некоторые на Хаскель ложатся просто идеально. По моим ощущениям — так или иначе связанные с (или сводящиеся к) обработкой сигналов/потоков. Там рулят бесконечные списки и стрелки.

А сам я писал одну моделирующую программу по физике на OCaml. С него начинал ФП вообще.
Re: [haskell] вычисление средних значений векторов
От: novitk США  
Дата: 27.03.09 21:11
Оценка:
Здравствуйте, Oboltus, Вы писали:

Интересно все же иметь некоторый материал для обсуждения, а не разводить пустой флейм. Например начать с показа самой быстрой функциональной версии, где уже убраны простейшие грабли (типа s/foldl/foldl'/).
Re: [haskell] вычисление средних значений векторов
От: vshabanov http://vshabanov-ru.blogspot.com
Дата: 27.03.09 21:25
Оценка:
Здравствуйте, Oboltus, Вы писали:

Есть такая фигня -- на больших объемах данных, если результат нужен только в конце, накапливается огроменная невычисленная цепочка ленивых 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] вычисление средних значений векторов
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 28.03.09 14:10
Оценка: 21 (1) :))) :))
Данный пример как бы говорит нам, что Хаскель станет мэйнстримом не раньше, чем произойдет одно из двух событий:
а) анализатор строгости научится решать подобные вопросы автоматически, или
б) машину тьюринга таки реализуют до конца — с бесконечной лентой.
Re[2]: [haskell] вычисление средних значений векторов
От: Oboltus  
Дата: 30.03.09 07:20
Оценка:
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] вычисление средних значений векторов
От: Oboltus  
Дата: 30.03.09 07:22
Оценка:
Здравствуйте, 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] вычисление средних значений векторов
От: Quintanar Россия  
Дата: 30.03.09 13:24
Оценка:
Здравствуйте, Oboltus, Вы писали:

O>Для каких задач применим Haskell по-Вашему? Я ищу высокоуровневый язык для реализации матмоделей из области физики, думал, что Haskell — самое то, но что-то не выходит...


Хаскель для работы с мат. данными не предназначен. Используй солидные векторные языки (Q например):

.Q.fs[{1 " " sv string avg each "I"$" "vs/:x}]`$":",.z.x[0]; 1"\n"; exit 0;
Re[2]: [haskell] вычисление средних значений векторов
От: Oboltus  
Дата: 30.03.09 14:45
Оценка:
Здравствуйте, Quintanar, Вы писали:
Q>Хаскель для работы с мат. данными не предназначен. Используй солидные векторные языки (Q например):

А для чего тогда? ФП-подход очень даже математичен, на первый взгляд.
Re[3]: [haskell] вычисление средних значений векторов
От: Аноним  
Дата: 31.03.09 06:47
Оценка:
Здравствуйте, Oboltus, Вы писали:

O>Здравствуйте, Quintanar, Вы писали:

Q>>Хаскель для работы с мат. данными не предназначен. Используй солидные векторные языки (Q например):

O>А для чего тогда? ФП-подход очень даже математичен, на первый взгляд.


Хаскель для всего предназначен, он общего назначения язык.
Просто, как и везде, есть свои подводные камни.
Пока не придумали языка чтобы код и декларативный был, и на все случаи жизни подходил.
Re[3]: [haskell] вычисление средних значений векторов
От: awson  
Дата: 31.03.09 10:42
Оценка:
Здравствуйте, Oboltus, Вы писали:

O>
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] вычисление средних значений векторов
От: Beam Россия  
Дата: 31.03.09 19:09
Оценка: 27 (5)
Здравствуйте, 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]


В итоге:
genFile 500 500 "small.txt" ~ 1.5 Мб
genFile 2000 2000 "big.txt" ~ 27.5 Мб

Т.к. мы часто будем работать с массивами хранящимися в файлах напишем:
-- читает двумерный массив из файла
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 truncate
  where
    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). Но что еще сделать, я не знаю Будем надеяться, что этой скорости будет достаточно. Ведь самое главное что теперь есть:
fun1 = ...
fun2 = ...
fun3 = ...

process inFile outFile (fun1 . fun2 . fun3)

Все, забыли про файлы! Акцентируем внимание на обработке.

Ну и еще.
-- Функцию 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 Россия  
Дата: 31.03.09 19:22
Оценка:
Здравствуйте, 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  
Дата: 01.04.09 19:06
Оценка:
Здравствуйте, Beam, Вы писали:

Ну круто! Не отходите далеко, я проверю.

P.S. А разве стандартная функция words не заменяет самописную split?
Re[3]: [haskell] вычисление средних значений векторов
От: Beam Россия  
Дата: 03.04.09 12:31
Оценка:
Здравствуйте, Oboltus, Вы писали:

O>P.S. А разве стандартная функция words не заменяет самописную split?

Да уж. В данном контексте заменяет. Что-то я не подумал про нее:
split ' ' == words
intercalate " " = unwords
Best regards, Буравчик
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.