Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Оптимизация программы
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Q0i Q0i вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 3
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 30.07.2012
По умолчанию Оптимизация программы - 30.07.2012, 19:52

Здравствуйте
Написал свою первую программу на HASKELL.
Возникли вопросы, на которые могут помочь специалисты с форума.
Программа тратит памяти больше, чем мне кажется разумным.
Кроме того выполняется долго.
Можно ли как-то оптимизировать программу?

Итак про саму программу.
Программа открывает для чтения текстовый файл FileName.txt (~100 Мб), и просматривает в нем все строки.
Некоторые строки начинаются с символов "id=<НатуральноеЧисло>".
В абсолютном большинстве случаев при переходе от строки указанного вида к следующей строке указанного вида значение id просто увеличивается на 1.
Иногда монотонность и непрерывность значений id нарушается.
Некоторые значения id могут встречаться больше одного раза, некоторые значения id могут оказаться пропущены.
Нужно найти минимальное min и максимальное max значения id встречающихся в файле и вывести на экран все значения id из интервала [min, max] которые не встретились в файле.

Вот сама программа, надеюсь все понятно:
haskell Код:
-- Использование ленивых версий Data.ByteString.Lazy*
-- или обычных строк String ухудшает производительность
-- программы и повышает расход памяти.
import qualified Data.ByteString.Char8 as B

import Data.List
import System.IO
import Text.Regex.Posix
 
main = do
   -- открываем файл на чтение
   data <- B.readFile "FileName.txt"

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

   -- Использование ленивой foldl ухудшает производительность
   -- программы и повышает расход памяти.
   let ( flgFirst, cmin, cmax, miss ) = foldl' f ( True, 0, 0, [] ) $ B.lines data

   -- печатаем пропущенные значения
   mapM print miss




-- В аккумуляторе (tuple) первое значение - флаг,
-- равный True при чтении первой строки с id=...
-- и равный False при чтении всех последующих строк

-- Второе и третье значения в tuple - минимальное и
-- максимальное встретившееся id.

-- Четвертое значение в tuple - массив пропущенных id.

f :: (Bool,Int,Int,[Int]) -> B.ByteString -> (Bool,Int,Int,[Int])
f acc line =

   -- Проверяем, начинается ли строка с id=<НатуральноеЧисло>
   let parc = line =~ "^id=([0-9]+)" :: [[B.ByteString]]
   in
      if parc == []
      then
         acc  -- Строка не подходит под шаблон, аккумулятор не меняем
      else
         let [[ _, id ]] = parc
            Just ( num, _ ) = B.readInt id
            ( flgFirst, cmin, cmax, miss ) = acc
         in
            if flgFirst
            then
               -- Читаем первую строку с id=num.
               -- Прочитанное значение сохраняем в max и в min.
               -- Массив пропущенных id берем пустым.
               -- Здесь и далее флаг первой строки выставляем всегда в False.
               ( False, num, num, [] )  
            else
               -- Все, что ниже этой строки, думаю, комментариев не требует...
               if ( num == cmax + 1 )
               then
                  ( False, cmin, num, miss )
               else
                  if ( num > cmax )
                  then
                     ( False, cmin, num, [cmax+1..num-1] ++ miss )
                  else
                     if ( num < cmin )
                     then
                        ( False, num, cmax, [num+1..cmin-1] ++ miss )
                     else
                        ( False, cmin, cmax, delete num miss )

Данная версия программы требует памяти в 1,5 раза больше чем объем входного файла.
Как можно улучшить программу?
Хотелось бы пообщаться с опытными людьми на эту тему...
Ответить с цитированием
  (#2 (permalink)) Старый
korvin korvin вне форума
Member
 
Аватар для korvin
 
Сообщений: 337
Сказал(а) спасибо: 1
Поблагодарили 15 раз(а) в 15 сообщениях
Регистрация: 25.01.2010
По умолчанию 02.08.2012, 11:09

Не знаток Haskell'а, но может попробовать добавить еще немного строгости с помощью BangPatterns? Вот на хабре в статье, в конце они упоминаются.

И нагромождение if'ов лучше заменить guard'ами (вряд ли сказывается на производительности, но читается намного приятней).

Кроме того, возможно:
1) вместо накопления miss-элемнтов как ты это делаешь, лучше сохранить элементы, которые присутствуют, а потом отфильтровать список [cmin..cmax];
2) вместо проверки для каждого элемента флага first, лучше просто первый подходящий элемент обработать "особым образом", а остальные -- обычным;
3) проверка num == cmax + 1 лишняя.

Итого у меня получился такой код (только без BangPatterns):

haskell Код:
import qualified Data.ByteString.Char8 as B

import Data.List
import System.IO
import Text.Regex.Posix

type Str = B.ByteString
type Acc = (Int, Int, [Int])

main :: IO ()
main = B.readFile "FileName.txt" >>= printResults . processFile

processFile :: Str -> Maybe Acc
processFile text = case findFirstId $ B.lines text of
    Nothing              -> Nothing
    Just (firstId, rest) -> Just (cmin, cmax, miss) where
        (cmin, cmax, exist) = foldl' f (firstId, firstId, []) rest
        miss = filter (`notElem` exist) [cmin..cmax]

printResults :: Maybe Acc -> IO ()
printResults Nothing = return ()
printResults (Just (cmin, cmax, miss)) = do
    print (cmin, cmax)
    mapM_ print miss

findFirstId :: [Str] -> Maybe (Int, [Str])
findFirstId [] = Nothing
findFirstId (x:xs) = case parseId x of
    Nothing -> findFirstId xs
    Just id -> Just (id, xs)

parseId :: Str -> Maybe Int
parseId line = case (line =~ "^id=([0-9]+)" :: [[Str]]) of
    []        -> Nothing
    [[_, id]] -> getId (B.readInt id) where
        getId  Nothing      = Nothing
        getId (Just (n, _)) = Just n

f :: Acc -> Str -> Acc
f acc line = case parseId line of
    Nothing -> acc
    Just id -> f' acc id

f' :: Acc -> Int -> Acc
f' (cmin, cmax, exist) id
    | id >  cmax  =  (cmin, id,   cmax:exist)
    | id <  cmin  =  (id,   cmax, cmin:exist)
    | otherwise   =  (cmin, cmax,   id:exist)

Компилируется, но результаты не проверял, т.к. лень составлять тестовые входные данные =)


Object-oriented design is the roman numerals of computing. — Rob Pike

Последний раз редактировалось korvin; 02.08.2012 в 11:18
Ответить с цитированием
Пользователь сказал cпасибо:
Q0i (03.08.2012)
  (#3 (permalink)) Старый
Q0i Q0i вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 3
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 30.07.2012
По умолчанию 03.08.2012, 01:59

korvin, спасибо за ответ!


После компиляции с ключом оптимизации -O или -O2 скорость увеличилась, расход памяти уменьшился.
Скорость пока кажется приемлемой, во всяком случае не приходится долго ждать.
Производительность с аналогичной программой на C/C++ пока не сравнивал, но надо бы сравнить, интересно где в Haskell могут быть подводные камни и как с ними бороться...

Расход памяти уменьшается использованием ленивых Data.ByteString.Lazy.Char8.
Время выполнения программы с ленивыми строками несколько увеличивается, зато не надо хранить в памяти огромные файлы целиком.



Цитата:
Сообщение от korvin Посмотреть сообщение
Кроме того, возможно:
1) вместо накопления miss-элемнтов как ты это делаешь, лучше сохранить элементы, которые присутствуют, а потом отфильтровать список [cmin..cmax];
Не согласен.
Эта строчка будет выполняться очень долго:
miss = filter (`notElem` exist) [cmin..cmax]
Представьте себе список [cmin..cmax] из, например, N = 1 000 000 элементов, и список exist сравнимой длины.
Методом простого перебора filter выполнит порядка N^2 сравнений...
Число пропусков гораздо меньше N, так что лучше иметь дело именно с пропусками.


Цитата:
Сообщение от korvin Посмотреть сообщение
2) вместо проверки для каждого элемента флага first, лучше просто первый подходящий элемент обработать "особым образом", а остальные -- обычным;
Согласен.
Просто я не придумал как это сделать, Ваш вариант мне нравится.
Правда, на производительность это улучшение практически не влияет, но с идеологической точки лучше не хранить лишний флаг и не проверять его значение на каждой итерации.
Интересно, можно как-то избавиться от этого флага не вводя рекурсию?
В Вашем варианте стек рекурсивных вызовов findFirstId растет.
Это не проблема, конечно, но без заполнения стека решение было бы красивее.


Цитата:
Сообщение от korvin Посмотреть сообщение
3) проверка num == cmax + 1 лишняя.
Согласен.
Изначально я написал эту ветку, чтобы наиболее частый случай выполнялся в fold' максимально быстро.
Однако, согласно замерам, удаление этой ветки (фактически, включение её в ветку num > cmax) почти не сказывается на производительности.
Так что ради простоты можно эту ветку удалить.


Цитата:
Сообщение от korvin Посмотреть сообщение
Не знаток Haskell'а, но может попробовать добавить еще немного строгости с помощью BangPatterns?
Спасибо за подсказку.
Впрочем, в данной программе BangPatterns на скорость почти не влияет.
Видимо, это связано со следующими особенностями задачи и алгоритма:
1) список miss очень короткий,
2) для выполнения итерации fold' уже нужно знать значения всех остальных полей в аккумуляторе, чтобы выбрать ветку для исполнения.
То есть в данной конкретной задаче BangPatterns не критичен для производительности.

Последний раз редактировалось Q0i; 03.08.2012 в 02:51
Ответить с цитированием
  (#4 (permalink)) Старый
korvin korvin вне форума
Member
 
Аватар для korvin
 
Сообщений: 337
Сказал(а) спасибо: 1
Поблагодарили 15 раз(а) в 15 сообщениях
Регистрация: 25.01.2010
По умолчанию 03.08.2012, 09:20

Цитата:
Сообщение от Q0i Посмотреть сообщение
Просто я не придумал как это сделать, Ваш вариант мне нравится.
Правда, на производительность это улучшение практически не влияет, но с идеологической точки лучше не хранить лишний флаг и не проверять его значение на каждой итерации.
Интересно, можно как-то избавиться от этого флага не вводя рекурсию?
В Вашем варианте стек рекурсивных вызовов findFirstId растет.
Это не проблема, конечно, но без заполнения стека решение было бы красивее.
Это из-за ленивости, сделай findFirstId энергичной и стек не будет расти.


Object-oriented design is the roman numerals of computing. — Rob Pike
Ответить с цитированием
Пользователь сказал cпасибо:
Q0i (03.08.2012)
  (#5 (permalink)) Старый
korvin korvin вне форума
Member
 
Аватар для korvin
 
Сообщений: 337
Сказал(а) спасибо: 1
Поблагодарили 15 раз(а) в 15 сообщениях
Регистрация: 25.01.2010
По умолчанию 03.08.2012, 09:22

Вот здесь есть ссылки про хвостовую рекурсию и ленивость.


Object-oriented design is the roman numerals of computing. — Rob Pike

Последний раз редактировалось korvin; 03.08.2012 в 09:37
Ответить с цитированием
Пользователь сказал cпасибо:
Q0i (03.08.2012)
Ads.
  (#6 (permalink)) Старый
Mokujin Mokujin вне форума
Новичок
 
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.01.2014
По умолчанию 08.01.2014, 00:58

спасибо за ссылку

Последний раз редактировалось Mokujin; 08.01.2014 в 01:03
Ответить с цитированием
  (#7 (permalink)) Старый
beroal beroal вне форума
Member
 
Сообщений: 108
Сказал(а) спасибо: 3
Поблагодарили 4 раз(а) в 4 сообщениях
Регистрация: 13.12.2002
По умолчанию 08.01.2014, 22:49

Цитата:
Сообщение от Q0i Посмотреть сообщение
интересно где в Haskell могут быть подводные камни и как с ними бороться...
Изучайте компилятор и скомпилированный код.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимизация SSD Egorro Накопители 0 30.04.2012 13:07
Оптимизация DocRain Любые вопросы от новичков 6 31.03.2012 00:05
Оптимизация Jean-Esther Haskell 2 02.03.2012 00:16
оптимизация по скорости sin cos log e Gastly Вопросы начинающих программистов 5 16.12.2011 01:11
Оптимизация линейных участков программы Kama Prolog 18 20.03.2011 17:22
Оптимизация программы EiZeRR С/С++ 3 20.11.2006 19:44
Оптимизация на Builder 6 Романнист C++ Builder 1 18.03.2006 11:05
Оптимизация для Java eloiman Java 0 25.02.2004 14:27
Оптимизация кода BCB LaMiK C++ Builder 6 18.02.2004 18:26
Оптимизация Anonymous PHP 1 29.01.2004 14:37
Оптимизация PickTri Eliace Программирование графики 6 23.01.2004 21:11



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов