Оптимизация чтения данных Haskell из файла

Ответ 1

Использование карт:

• Используйте IntMap или HashMap, когда это возможно. Оба они значительно быстрее для клавиш Int, чем Map. HashMap обычно быстрее, чем IntMap, но использует больше ОЗУ и имеет менее богатую библиотеку.
• Не делайте ненужных поисков. Пакет containers имеет большое количество специализированных функций. С alter количество поисковых запросов может быть уменьшено в два раза по сравнению с реализацией createGraph в вопросе.

Пример для createGraph:

import Data.List (foldl')
import qualified Data.IntMap.Strict as IM

type NodeName = Int
type Edges = [NodeName]
type Explored = Bool

data Node = Node Explored Edges Edges deriving (Eq, Show)
type Graph1 = IM.IntMap Node

createGraph :: [(Int, Int)] -> Graph1
createGraph xs = foldl' build IM.empty xs
    where
        addFwd y (Just (Node _ f b)) = Just (Node False (y:f) b)
        addFwd y _                   = Just (Node False [y] [])
        addBwd x (Just (Node _ f b)) = Just (Node False f (x:b))
        addBwd x _                   = Just (Node False [] [x])

        build :: Graph1 -> (Int, Int) -> Graph1
        build acc (x, y) = IM.alter (addBwd x) y $ IM.alter (addFwd y) x acc 

Использование векторов:

• Рассмотрим эффективные функции построения (аккумуляторы, разворачивается, generate, iterate, constructN и т.д.). Они могут использовать мутацию за кулисами, но значительно удобнее использовать, чем фактические изменяемые векторы.
• В более общем случае используйте лень вложенных векторов, чтобы включить самореференцию при конструировании вектора.
• При необходимости используйте нераспознанные векторы.
• Используйте небезопасные функции, когда вы абсолютно уверены в границах.
• Используйте только изменяемые векторы, когда нет чистых альтернатив. В этом случае предпочитайте монаду ST для ввода-вывода. Кроме того, избегайте создания многих изменяемых объектов кучи (то есть предпочитайте изменчивые векторы к неизменяемым векторам изменяемых ссылок).

Пример для createGraph:

import qualified Data.Vector as V

type NodeName = Int
type Edges = [NodeName]
type Explored = Bool

data Node = Node Explored Edges Edges deriving (Eq, Show)
type Graph1 = V.Vector Node

createGraph :: Int -> [(Int, Int)] -> Graph1
createGraph maxIndex edges = graph'' where
    graph    = V.replicate maxIndex (Node False [] [])
    graph'   = V.accum (\(Node e f b) x -> Node e (x:f) b) graph  edges
    graph''  = V.accum (\(Node e f b) x -> Node e f (x:b)) graph' (map (\(a, b) -> (b, a)) edges)

Обратите внимание, что если есть пробелы в диапазоне индексов node, тогда было бы разумно либо

• Смежно переопределять индексы перед тем, как делать что-либо еще.
• Ввести пустой конструктор в Node, чтобы обозначить отсутствующий индекс.

Более быстрый ввод-вывод:

• Используйте функции ввода-вывода от Data.Text или Data.ByteString. В обоих случаях существуют также эффективные функции для разбиения входных данных на строки или слова.

Пример:

import qualified Data.ByteString.Char8 as BS
import System.IO

getLines :: FilePath -> IO [(Int, Int)]
getLines path = do
    lines <- (map BS.words . BS.lines) `fmap` BS.readFile path
    let pairs = (map . map) (maybe (error "can't read Int") fst . BS.readInt) lines
    return [(a, b) | [a, b] <- pairs]

Бенчмаркинг:

Всегда делай это, в отличие от меня в этом ответе. Используйте criterion.

Ответ 2

Основываясь на предложениях András, я сократил 113-секундную задачу до 24 (измеряется секундомером, поскольку я не могу получить Criterion еще ничего) (а затем до 10 путем компиляции -O2)!!! В прошлом году я посещал некоторые курсы, в которых говорилось о проблеме оптимизации для больших наборов данных, но это был первый случай, когда я столкнулся с вопросом, который действительно касался одного, и это было так же просто, как и мои преподаватели. Это то, что у меня есть сейчас:

import System.IO
import Control.Monad
import Data.List (foldl')
import qualified Data.IntMap.Strict as IM
import qualified Data.ByteString.Char8 as BS

type NodeName = Int
type Edges = [NodeName]
type Explored = Bool

data Node = Node Explored Edges Edges deriving (Eq, Show)
type Graph1 = IM.IntMap Node

-- DFS uses a stack to store next points to explore, a list can do this
type Stack = [(NodeName, NodeName)]

getBytes :: FilePath -> IO [(Int, Int)]
getBytes path = do
    lines <- (map BS.words . BS.lines) `fmap` BS.readFile path
    let
        pairs = (map . map) (maybe (error "Can't read integers") fst . BS.readInt) lines
    return [(a,b) | [a,b] <- pairs]

main = do
    --list <- getLines' "testdata.txt"  -- [String]
    list <- getBytes "SCC.txt"  -- [String] 
    let list' = createGraph' list
    putStrLn $ show $ list' IM.! 66
    -- return list'


bmark = defaultMain [
    bgroup "1" [
        bench "Sim test" $ whnf bmark' "SCC.txt"
        ]
    ]

bmark' :: FilePath -> IO ()
bmark' path = do
    list <- getLines path
    let
        list' = createGraph list
    putStrLn $ show $ list' IM.! 2


createGraph' :: [(Int, Int)] -> Graph1
createGraph' xs = foldl' build IM.empty xs
    where
        addFwd y (Just (Node _ f b)) = Just (Node False (y:f) b)
        addFwd y _                   = Just (Node False [y] [])
        addBwd x (Just (Node _ f b)) = Just (Node False f (x:b))
        addBwd x _                   = Just (Node False [] [x])

        build :: Graph1 -> (Int, Int) -> Graph1
        build acc (x, y) = IM.alter (addBwd x) y $ IM.alter (addFwd y) x acc 

И теперь с остальной частью упражнения....

Ответ 3

На самом деле это не ответ, я бы предпочел комментарий András Kovács post, если я добавлю эти 50 баллов...

Я выполнил загрузку графика как в IntMap, так и в MVector, пытаясь сопоставить изменчивость и неизменность.

Обе программы используют Attoparsec для синтаксического анализа. Конечно, есть более экономичный способ сделать это, но Attoparsec относительно быстро по сравнению с его высоким уровнем абстракции (синтаксический анализатор может стоять в одной строке). Рекомендация состоит в том, чтобы избежать String и read. read является частичным и медленным, [Char] является медленным, а не эффективным с точки зрения памяти, если только не правильно спланировано.

Как заметил András Kovács, IntMap лучше, чем Map for Int. Мой код предоставляет другой пример использования alter. Если отображение идентификатора node является плотным, вы также можете использовать Vector и Array. Они позволяют индексировать O (1) по идентификатору.

Измененная версия обрабатывает по требованию экспоненциальный рост MVector. Это позволяет не уточнять верхнюю границу идентификаторов node, но ввести более сложную (ссылка на вектор может измениться).

Я сравнивал с файлом 5M ребер с идентификаторами в диапазоне [0..2 ^ 16]. Версия MVector ~ 2x быстрее, чем код IntMap (12 секунд против 25 секунд на моем компьютере).

Код здесь [Gist].

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