В постоянном стремлении эффективно поиграть с битами (например, см. Этот SO вопрос ) новейшей задачей является эффективная потоковая передача и потребление битов.
В качестве первой простой задачи я выбираю поиск самой длинной последовательности идентичных битов в потоке битов, генерируемом /dev/urandom. Типичное заклинание будет head -c 1000000 </dev/urandom | my-exe. Фактическая цель состоит в том, чтобы передавать биты и декодировать гамма-код Элиаса , например, то есть коды, которые не являются кусками байтов или их кратными числами.
Для таких кодов переменной длины хорошо иметь язык take, takeWhile, group и т. Д. Для манипулирования списком. Поскольку BitStream.take фактически потребляет часть бистрима, возможно, в игру вступит какая-то монада.
Очевидной отправной точкой является ленивая строка из Data.ByteString.Lazy.
A. Подсчет байтов
Эта очень простая программа на Haskell работает наравне с программой на C, как и следовало ожидать.
import qualified Data.ByteString.Lazy as BSL
main :: IO ()
main = do
bs <- BSL.getContents
print $ BSL.length bs
B. Добавление байтов
Как только я начну использовать unpack, все должно стать хуже.
main = do
bs <- BSL.getContents
print $ sum $ BSL.unpack bs
Удивительно, но Haskell и C показывают почти одинаковую производительность.
C. Самая длинная последовательность идентичных битов
В качестве первой нетривиальной задачи можно найти самую длинную последовательность идентичных битов, например:
module Main where
import Data.Bits (shiftR, (.&.))
import qualified Data.ByteString.Lazy as BSL
import Data.List (group)
import Data.Word8 (Word8)
splitByte :: Word8 -> [Bool]
splitByte w = Prelude.map (\i-> (w `shiftR` i) .&. 1 == 1) [0..7]
bitStream :: BSL.ByteString -> [Bool]
bitStream bs = concat $ map splitByte (BSL.unpack bs)
main :: IO ()
main = do
bs <- BSL.getContents
print $ maximum $ length <$> (group $ bitStream bs)
Ленивая строка байтов преобразуется в список [Word8], а затем, используя сдвиги, каждая Word разбивается на биты, в результате получается список [Bool]. Этот список списков затем сводится с помощью concat. Получив (ленивый) список Bool, используйте group, чтобы разбить список на последовательности идентичных битов, а затем отобразить length поверх него. Наконец maximum дает желаемый результат. Довольно просто, но не очень быстро:
# C
real 0m0.606s
# Haskell
real 0m6.062s
Эта наивная реализация на один порядок медленнее.
Профилирование показывает, что выделяется довольно много памяти (около 3 ГБ для анализа 1 МБ входных данных). Тем не менее, значительных утечек в космосе не наблюдается.
Отсюда я начинаю ковыряться:
- Существует
bitstream пакет , который обещает " быстрые, упакованные, строгие потоки битов (то есть список Bools) с полуавтоматическим слиянием потоков. ". К сожалению, он не соответствует текущей версии vector, подробности см. здесь .
- Далее я расследую
streaming. Я не совсем понимаю, зачем мне нужна «эффективная» потоковая передача, которая приводит в действие некоторую монаду - по крайней мере, пока я не начну с обратной задачи, то есть кодирования и записи битовых потоков в файл.
- Как насчет
fold -ing над ByteString? Я должен был бы ввести состояние, чтобы отслеживать потребляемые биты. Это не совсем приятный take, takeWhile, group и т. Д. Язык, который желателен.
А теперь я не совсем уверен, куда идти.
Обновление
Я выяснил, как это сделать с streaming и streaming-bytestring. Я, вероятно, не делаю это правильно, потому что результат катастрофически плох.
import Data.Bits (shiftR, (.&.))
import qualified Data.ByteString.Streaming as BSS
import Data.Word8 (Word8)
import qualified Streaming as S
import Streaming.Prelude (Of, Stream)
import qualified Streaming.Prelude as S
splitByte :: Word8 -> [Bool]
splitByte w = (\i-> (w `shiftR` i) .&. 1 == 1) <$> [0..7]
bitStream :: Monad m => Stream (Of Word8) m () -> Stream (Of Bool) m ()
bitStream s = S.concat $ S.map splitByte s
main :: IO ()
main = do
let bs = BSS.unpack BSS.getContents :: Stream (Of Word8) IO ()
gs = S.group $ bitStream bs :: Stream (Stream (Of Bool) IO) IO ()
maxLen <- S.maximum $ S.mapped S.length gs
print $ S.fst' maxLen
Это проверит ваше терпение с чем-либо, кроме нескольких тысяч байтов ввода от стандартного ввода. Профилировщик говорит, что тратит безумное количество времени (квадратичное по размеру ввода) в Streaming.Internal.>>=.loop и Data.Functor.Of.fmap. Я не совсем уверен, что это за первый, но fmap указывает (?), Что жонглирование этих Of a b не приносит нам никакой пользы, и потому что мы в монаде IO, это не может быть оптимизирован прочь.
У меня также есть потоковый эквивалент байтового сумматора здесь: SumBytesStream.hs, что немного медленнее, чем простая реализация lazy ByteString, но все еще прилично. Поскольку streaming-bytestring является , объявленным как " bytestring io сделано правильно ", я ожидал лучшего. Я, вероятно, не делаю это правильно, тогда.
В любом случае, все эти битовые вычисления не должны происходить в монаде IO. Но BSS.getContents заставляет меня в IO монаду, потому что getContents :: MonadIO m => ByteString m (), и нет никакого выхода.
Обновление 2
Следуя совету @dfeuer, я использовал пакет streaming на master @ HEAD. Вот результат.
longest-seq-c 0m0.747s (C)
longest-seq 0m8.190s (Haskell ByteString)
longest-seq-stream 0m13.946s (Haskell streaming-bytestring)
Проблема O (n ^ 2) в Streaming.concat решена, но мы все еще не приближаемся к тесту C.
Обновление 3
Решение Cirdec обеспечивает производительность наравне с C. Используемая конструкция называется «Списки, закодированные Церковью», см. Этот SO ответ или Вики на Haskell для ранг-N типов .
Исходные файлы:
Все исходные файлы можно найти на github . У Makefile есть все различные цели для проведения экспериментов и профилирования. По умолчанию make будет просто собирать все (сначала создайте каталог bin/!), А затем make time определит время для исполняемых файлов longest-seq. Исполняемые файлы C добавляются -c, чтобы различать их.