[Haskell] Проверки целостности лог файлов

 
0
 
Functional languages
ava
Lazin | 24.01.2009, 16:13
написал небольшую програмку на Haskell-e для проверки целостности лог файлов, в общем задание такое, есть файл вида
Цитата


14:18:59.671    1614  17A8 m: 0 l: 000000

14:18:59.671    1614  17A8 m: 1 l: 000000

14:18:59.671    1614  17A8 m: 2 l: 000000

14:18:59.671    1614  17A8 m: 3 l: 000000

14:18:59.671    1614  17A8 m: 4 l: 000000

14:18:59.671    1614  17A8 m: 5 l: 000000

14:18:59.671    1614  17A8 m: 6 l: 000000

14:18:59.671    1614  17A8 m: 9 l: 000000

14:18:59.671    1614  17A8 m: 8 l: 000000

14:18:59.671    1614  17A8 m: 7 l: 000000


в котором записи идут болшую часть времени по порядку но могут быть перемешаны, программа должна проверять, есть ли среди них пропщеные или повторяющиеся ( номера записей идут после m:  ), причем запись может быть перемещены на несколько тысяч строк вперед или назад, ну и файлы оч. большие, все в память грузить не вариант
вот что у меня получилось:

import qualified Data.ByteString.Lazy.Char8 as L
import Control.Exception
import Control.Monad
import Numeric
import Data.List



-- log entery data type
data LogEntry = LogEntry { process :: Int
                         , thread  :: Int
                         , number  :: Int
                         }


instance Eq LogEntry where
    (LogEntry _ _ x) == (LogEntry _ _ y) = x == y
    (LogEntry _ _ x) /= (LogEntry _ _ y) = x /= y


instance Ord LogEntry where
    (LogEntry _ _ x) <= (LogEntry _ _ y) = x <= y
    (LogEntry _ _ x) >= (LogEntry _ _ y) = x >= y


instance Show LogEntry where
    show (LogEntry p t n) = "number: " ++ show p ++ " thread: " ++ show t ++ " number: " ++ show n


instance Read LogEntry where
    readsPrec k line = case tokens of
                            (_:p:t:_:n:xs) -> [(LogEntry (parce' readHex p) (parce' readHex t) (parce' readDec n), "")]
                            _:_ -> undefined
                       where tokens = words line
                             parce' fn x = case out of
                                                [(x,_)] -> x
                                                [] -> undefined
                                                where out = fn x


parseFile :: [L.ByteString] -> [LogEntry]
parseFile input = map (read . L.unpack) input



processLog :: [LogEntry] -> LogEntry -> [LogEntry] -> Bool
processLog [] _ [] = True
processLog [] _ _ = False
processLog (x:xs) top []
    | npred == ntop = processLog xs x []
    | otherwise = processLog xs top [x]
    where npred = number x - 1
          ntop  = number top
processLog (x:xs) top unord = processLog xs ntop ys
    where update_top (x:xs) top = if (number x) - 1 == number top
                                  then update_top xs x
                                  else (x:xs, top)
          update_top [] top =     ([], top)
          sorted = sort (x:unord)
          (ys, ntop) = update_top sorted top



main = do
        content <- L.readFile "test.log"
        let lines = L.lines content
        mapM (putStrLn . show) (parseFile lines)
        let (x:xs) = parseFile lines
        putStrLn (if processLog xs x [] then "OK" else "Fail")

проблема в том, что это работает слишком медленно, аналогичный код написаный на питоне работает намного быстрее smile 
что я делаю не так, просто это моя первая программа на Haskell, много чего я еще не понимаю smile 
Comments (12)
ava
Lazin | 24.01.2009, 23:39 #
с помощью Data.Set избавился от сортировки списка, работает шустро, но, кушает много памяти, к примеру, если на вход подать файл размером 40Мб, в котором будет отсутствовать строка в самом начале, то оно выжрет примерно 300Мб оперативки, что немного смущает, как-то оно не очень эффективно работает с памятью...

import qualified Data.ByteString.Lazy.Char8 as L
import Control.Exception
import Control.Monad
import Numeric
import Data.List
import qualified Data.Set as Set



-- log entery data type
data LogEntry = LogEntry { process :: Int
                         , thread  :: Int
                         , number  :: Int
                         }


instance Eq LogEntry where
    (LogEntry _ _ x) == (LogEntry _ _ y) = x == y
    (LogEntry _ _ x) /= (LogEntry _ _ y) = x /= y


instance Ord LogEntry where
    (LogEntry _ _ x) <= (LogEntry _ _ y) = x <= y
    (LogEntry _ _ x) >= (LogEntry _ _ y) = x >= y


instance Show LogEntry where
    show (LogEntry p t n) = "number: " ++ show p ++ " thread: " ++ show t ++ " number: " ++ show n


instance Read LogEntry where
    readsPrec k line = case tokens of
                            (_:p:t:_:n:xs) -> [(LogEntry (parce' readHex p) (parce' readHex t) (parce' readDec n), "")]
                            _:_ -> undefined
                       where tokens = words line
                             parce' fn x = case out of
                                                [(x,_)] -> x
                                                [] -> undefined
                                                where out = fn x

nextEntry (LogEntry x y z) = LogEntry x y (z + 1)
prevEntry (LogEntry x y z) = LogEntry x y (z - 1)

parseFile :: [L.ByteString] -> [LogEntry]
parseFile input = map (read . L.unpack) input



processLog :: [LogEntry] -> LogEntry -> (Set.Set LogEntry) -> Bool
processLog [] _ set = Set.null set
processLog (x:xs) top unord =
    if prevEntry x == top
    then processLog xs x unord
    else processLog xs ntop ys
        where update_top set top =    
                        if Set.member x set
                        then update_top (Set.delete x set) x
                        else (set, top)
                            where x = nextEntry top
              (ys, ntop) = update_top (Set.insert x unord) top



main = do
        content <- L.readFile "test.log"
        let lines = L.lines content
        -- mapM (putStrLn . show) (parseFile lines)
        let (x:xs) = parseFile lines
        putStrLn (if processLog xs x Set.empty then "OK" else "Fail")



added later:
так-же смущат то, что компилятор(GHC) не может сам распознать возможность бесконечной рекурсии, либо не полный pattern matching, хотя в остальном все классно =)
еще подумалось, что такой код можно очень легко и практически полностью покрыть тестами
ava
Lazin | 25.01.2009, 00:43 #
люди, вы где?
ava
Void | 25.01.2009, 08:51 #
Lazin, не торопись smile Я лично Haskell читать могу, но вот сходу выцепить узкое место в программе smile
Цитата (Lazin @  25.1.2009,  01:39 findReferencedText)
не может сам распознать возможность бесконечной рекурсии

Насколько я понимаю, без возможности бесконечной рекурсии чистый ФЯ будет не Тьюринг-полным. С трудом представляю себе статический анализ, способный определить возможность зацикливания.
Цитата (Lazin @  25.1.2009,  01:39 findReferencedText)
как-то оно не очень эффективно работает с памятью...

Эффективность по памяти — не самая сильная сторона Haskell.
Возможно, ты решаешь задачу слишком энергично.
ava
Lazin | 25.01.2009, 11:08 #
Цитата (Void @  25.1.2009,  08:51 findReferencedText)
но вот сходу выцепить узкое место в программе

узкое место я уже нашел - дело было в алгоритме, избавился от постоянной сортировки постоянно увеличивающегося в размере списка и все заработало быстро

Цитата (Void @  25.1.2009,  08:51 findReferencedText)
Эффективность по памяти — не самая сильная сторона Haskell.

вот это уже удручает, я правильно понимаю, что это из-за того, что приходится создавать каждый раз новых объект вместо того что-бы изменить старый?
ava
Void | 25.01.2009, 11:26 #
Цитата (Lazin @  25.1.2009,  13:08 findReferencedText)
вот это уже удручает, я правильно понимаю, что это из-за того, что приходится создавать каждый раз новых объект вместо того что-бы изменить старый? 

Это как раз не так страшно, ведь зачастую новый объект разделяет со старым большую часть своей структуры.
Кроме этого, thunk может быть больше, чем значение, которое он вычислит.
Особенности представления строк: с [Char] удобно работать, но представь, сколько оно занимает.
Впрочем, думаю, оптимизировать эту задачу по памяти можно.
ava
Lazin | 25.01.2009, 11:31 #
а с обычными массивами там можно работать, или только с ByteString?

added later:
видимо Haskell для работы не очень подходит, слишком мало контроля над тем как программа всебя ведет..
ava
Lazin | 25.01.2009, 11:51 #
Вообще, мне подумалось, что было-бы неплохо начать использовать в работе какой-нибудь ФП язык, со строгой статической типизацией, из 3х вариантов - Clean, Haskell, OCaml я выбрал второй, видимо надо будет попробовать третий =)
ava
Void | 25.01.2009, 12:06 #
Цитата (Lazin @  25.1.2009,  13:31 findReferencedText)
а с обычными массивами там можно работать, или только с ByteString?

http://haskell.org/haskellwiki/Arrays

А с этой задачей попробуй на RSDN.decl, там как раз недавно обширные обсуждения по поводу Haskell in the real world были. Опытные собаководы покажут, как красиво сделать smile
ava
Lazin | 25.01.2009, 12:16 #
А насколько OCaml ближе к реальному миру, чим Haskell? smile 
ava
Void | 25.01.2009, 12:18 #
Цитата (Lazin @  25.1.2009,  13:51 findReferencedText)
Вообще, мне подумалось, что было-бы неплохо начать использовать в работе какой-нибудь ФП язык, со строгой статической типизацией, из 3х вариантов - Clean, Haskell, OCaml я выбрал второй, видимо надо будет попробовать третий =)


OCaml даже после короткого знакомства с Haskell имеет все шансы показаться корявым, хотя бы из-за отсутствия type classes. Стандартная библиотека опять же скудновата по сравнению с GHC, на ExtLib или batteries придётся смотреть довольно скоро.

Но контролировать поведение программы легче, да. По крайней мере для человека, не освоившегося с чистым ленивым языком. Посмотреть, в общем, стоит: из строгих ФЯ со статической типизацией OCaml по любому безальтернативен. (забыл про F#, Nemerle).

Цитата (Lazin @  25.1.2009,  14:16 findReferencedText)
А насколько OCaml ближе к реальному миру, чим Haskell? smile  

Я бы не сказал, что Haskell дальше или OCaml ближе. Просто у Haskell порог вхождения, пожалуй, выше. Haskell синтаксически и концептуально красивее, OCaml может быть шустрее, а про библиотеки я уже сказал.
ava
Lazin | 25.01.2009, 13:07 #
Цитата (Void @  25.1.2009,  12:18 findReferencedText)
Посмотреть, в общем, стоит: из строгих ФЯ со статической типизацией OCaml по любому безальтернативен. (забыл про F#, Nemerle).

Под строгостью я имел ввиду строгую типизацию, то-есть что-бы int нельзя было привести к float неявно, а не строгость как альтернативу ленивости.
Но пока я не могу контролировать поведение программы на Haskell и это обламывает. Мне даже сложно отладочную печать вставить в код =)
ava
Void | 25.01.2009, 13:09 #
Цитата (Lazin @  25.1.2009,  15:07 findReferencedText)
Под строгостью я имел ввиду строгую типизацию, то-есть что-бы int нельзя было привести к float неявно, а не строгость как альтернативу ленивости.

Я понял, просто выделил именно разницу строгий—ленивый.
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  Void   Lazin
advanced
Submit