Как заставить мой код на Haskell использовать Laziness and Garbage collector - PullRequest
Новая
       26

Как заставить мой код на Haskell использовать Laziness and Garbage collector

2 голосов
/ 17 сентября 2010

Я написал код на Haskell, который должен решить следующую проблему: у нас есть n файлов: f1, f2, f3 .... fn, и я вырезал эти файлы так, чтобы у каждого среза было 100 строк 

  f1_1, f1_2, f1_3 .... f1_m

  f2_1, f2_2, .... f2_n
  ...

  fn_1, fn_2, .... fn_k

наконец, я создаю специальный тип данных (Dags), используя кусочки следующим образом 

  f1_1, f2_1, f3_1, .... fn_1 => Dag1

  f1_2, f2_2, f3_2, ..... fn_2 => Dag2

  ....

  f1_k, f2_k, f3_k, ..... fn_k => Dagk

код, который я написал, начинается с вырезания всех файлов, затем он связывает i-тые элементы списка результатов и создает Dag, используя окончательный список результатов

это выглядит так 

  -- # take a filename and cut the file in slices of 100 lines

  sliceFile :: FilePath -> [[String]]

  -- # take a list of lists and group the i-th elements into list

  coupleIthElement :: [[String]] -> [[String]]

  -- # take a list of lines and create a DAG

  makeDags :: [String] ->  Dag

  -- # final code look like this

  makeDag_ :: [FilePath] -> [Dag]

  makeDags files = map makeDags $ coupleIthElement (concat (map sliceFile files))

Проблема в том, что этот код неэффективен, потому что:

  • необходимо сохранить все файлы в памяти в виде списка

  • сборщик мусора не работает эффективно, так как все функции нуждаются в списке результатов предыдущей функции

Как я мог переписать свою программу, чтобы воспользоваться преимуществами работы сборщика мусора и Laziness of Haskell?

если невозможно или проще, что я могу сделать, чтобы хоть немного повысить эффективность?

спасибо за ответ

редактировать

coupleIthElement ["abc", "123", "xyz"] должен вернуть ["a1x","b2y","c3z"]

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

другое издание 

data Dag = Dag ([(Int, String)], [((Int, Int), Int)]) deriving Show

test_dag = Dag ([(1, "a"),(2, "b"),(3, "c")],[((1,2),1),((1,3),1)])

test_dag2 = Dag ([],[])

первый список - каждая вершина, определяемая номером и меткой, второй список - ребра ((1,2),3) означает ребро между вершинами 1 и 2 со стоимостью 3

Ответы [ 2 ]

2 голосов
/ 17 сентября 2010

Несколько баллов:

1) Рассматривали ли вы использование fgl ? Это, вероятно, более эффективно, чем ваша Dag реализация. Если вам действительно нужно использовать Dag, вы можете построить свои графики с помощью fgl, а затем преобразовать их в Dag, когда они будут завершены.

2) Похоже, что вы на самом деле не используете срезы при построении графиков, они контролируют, сколько графиков у вас есть. Если так, то как что-то вроде этого: 

dagFromHandles :: [Handle] -> IO Dag
dagFromHandles = fmap makeDags . mapM hGetLine

allDags :: [FilePath] -> IO [Dag]
allDags listOfFiles = do
  handles <- mapM (flip openFile ReadMode) listOfFiles
  replicateM 100 (dagFromHandles handles)

Это предполагает, что каждый файл имеет не менее 100 строк, и любые дополнительные строки будут игнорироваться. Еще лучше было бы, если бы у вас была функция, которая потребляла бы Dag, тогда вы могли бы сделать 

useDag :: Dag -> IO ()

runDags :: [FilePath] -> IO ()
runDags listOfFiles = do
  handles <- mapM (flip openFile ReadMode) listOfFiles
  replicateM_ 100 (dagFromHandles handles >>= useDag)

Это должно более эффективно использовать сборку мусора.

Конечно, это предполагает, что я правильно понимаю проблему, и я не уверен, что понимаю. Обратите внимание, что concat (map sliceFile) должен быть неактивным (sliceFile должен быть в IO, поскольку вы определили тип, но пока игнорируете его), поэтому я не понимаю, почему вы беспокоитесь об этом в все.

1 голос
/ 17 сентября 2010

Если вам не нужно обрабатывать файл по частям, избегайте этого. Haskell делает это автоматически! В Haskell вы думаете о IO как о потоке. Данные считываются с ввода, как только они нужны, и отбрасываются, как только они не используются. Так, например, это простая программа для копирования файлов: 

main = interact id

interact имеет сигнатуру interact :: (String -> String) -> IO () и передает входные данные в функцию, которая обрабатывает их и производит некоторый вывод, который записывается в стандартный вывод. Эта программа более эффективна, чем большинство реализаций C, поскольку среда выполнения автоматически буферизует ввод и вывод.

Если вы хотите понять лень, вы должны забыть всю мудрость, которую вы узнали как императивный программист, и должны думать о программе как о описании для изменения данных, а не как о наборе инструкций - данные только обрабатывается при необходимости!

Ключевым моментом того, почему ваши данные могут обрабатываться неправильно, является многократный обход списка. Ваша функция makeDags пересекает список транспонированных фрагментов один за другим, поэтому элементы исходного списка не могут быть отброшены. Что вы должны попробовать, так это написать свою функцию следующим образом: 

sliceFile :: FilePath -> [[String]]
sliceFile fp = do
  f <- readFile fp
  let l = lines fp
      slice [] = []
      slice x  = ll : slice ls where (ll,ls) = splitAt 100 x
  return slice l

sliceFirstRow :: [[String]] -> ([String],[[String]])
sliceFirstRow list = unzip $ map (\(x:xs) -> (x,xs)) list

makeDags :: [[String]] -> [Dag]
makeDags [[]] = []
makeDags list = makeDag firstRow : makeDags restOfList where
 (firstRow,restOfList) = sliceFirstRow list

Эта функция может быть решением, так как на первую строку больше не ссылаются, когда это сделано. Но в большинстве случаев это результат лени, поэтому вы можете попытаться использовать seq для принудительного построения Dags и обеспечения возможности сбора данных ввода-вывода. (Если вы не форсируете создание пакетов, данные не могут быть собраны мусором).

Но в любом случае, я мог бы дать более полезный ответ, если вы дадите некоторую информацию о том, что это за даг.

...