Сравнение производительности

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

finalCountDown :: Int –> Writer (DiffList String) ()

finalCountDown 0 = tell (toDiffList ["0"])

finalCountDown x = do

   finalCountDown (x-1)

   tell (toDiffList [show x])

Если мы передаём ей значение 0, она просто записывает это значение в журнал. Для любого другого числа она сначала вычисляет предшествующее ему число в обратном направлении до 0, а затем добавляет это число в конец журнала. Поэтому если мы применим функцию finalCountDown к значению 100, строка "100" будет идти в журнале последней.

Если вы загрузите эту функцию в интерпретатор GHCi и примените её к большому числу, например к значению 500 000, то увидите, что она быстро начинает счёт от 0 и далее:

ghci> mapM_ putStrLn . fromDiffList .snd . runWriter $ finalCountDown 500000

0

1

2

...

Однако если вы измените её, чтобы она использовала обычные списки вместо разностных, например, так:

finalCountDown :: Int –> Writer [String] ()

finalCountDown 0 = tell ["0"]

finalCountDown x = do

   finalCountDown (x-1)

   tell [show x]

а затем скажете интерпретатору GHCi, чтобы он начал отсчёт:

ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000

вы увидите, что вычисления идут очень медленно.

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

Ну, теперь в вашей голове наверняка засела песня «Final Countdown» группы Europe. Балдейте!