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

Lazin

Дата 24.1.2009, 16:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: нет
Всего: 154

написал небольшую програмку на 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

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Lazin

Дата 24.1.2009, 23:39 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: нет
Всего: 154

с помощью 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")

Добавлено через 13 минут и 57 секунд
так-же смущат то, что компилятор(GHC) не может сам распознать возможность бесконечной рекурсии, либо не полный pattern matching, хотя в остальном все классно =)
еще подумалось, что такой код можно очень легко и практически полностью покрыть тестами

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Lazin

Дата 25.1.2009, 00:43 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: нет
Всего: 154

люди, вы где?

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Void

Дата 25.1.2009, 08:51 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Lazin, не торопись smile

Я лично Haskell читать могу, но вот сходу выцепить узкое место в программе

Цитата(Lazin @ 25.1.2009, 01:39

)

не может сам распознать возможность бесконечной рекурсии

Насколько я понимаю, без возможности бесконечной рекурсии чистый ФЯ будет не Тьюринг-полным. С трудом представляю себе статический анализ, способный определить возможность зацикливания.

Цитата(Lazin @ 25.1.2009, 01:39

)

как-то оно не очень эффективно работает с памятью...

Эффективность по памяти — не самая сильная сторона Haskell.
Возможно, ты решаешь задачу слишком энергично.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Lazin

Дата 25.1.2009, 11:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: нет
Всего: 154

Цитата(Void @ 25.1.2009, 08:51

)

но вот сходу выцепить узкое место в программе

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

Цитата(Void @ 25.1.2009, 08:51

)

Эффективность по памяти — не самая сильная сторона Haskell.

вот это уже удручает, я правильно понимаю, что это из-за того, что приходится создавать каждый раз новых объект вместо того что-бы изменить старый?

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Void

Дата 25.1.2009, 11:26 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(Lazin @ 25.1.2009, 13:08

)

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

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Lazin

Дата 25.1.2009, 11:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: нет
Всего: 154

а с обычными массивами там можно работать, или только с ByteString?

Добавлено через 1 минуту и 21 секунду
видимо Haskell для работы не очень подходит, слишком мало контроля над тем как программа всебя ведет..

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Lazin

Дата 25.1.2009, 11:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: нет
Всего: 154

Вообще, мне подумалось, что было-бы неплохо начать использовать в работе какой-нибудь ФП язык, со строгой статической типизацией, из 3х вариантов - Clean, Haskell, OCaml я выбрал второй, видимо надо будет попробовать третий =)

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Void

Дата 25.1.2009, 12:06 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(Lazin @ 25.1.2009, 13:31

)

а с обычными массивами там можно работать, или только с ByteString?

http://haskell.org/haskellwiki/Arrays

А с этой задачей попробуй на RSDN.decl, там как раз недавно обширные обсуждения по поводу Haskell in the real world были. Опытные собаководы покажут, как красиво сделать smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Lazin

Дата 25.1.2009, 12:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: нет
Всего: 154

А насколько OCaml ближе к реальному миру, чим Haskell? smile

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Void

Дата 25.1.2009, 12:18 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(Lazin @ 25.1.2009, 13:51

)

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

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

Цитата(Lazin @ 25.1.2009, 14:16

)

А насколько OCaml ближе к реальному миру, чим Haskell? smile

Я бы не сказал, что Haskell дальше или OCaml ближе. Просто у Haskell порог вхождения, пожалуй, выше. Haskell синтаксически и концептуально красивее, OCaml может быть шустрее, а про библиотеки я уже сказал.

Это сообщение отредактировал(а) Void - 25.1.2009, 12:22

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Lazin

Дата 25.1.2009, 13:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: нет
Всего: 154

Цитата(Void @ 25.1.2009, 12:18

)

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

Под строгостью я имел ввиду строгую типизацию, то-есть что-бы int нельзя было привести к float неявно, а не строгость как альтернативу ленивости.
Но пока я не могу контролировать поведение программы на Haskell и это обламывает. Мне даже сложно отладочную печать вставить в код =)

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Void

Дата 25.1.2009, 13:09 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(Lazin @ 25.1.2009, 15:07

)

Под строгостью я имел ввиду строгую типизацию, то-есть что-бы int нельзя было привести к float неявно, а не строгость как альтернативу ленивости.

Я понял, просто выделил именно разницу строгий—ленивый.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Функциональные языки: общие вопросы \| Следующая тема »