haskell очень медленно читает вектор пар из байтовой строки, как это сделать быстрее?

Я пытаюсь прочитать большой вектор пользовательского типа данных из двоичного файла. Я попытался использовать пример , приведенный здесь.

Проблема с примером кода в том, что он использует списки, а я хочу использовать векторы. Поэтому я адаптировал этот код, как показано ниже, но для чтения даже файла размером 1 МБ требуется очень много времени (больше минуты, после этого я сдался).

module Main where

import Data.Word
import qualified Data.ByteString.Lazy as BIN
import Data.Binary.Get
import qualified Data.Vector.Unboxed as Vec

main = do
  b <- BIN.readFile "dat.bin" -- about 1 MB size file
  let v = runGet getPairs (BIN.tail b) -- skip the first byte
  putStrLn $ show $ Vec.length v

getPair :: Get (Word8, Word8)
getPair = do
  price <- getWord8
  qty <- getWord8
  return (price, qty)

getPairs :: Get (Vec.Vector (Word8, Word8))
getPairs = do
 empty <- isEmpty
 if empty
   then return Vec.empty
   else do pair  <- getPair
           pairs <- getPairs
           return (Vec.cons pair pairs) -- is it slow because V.cons is O(n)?

Когда я попытался запустить его с ghc --make -O2 pairs.hs, я получил ошибку Stack space overflow: current size ...

Как эффективно считывать пары значений из байтовой строки в вектор?

Опять же, я хочу получить полный рабочий код, а не только указатели на сайт Haskell или RWH, или просто список имён функций / модулей.


performance vector haskell bytestring
person mntk123    schedule 19.09.2015    source источник
comment
вы не должны требовать полного рабочего решения в качестве ответа. SO - это сайт для обучения и понимания проблем, а не сервис краудсорсинга.   -  person Erik Kaplun    schedule 19.09.2015
comment
@ErikAllik Мне требуется полное рабочее решение в том же духе наименьшего полного рабочего примера. Также привожу минимальный рабочий пример. Еще одна причина - редкость рабочих примеров на сайтах Haskell. Проблемы, решения которых я прошу, обычно представляют собой очень маленькие фрагменты, которых вряд ли достаточно, чтобы обвинить меня в краудсорсинговом коде. SO великолепен, а документация на Haskell оставляет желать лучшего, поэтому мне нужно предъявить этот запрос. Прошу прощения, если это причинило кому-то боль / оскорбление или причинило чрезмерные страдания.   -  person mntk123    schedule 19.09.2015
comment
Да, это медленно, потому что V.cons равно O (n). Что вы ожидали? Миллион раз на миллион - это много! vector имеет отличную документацию. Обратите внимание, что документация по модулю Hackage обычно имеет оглавление в правом верхнем углу. Ознакомьтесь с разделом о построении векторов.   -  person dfeuer    schedule 19.09.2015
comment
@dfeuer Я ожидал, что это будет медленно. Но я не знал другого метода построения вектора путем постепенного добавления к нему элементов по мере чтения значений из байтовой строки. Что касается того, почему я задал вопрос: я не понимал ни одного другого метода, приведенного во взломе, который мог бы позволить мне постепенно построить вектор по своему желанию.   -  person mntk123    schedule 19.09.2015
comment
Ну, вы в основном не можете построить вектор, добавляя к нему постепенно! Они больше похожи на массивы C или C ++ или векторы FORTRAN, чем на гибкие объекты, которые некоторые другие среды называют векторами. Вы можете получить такие гибкие вещи в Haskell, если хотите; традиционный - Data.Sequence, но Эд Кмет в последнее время работает над некоторыми более быстрыми.   -  person dfeuer    schedule 19.09.2015

Ответы (2)


arrow_upward
2
arrow_downward

Вот пара примеров создания векторов из файлов. Они не самые эффективные, но оба запускаются в ghci всего за пару секунд.

module Main where

import qualified Data.ByteString.Lazy as BIN
import qualified Data.ByteString as BS
import qualified Data.Vector.Unboxed as Vec
import System.IO
import System.Posix

getFileSize :: String -> IO Int
getFileSize path = do
    stat <- getFileStatus path
    return (fromEnum $ fileSize stat)

readVector1 path = do
  size <- getFileSize path
  withBinaryFile path ReadMode $ \h -> do
    -- can also use: size <- hFileSize h
    let go _ = do bs <- BS.hGet h 2 
                  return (BS.index bs 0, BS.index bs 1)
    Vec.generateM (div size 2) go

pairs (a:b:rest) = (a,b) : pairs rest
pairs _          = []

readVector2 path = do
  contents <- BIN.readFile path
  -- unfoldr :: Unbox a => (b -> Maybe (a, b)) -> b -> Vector a
  let v = Vec.unfoldr go (pairs $ BIN.unpack contents)
        where go [] = Nothing
              go (p:ps) = Just (p, ps)
  return v

main = do
  v <- readVector1 "rand" -- large file
  print $ Vec.length v
  v <- readVector2 "rand"
  print $ Vec.length v

Третья альтернатива:

readVector3 path = do
  contents <- BS.readFile path
  let size = BS.length contents
      v = Vec.generate (div (fromIntegral size) 2) go
            where go i = let a = BS.index contents (2*i)
                             b = BS.index contents (2*i+1)
                         in (a,b)
  return v

Этот оказался самым быстрым из трех.

person ErikR    schedule 19.09.2015
comment
Обратите внимание, что использование size <- hFileSize h может быть более переносимым способом получения размера файла и не требует System.Posix - person ErikR; 19.09.2015
comment
функция readVector2 использует списки, а readVector1 - слишком много работы для ввода-вывода. - person mntk123; 19.09.2015
comment
Оба работают менее чем за секунду при компиляции на моей машине. Сколько времени это займет у вас? - person ErikR; 19.09.2015
comment
@ user5402: Вы немного изменили код - не могли бы вы объяснить, какие самые важные изменения были / были для повышения производительности? (Мне любопытно) - person Sam van Herwaarden; 19.09.2015
comment
Я думаю, что главный вывод заключается в том, что Vec.cons, вероятно, неэффективен. Сначала я подумал, что вы должны указать вектору необходимую длину - отсюда и первая версия. Однако unfold тоже неплохо работает. Основное различие между unfoldr и cons заключается в том, что unfoldr добавляется к вектору, что является более естественной операцией и, следовательно, я считаю более эффективной. cons, однако, я считаю, что он должен добавляться к вектору, что не является естественным способом роста векторов. - person ErikR; 19.09.2015
comment
Нет. Unfoldr просто использует традиционный трюк с удвоением массива для достижения O (1) амортизированного времени на snoc, даже если ему, возможно, придется удваивать размер массива несколько раз, каждый раз копируя все это целиком. - person dfeuer; 19.09.2015
comment
Да, но я считаю, что это на много лучше, чем использование cons. - person ErikR; 19.09.2015
comment
Ну да, конечно! Но вместо этого можно применить ту же технику, чтобы заполнить вектор сзади наперед. cons должен каждый раз копировать весь вектор. unfoldr экономит место для маневра, поэтому может позволить себе случайное копирование, не нарушая асимптотической границы. Prepend vs. append не имеет к этому никакого отношения. - person dfeuer; 19.09.2015
comment
@ user5402 Мне понравился и проголосовал за ваш ответ, но меня беспокоит часть ввода-вывода в readVector1. Если вы дадите код для чтения вектора, который просто принимает ByteString (вы можете найти его размер), а затем возвращает вектор, заполненный значениями, я его приму. Я изо всех сил пытаюсь получить этот тип кода, используя ваш код, но не могу удалить из него ввод-вывод. - person mntk123; 19.09.2015
comment
Хорошо - смотри это пространство. - person ErikR; 19.09.2015
comment
Взгляните на readVector3. Настройте формулы смещения 2*i, 2*i+1 и определение длины div size 2, чтобы учесть любые байты заголовка, которые вы хотите пропустить. - person ErikR; 19.09.2015
comment
@ user5402 Я принимаю этот ответ. Я не могу проголосовать за него более одного раза. Вы научили меня многому через ответ. - person mntk123; 19.09.2015

arrow_upward
2
arrow_downward

Вот альтернативный подход для загрузки вектора, который использует pipes и pipes-bytestring для потоковой передачи файла, а также _ 3_ из foldl для создания вектора:

{-# LANGUAGE PackageImports #-}
import Data.Functor (void)
import "pipes" Pipes
import qualified "pipes" Pipes.Prelude as P
import qualified "pipes-bytestring" Pipes.ByteString as B
import qualified "pipes-binary" Pipes.Binary as B
import qualified "vector" Data.Vector.Unboxed as V
import qualified "foldl" Control.Foldl as L
import "lens-family-core" Lens.Family (view)
import System.IO

main :: IO ()
main = do
    v <- withBinaryFile "somefile" ReadMode (\h ->
        -- for simplicity, errors are ignored with "void"
        L.impurely P.foldM L.vector (void (view B.decoded (B.drop 1 (B.fromHandle h)))))
    print (V.length (v::V.Vector (B.Word8,B.Word8)))

cons неэффективен. Подход, используемый foldl's vector, заключается в постепенном удвоении емкости вектора с помощью _ 9_, чтобы учесть входящие значения и в конце" обрезать "любую избыточную емкость с помощью _ 10_.

person danidiaz    schedule 19.09.2015
comment
Это элегантное решение - мне оно очень нравится, но когда я тестирую, требуется около 2 секунд, чтобы использовать файл размером 1 МБ, тогда как чтение двух байтов за раз метод занимает около 0,1 секунды. Это то, что вы видите? - person ErikR; 19.09.2015