Насколько лениво у Хаскелла `++`? - PullRequest
Новая
       13

Насколько лениво у Хаскелла `++`?

14 голосов
/ 15 января 2012

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

import Data.List
swapAt n = f . splitAt n where f (a,b) = b++a
minimumrotation x = minimum $ map (\i -> swapAt i x) $ elemIndices (minimum x) x

Я полагаю, что мне следует использовать Data.Vector, а не списки, потому что Data.Vector обеспечивает операции на месте, вероятно, просто манипулируя некоторыми индексами в исходных данных. На самом деле мне не нужно самостоятельно следить за индексами, чтобы избежать лишнего копирования, верно?

Мне любопытно, как ++ влияет на оптимизацию. Я предполагаю, что он генерирует ленивый поток строк, который никогда не добавляет, пока строка не будет прочитана настолько далеко. Следовательно, a никогда не должен добавляться к b всякий раз, когда минимум может удалить эту строку рано, например, потому что она начинается с какой-то очень поздней буквы. Это правильно?

Ответы [ 3 ]

10 голосов
/ 15 января 2012

xs ++ ys добавляет некоторые издержки во все ячейки списка из xs, но как только он достигает конца xs, он становится свободным - он просто возвращает ys.

Просмотр определения(++) помогает понять, почему: 

[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

, т. Е. Он должен «перестроить» весь первый список по мере прохождения результата. Эта статья очень полезна для понимания того, как рассуждать о ленивом коде таким образом.

Главное, что нужно понять, это то, что добавление не происходит сразу;новый связанный список создается постепенно, сначала пройдя через все 1015 *, а затем поместив ys туда, куда пойдет [].

Итак, вам не нужно беспокоиться о достижении концаb и внезапно повлечет за собой разовую стоимость «добавления» a к нему;стоимость распределена по всем элементам b.

Векторы - это совершенно другое дело;они строгие по своей структуре, поэтому даже проверка только первого элемента xs V.++ ys влечет за собой все затраты на выделение нового вектора и копирование в него xs и ys - как в строгом языке.То же относится и к изменяемым векторам (за исключением того, что затраты возникают при выполнении операции, а не при форсировании результирующего вектора), хотя я думаю, что вам все равно придется написать собственную операцию добавления с этими операциями.Вы можете представить набор добавленных (неизменяемых) векторов как [Vector a] или аналогичный, если это проблема для вас, но это просто перемещает накладные расходы, когда вы сливаете их обратно в один вектор, и это звучит так, как будто вы болееинтересует изменяемые векторы.

5 голосов
/ 16 января 2012

Попробуйте 

minimumrotation :: Ord a => [a] -> [a]
minimumrotation xs = minimum . take len . map (take len) $ tails (cycle xs)
  where
    len = length xs

Я ожидаю, что это будет быстрее, чем у вас, хотя жонглирование индексами на распакованных Vector или UArray, вероятно, будет еще быстрее.Но действительно ли это узкое место?

3 голосов
/ 16 января 2012

Если вы заинтересованы в быстрой конкатенации и быстрой splitAt, используйте Data.Sequence .

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

import qualified Data.Sequence as S
import qualified Data.Foldable as F

minimumRotation :: Ord a => [a] -> [a]
minimumRotation xs = F.toList
                   . F.minimum
                   . fmap (`swapAt` xs')
                   . S.elemIndicesL (F.minimum xs')
                   $ xs'
  where xs' = S.fromList xs
        swapAt n = f . S.splitAt n
          where f (a,b) = b S.>< a
...