Обрабатывать большие списки в Haskell в одно значение - PullRequest
Новая
       6

Обрабатывать большие списки в Haskell в одно значение

0 голосов
/ 14 октября 2018

У меня есть 2 списка Int одинакового размера (примерно 10000 элементов): скажем, x и y.Мне нужно вычислить произведение следующего выражения для каждой соответствующей пары элементов из списков: x_i / (x_i + y_i), т.е. x_i и y_i - первые элементы списков, затем вторые и т. Д.

Мои подходы хорошо работают в небольших тестовых случаях, но ghci зависает для больших списков.Любое понимание причины и решения будет приветствоваться.

Я попытался сделать это с фолдом, сначала сжав списки: 

getP:: [Int] -> [Int] -> Double
getP zippedCounts = foldr (\(x,y) acc -> let intX = fromIntegral x
                                             intY = fromIntegral y
                                             intSum = intX + intY in
                                             (acc*(intX/intSum))) 
                          1.0
                          zippedCounts

Я также попытался отречься: 

getP lst [] = 1.0
getP [] lst = 1.0
getP (h1:t1) (h2:t2) = ((fromIntegral h1) / ((fromIntegral h1) + (fromIntegral h2))) * (getP t1 t2)

А также понимание списка: 

getP lst1 lst2 = (product [((fromIntegral x) / ((fromIntegral x) + (fromIntegral y)))|x <- lst1, y <- lst2])

Ответы [ 2 ]

0 голосов
/ 14 октября 2018

У всех трех решений есть утечки пространства, возможно, именно это и приводит к отсутствию ответа.

В Haskell, при сокращении большого списка до единого итогового значения, очень легко непреднамеренно вызвать утечку пространства, если мы никогда не "посмотрите на "промежуточные значения вычисления.Мы можем получить гигантское дерево неоцененных громов, скрывающееся за, казалось бы, безобидным единственным значением Double.

Пример foldr протекает, потому что foldr никогда не вынуждает свой аккумулятор к слабымголова нормальной формы .Вместо этого используйте строгий левый foldl' (вам нужно будет переупорядочить некоторые аргументы функции).foldl' должен обеспечить, чтобы промежуточные значения Double оставались "маленькими", а thunks не накапливались.

Пример явной рекурсии опасен, поскольку он не является хвост-рекурсивным и для больших списков можетвызвать переполнение стека (мы многократно помещаем значения в стек, ожидая завершения следующего рекурсивного вызова).Решение может заключаться в том, чтобы сделать функцию хвостовой рекурсивной, передав передачу промежуточного результата в качестве дополнительного параметра , и добавив шаблон взрыва для этого параметра, чтобы убедиться, что thunks не накапливается.

В примере product утечка, потому что, к сожалению, ни функции sum, ни product не являются строгими.Для больших списков лучше использовать foldl'.(Существует также ошибка, как это было упомянуто в комментариях.)

0 голосов
/ 14 октября 2018

Вы можете попробовать zipWith, а затем product: 

getP :: [Int] -> [Int] -> Double
getP xs ys = product $ zipWith func xs ys
  where 
    func x y = let dx = fromIntegral x
                   dy = fromIntegral y
               in dx / (dx + dy)

Я бы не использовал явную рекурсию и придерживался библиотечных функций для скорости.Вы также можете использовать определенные флаги ghc для ускорения скомпилированного кода.

...