Оптимизация на Haskell функции, которая ищет терминатор байтов - PullRequest
Новая
       24

Оптимизация на Haskell функции, которая ищет терминатор байтов

0 голосов
/ 20 марта 2010

Профилирование некоторого кода показало, что около 65% времени я был внутри следующего кода.

Что он делает, так это использует монаду Data.Binary.Get, чтобы пройти через строку байтов, ищущую терминатор. Если он обнаруживает 0xff, он проверяет, равен ли следующий байт 0x00. Если это так, он сбрасывает 0x00 и продолжает. Если это не 0x00, тогда он сбрасывает оба байта, и результирующий список байтов преобразуется в строку байтов и возвращается.

Есть ли очевидные способы оптимизировать это? Я не вижу этого. 

parseECS = f [] False
    where
    f acc ff = do
        b <- getWord8
        if ff
            then if b == 0x00
                then f (0xff:acc) False
                else return $ L.pack (reverse acc)
            else if b == 0xff
                then f acc True
                else f (b:acc) False

Ответы [ 2 ]

1 голос
/ 20 марта 2010

Исправление ошибок

Кажется, здесь может быть ошибка. Исключение возникает, если вы достигаете конца потока байтов до 0xff, а не 0x00 последовательности. Вот модифицированная версия вашей функции: 

parseECS :: Get L.ByteString
parseECS = f [] False
  where
    f acc ff = do
      noMore <- isEmpty
      if noMore
         then return $ L.pack (reverse acc)
         else do
           b <- getWord8
           if ff
              then
                if b == 0x00
                   then f (0xff:acc) False
                   else return $ L.pack (reverse acc)
              else
                if b == 0xff
                   then f acc True
                   else f (b:acc) False

Оптимизация

Я не выполнял профилирование, но эта функция, вероятно, будет быстрее. Реверсирование длинных списков стоит дорого. Я не уверен, насколько ленива getRemainingLazyByteString. Если он слишком строг, это, вероятно, не сработает для вас. 

parseECS2 :: Get L.ByteString
parseECS2 = do
    wx <- liftM L.unpack $ getRemainingLazyByteString
    return . L.pack . go $ wx
  where
    go []             = []
    go (0xff:0x00:wx) = 0xff : go wx
    go (0xff:_)      = []
    go (w:wx)         = w : go wx
0 голосов
/ 21 марта 2010

Если проблема в «обратном направлении», вы можете использовать «lookAhead» для сканирования позиции, а затем вернуться и перестроить новую строку 

parseECS2 :: Get L.ByteString
parseECS2 = do
    let nextWord8 = do
            noMore <- isEmpty
            if noMore then return Nothing
                      else liftM Just getWord8

    let scanChunk !n = do
            b <- nextWord8
            case b of
                Just 0xff -> return (Right (n+1))
                Just _ -> scanChunk (n+1)
                Nothing -> return (Left n)

    let readChunks = do
            c <- lookAhead (scanChunk 0)
            case c of
                Left n -> getLazyByteString n >>= \blk -> return [blk]
                Right n -> do
                    blk <- getLazyByteString n
                    b <- lookAhead nextWord8
                    case b of
                        Just 0x00 -> skip 1 >> liftM (blk:) readChunks
                        _ -> return [L.init blk]

    liftM (foldr L.append L.empty) readChunks
...