haskell membaca vektor pasangan dari bytestring sangat lambat, bagaimana cara membuatnya lebih cepat?

Saya mencoba membaca vektor besar tipe data khusus dari file biner. Saya mencoba menggunakan contoh yang diberikan di sini.

Masalah dengan kode contohnya adalah, ia menggunakan daftar dan saya ingin menggunakan vektor. Jadi saya mengadaptasi kode itu seperti di bawah ini, tetapi butuh waktu sangat lama (lebih dari satu menit, saya menyerah setelah itu) untuk membaca file 1 MB sekalipun.

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)?

Ketika saya mencoba menjalankannya dengan ghc --make -O2 pairs.hs saya mendapat kesalahan Stack space overflow: current size ...

Bagaimana cara membaca pasangan nilai dari bytestring ke vektor secara efisien?

Sekali lagi, saya ingin mendapatkan kode kerja yang lengkap tidak hanya hanya petunjuk ke situs Haskell atau RWH atau hanya daftar nama fungsi/modul.


performance vector haskell bytestring
person mntk123    schedule 19.09.2015    source sumber
comment
Anda tidak boleh menuntut solusi lengkap yang berfungsi sebagai jawabannya. SO adalah situs pembelajaran dan pemahaman masalah, bukan layanan coding crowdsourcing.   -  person Erik Kaplun    schedule 19.09.2015
comment
@ErikAllik Saya menuntut solusi kerja lengkap dengan semangat yang sama dengan Contoh Kerja Lengkap Terkecil. Saya juga memberikan contoh kerja minimum. Alasan lainnya adalah jarangnya contoh kerja di situs Haskell. Masalah yang saya minta solusinya umumnya berupa cuplikan yang sangat kecil, hampir tidak cukup untuk menuduh saya melakukan kode crowdsourcing. SO yang bagus dan dokumentasi Haskell yang buruk adalah alasan saya harus membuat permintaan itu. Saya minta maaf jika telah menyakiti/menyinggung atau menyebabkan kesusahan yang tidak semestinya pada seseorang.   -  person mntk123    schedule 19.09.2015
comment
Ya, ini lambat karena V.cons adalah O(n). Apa yang kamu harapkan? Satu juta kali satu juta itu banyak! vector memiliki dokumentasi yang sangat bagus. Perhatikan bahwa dokumentasi modul Hackage umumnya memiliki daftar isi di kanan atas. Lihat bagian membangun vektor.   -  person dfeuer    schedule 19.09.2015
comment
@dfeuer Saya mengira ini akan lambat. Tapi saya tidak tahu metode lain untuk membuat vektor dengan menambahkan elemen secara bertahap saat saya terus membaca nilai dari bytestring. Adapun mengapa saya mengajukan pertanyaan: Saya tidak memahami metode lain yang diberikan pada peretasan yang memungkinkan saya membuat vektor secara bertahap sesuai keinginan.   -  person mntk123    schedule 19.09.2015
comment
Ya, pada dasarnya Anda tidak bisa membuat vektor dengan menambahkannya secara bertahap! Mereka lebih seperti array C atau C++ atau vektor FORTRAN daripada hal-hal fleksibel yang disebut vektor oleh lingkungan lain. Anda bisa mendapatkan hal-hal fleksibel di Haskell jika Anda mau; yang tradisional adalah Data.Sequence, namun Ed Kmett sedang mengerjakan beberapa yang lebih cepat akhir-akhir ini.   -  person dfeuer    schedule 19.09.2015

Jawaban (2)


arrow_upward
2
arrow_downward

Berikut adalah beberapa contoh pembuatan Vektor dari file. Keduanya bukan yang paling efisien, tetapi keduanya berjalan hanya dalam beberapa detik di 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

Alternatif ketiga:

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

Yang ini ternyata yang tercepat dari ketiganya.

person ErikR    schedule 19.09.2015
comment
Perhatikan bahwa menggunakan size <- hFileSize h mungkin merupakan cara yang lebih portabel untuk mendapatkan ukuran file dan tidak memerlukan System.Posix - person ErikR; 19.09.2015
comment
fungsi readVector2 menggunakan daftar dan readVector1 terlalu banyak berfungsi di IO. - person mntk123; 19.09.2015
comment
Keduanya berjalan dalam waktu kurang dari satu detik ketika dikompilasi di mesin saya. Berapa lama waktu yang dibutuhkan untuk Anda? - person ErikR; 19.09.2015
comment
@ user5402: Anda mengubah sedikit kodenya - maukah Anda menjelaskan perubahan apa yang paling penting untuk meningkatkan kinerja? (Saya penasaran) - person Sam van Herwaarden; 19.09.2015
comment
Menurut saya kesimpulan utamanya adalah Vec.cons mungkin tidak efisien. Pada awalnya saya pikir Anda harus memberi tahu Vector panjang yang Anda butuhkan - karena itu versi pertama. Namun, unfold juga berfungsi dengan cukup baik. Perbedaan utama antara unfoldr dan cons adalah unfoldr ditambahkan ke vektor yang merupakan operasi yang lebih alami sehingga menurut saya lebih efisien. cons, namun, saya yakin harus menambahkan vektor yang bukan merupakan cara alami bagi vektor untuk berkembang. - person ErikR; 19.09.2015
comment
Tidak. unfoldr hanya menggunakan trik penggandaan array tradisional untuk mencapai O(1) waktu diamortisasi per snoc meskipun mungkin harus menggandakan ukuran array beberapa kali, menyalin semuanya setiap kali. - person dfeuer; 19.09.2015
comment
Ya - tapi menurut saya ini tampaknya jauh lebih baik daripada menggunakan cons. - person ErikR; 19.09.2015
comment
Ya, tentu saja! Namun teknik yang sama dapat diterapkan untuk mengisi vektor dari belakang ke depan. cons harus menyalin seluruh vektor setiap kali. unfoldr menghemat ruang gerak sehingga dapat membeli salinan sesekali tanpa melanggar batasan asimtotik. Tambahkan vs. tambahkan tidak ada hubungannya dengan itu. - person dfeuer; 19.09.2015
comment
@ user5402 Saya menyukai dan memberi suara positif pada jawaban Anda, tetapi yang mengganggu saya adalah bagian IO di readVector1. Jika Anda memberikan kode untuk membaca vektor yang hanya mengambil ByteString (Anda dapat menemukan ukurannya) dan kemudian mengembalikan vektor yang diisi dengan nilai, saya akan menerimanya. Saya berjuang sendiri untuk mendapatkan jenis kode itu menggunakan kode Anda tetapi tidak dapat menghapus IO darinya. - person mntk123; 19.09.2015
comment
Oke - perhatikan ruang ini. - person ErikR; 19.09.2015
comment
Lihat readVector3. Sesuaikan rumus offset 2*i, 2*i+1 dan penentuan panjang div size 2 untuk memperhitungkan byte header yang ingin Anda lewati. - person ErikR; 19.09.2015
comment
@ user5402 Saya menerima jawaban ini. Saya tidak dapat memberi suara positif lebih dari sekali. Anda telah mengajari saya banyak hal melalui jawabannya. - person mntk123; 19.09.2015

arrow_upward
2
arrow_downward

Berikut pendekatan alternatif untuk memuat vektor, yang menggunakan pipes dan pipes-bytestring untuk melakukan streaming file, dan vector berfungsi dari foldl untuk membuat vektor:

{-# 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 tidak efisien. Pendekatan yang diambil oleh foldl's vector adalah dengan menggandakan kapasitas vektor secara progresif menggunakan unsafeGrow, untuk mengakomodasi nilai yang masuk, dan pada akhirnya "memangkas" kelebihan kapasitas dengan unsafeTake.

person danidiaz    schedule 19.09.2015
comment
Ini solusi yang elegan - Saya sangat menyukainya, tetapi ketika saya melakukan benchmark, dibutuhkan sekitar 2 detik untuk menggunakan file 1 MB sedangkan metode membaca dua byte sekaligus membutuhkan waktu sekitar 0,1 detik. Itukah yang kamu lihat? - person ErikR; 19.09.2015