Насколько хорошо это работает? Профилирование в Haskell

Я уже говорил это раньше, но скажу еще раз. Как бы нам ни хотелось думать, что наш код на Haskell не работает только потому, что он компилируется. Вот почему у нас есть наборы тестов. Но даже если он проходит наши тестовые наборы, это не означает, что он работает так хорошо, как мог бы. Иногда мы понимаем, что написанный нами код недостаточно эффективен, поэтому нам приходится его улучшать.

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

Обратите внимание, что инструменты, которые мы будем использовать, требуют, чтобы вы организовали свой код с помощью Stack или Cabal. Если вы никогда не использовали ни один из них раньше, вам следует ознакомиться с нашим Мини-курсом по стеку! Он научит вас основам создания проекта с помощью Stack. Вы также изучите основные команды для использования со стеком. Это совершенно новое и, самое главное, БЕСПЛАТНОЕ! Проверьте это! Это наш первый курс любого рода, поэтому мы ждем отзывов!

Проблема

Нашей всеобъемлющей задачей в этой статье будет задача о наибольшем прямоугольнике. На самом деле вы можете сами попробовать решить эту проблему на Хакерранке под именем Джон и Заборы. Представьте, что у нас есть ряд вертикальных полос разной высоты, расположенных рядом друг с другом. Мы хотим найти площадь наибольшего прямоугольника, который мы можем нарисовать на этих полосах, не включая пустого пространства. Вот визуализация одной такой проблемы и решения:

В этом примере у нас есть посты высотой [2,5,7,4,1,8]. Самый большой прямоугольник, который мы можем сформировать, имеет площадь 12, как видно из выделенных квадратов.

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

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
...
newtype FenceValues = FenceValues { unFenceValues :: [Int] }
newtype FenceIndex = FenceIndex { unFenceIndex :: Int }
  deriving (Eq, Num, Ord)
-- Left Index is inclusive, right index is non-inclusive 
newtype FenceInterval = FenceInterval { unFenceInterval :: (FenceIndex, FenceIndex) }
newtype FenceSolution = FenceSolution { unFenceSolution :: Int }
  deriving (Eq, Show, Ord)

Далее мы определим нашу основную функцию. Он возьмет наш FenceValues, список целых чисел, и вернет наше решение.

largestRectangle :: FenceValues -> FenceSolution
largestRectangle values = ...

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

largestRectangle :: FenceValues -> FenceSolution
largestRectangle values = largestRectangleAtIndices values
  (FenceInterval (FenceIndex 0, FenceIndex (length (unFenceValues values))))
largestRectangleAtIndices :: FenceValues -> FenceInterval -> FenceSolution
largestRectangleAtIndices = ...

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

Любой другой «самый большой прямоугольник» не будет использовать этот конкретный индекс. Таким образом, мы можем разделить нашу задачу еще на два случая. В первом мы найдем самый большой прямоугольник на интервале слева. Во втором смотрим направо.

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

largestRectangleAtIndices :: FenceValues -> FenceInterval -> FenceSolution
largestRectangleAtIndices
  values
  interval@(FenceInterval (leftIndex, rightIndex)) = 
    -- Base Case: Checks if left + 1 >= right
    if isBaseInterval interval
      then FenceSolution (valueAtIndex values leftIndex)
      -- Compare three cases
      else max (max middleCase leftCase) rightCase
      where
      -- Find the minimum height and its index
      (minIndex, minValue) = minimumHeightIndexValue values interval
      -- Case 1: Use the minimum index
      middleCase = FenceSolution $ (intervalSize interval) * minValue
      -- Recursive call #1
      leftCase = largestRectangleAtIndices values (FenceInterval (leftIndex, minIndex))
      -- Guard against case where there is no "right" interval
      rightCase = if minIndex + 1 == rightIndex
        then FenceSolution (maxBound :: Int) -- Supply a "fake" solution that we'll ignore
        -- Recursive call #2
        else largestRectangleAtIndices values (FenceInterval (minIndex + 1, rightIndex))

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

valueAtIndex :: FenceValues -> FenceIndex -> Int
valueAtIndex values index = (unFenceValues values) !! (unFenceIndex index)
isBaseInterval :: FenceInterval -> Bool
isBaseInterval (FenceInterval (FenceIndex left, FenceIndex right)) = left + 1 >= right
intervalSize :: FenceInterval -> Int
intervalSize (FenceInterval (FenceIndex left, FenceIndex right)) = right - left

Теперь нам нужно определить минимум на этом интервале. Сделаем это самым наивным способом, просканировав весь интервал со складкой.

minimumHeightIndexValue :: FenceValues -> FenceInterval -> (FenceIndex, Int)
minimumHeightIndexValue values (FenceInterval (FenceIndex left, FenceIndex right)) =
  foldl minTuple (FenceIndex (-1), maxBound :: Int) valsInInterval
  where
    valsInInterval :: [(FenceIndex, Int)]
    valsInInterval = drop left (take right (zip (FenceIndex <$> [0..]) (unFenceValues values)))
    minTuple :: (FenceIndex, Int) -> (FenceIndex, Int) -> (FenceIndex, Int)
    minTuple old@(_, heightOld) new@(_, heightNew) =
      if heightNew < heightOld then new else old

И теперь мы закончили!

Сравнительный анализ нашего кода

Теперь это аккуратное небольшое алгоритмическое решение, но мы хотим знать, эффективен ли наш код. Нам нужно знать, будет ли он масштабироваться до больших входных значений. Мы можем найти ответ на этот вопрос, написав бенчмарки. Бенчмарки — это функция, которую мы можем использовать вместе с Cabal и Stack. Они во многом похожи на наборы тестов. Но вместо того, чтобы доказывать правильность нашего кода, они покажут нам, как быстро наш код работает при различных обстоятельствах. Для этого мы будем использовать библиотеку Criterion. Мы начнем с добавления раздела в наш файл .cabal для этого теста:

benchmark fences-benchmarks
  type:                exitcode-stdio-1.0
  hs-source-dirs:      benchmark
  main-is:             fences-benchmark.hs
  build-depends:       base
                     , FencesExample
                     , criterion
                     , random
  default-language:    Haskell2010

Теперь сделаем наш файл fences-benchmark.hs, сделаем из него модуль Main и добавим функцию main. Мы создадим 6 списков, каждый раз увеличивая размер в 10 раз. Затем мы создадим контрольную группу и вызовем функцию bench для каждой ситуации.

module Main where
import Criterion
import Criterion.Main (defaultMain)
import System.Random
import Lib
main :: IO ()
main = do
  [l1, l2, l3, l4, l5, l6] <- mapM 
    randomList [1, 10, 100, 1000, 10000, 100000]
  defaultMain
    [ bgroup "fences tests" 
      [ bench "Size 1 Test" $ whnf largestRectangle l1
      , bench "Size 10 Test" $ whnf largestRectangle l2
      , bench "Size 100 Test" $ whnf largestRectangle l3
      , bench "Size 1000 Test" $ whnf largestRectangle l4
      , bench "Size 10000 Test" $ whnf largestRectangle l5
      , bench "Size 100000 Test" $ whnf largestRectangle l6
      ]
    ]
-- Generate a list of a particular size
randomList :: Int -> IO FenceValues
randomList n = FenceValues <$> (sequence $ replicate n (randomRIO (1, 10000 :: Int)))

Обычно мы запускаем эти тесты с stack bench (или cabal bench, если вы не используете стек). Но мы также можем скомпилировать наш код с флагом --profile. Это автоматически создаст отчет о профилировании с дополнительной информацией о нашем коде. Обратите внимание, что использование профилирования требует повторной компиляции ВСЕХ зависимостей для использования профилирования. Таким образом, вы не хотите переключаться туда и обратно много.

>> stack bench --profile
Benchmark fences-benchmarks: RUNNING...
benchmarking fences tests/Size 1 Test
time                 47.79 ns   (47.48 ns .. 48.10 ns)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 47.78 ns   (47.48 ns .. 48.24 ns)
std dev              1.163 ns   (817.2 ps .. 1.841 ns)
variance introduced by outliers: 37% (moderately inflated)
benchmarking fences tests/Size 10 Test
time                 3.324 μs   (3.297 μs .. 3.356 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 3.340 μs   (3.312 μs .. 3.368 μs)
std dev              98.52 ns   (79.65 ns .. 127.2 ns)
variance introduced by outliers: 38% (moderately inflated)
benchmarking fences tests/Size 100 Test
time                 107.3 μs   (106.3 μs .. 108.2 μs)
                     0.999 R²   (0.999 R² .. 0.999 R²)
mean                 107.2 μs   (106.3 μs .. 108.4 μs)
std dev              3.379 μs   (2.692 μs .. 4.667 μs)
variance introduced by outliers: 30% (moderately inflated)
benchmarking fences tests/Size 1000 Test
time                 8.724 ms   (8.596 ms .. 8.865 ms)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 8.638 ms   (8.560 ms .. 8.723 ms)
std dev              228.8 μs   (193.6 μs .. 272.8 μs)
benchmarking fences tests/Size 10000 Test
time                 909.2 ms   (899.3 ms .. 914.1 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 915.1 ms   (914.6 ms .. 915.8 ms)
std dev              620.1 μs   (136.0 as .. 664.8 μs)
variance introduced by outliers: 19% (moderately inflated)
benchmarking fences tests/Size 100000 Test
time                 103.9 s    (91.11 s .. 117.3 s)
                     0.997 R²   (0.997 R² .. 1.000 R²)
mean                 107.3 s    (103.7 s .. 109.4 s)
std dev              3.258 s    (0.0 s .. 3.702 s)
variance introduced by outliers: 19% (moderately inflated)
Benchmark fences-benchmarks: FINISH

Итак, когда мы запустим это, мы обнаружим что-то… тревожное. Финальный бенчмарк для размера 100000 занимает очень много времени. В среднем этот случай занимает более 100 секунд… более полутора минут! Мы также можем отметить, как среднее время работы увеличивается в зависимости от размера корпуса. Давайте немного сократим данные:

Size 1: 47.78 ns
Size 10: 3.340 μs (increased ~70x)
Size 100: 107.2 μs (increased ~32x)
Size 1000: 8.638 ms (increased ~81x)
Size 10000: 915.1 ms (increased ~106x)
Size 100000: 107.3 s (increased ~117x)

Каждый раз, когда мы увеличиваем размер задачи в 10 раз, затрачиваемое время увеличивается в 100 раз! Это предполагает, что наше время выполнения составляет O(n^2) (ознакомьтесь с этим руководством, если вы не знакомы с нотацией Big-O). Мы хотели бы сделать лучше.

Определение проблемы

Итак, мы хотим выяснить, почему наш код работает не очень хорошо. К счастью, мы уже профилировали наш эталон! Это выводит определенный файл, который мы можем просмотреть, с именем fences-benchmark.prof. У него есть очень интересные результаты:

COST CENTRE                            %time %alloc
minimumHeightIndexValue.valsInInterva  69.8   99.7
valueAtIndex                           29.3    0.0

Мы видим, что у нас есть два больших преступника, занимающих много времени. Во-первых, это наша функция, которая определяет минимум между определенным интервалом. Отчет еще более конкретен, выявляя конкретную часть функции, нарушающую правила. Мы тратим много времени на получение разных значений для определенного интервала. На втором месте у нас valueAtIndex. Это означает, что мы также тратим много времени на получение значений из нашего списка.

Во-первых, давайте порадуемся, что мы хорошо разобрали наш код. Если бы мы написали все наше решение в одной большой функции, у нас не было бы здесь лидов. Это значительно облегчает нам анализ проблемы. Изучая код, мы видим, почему обе эти функции могут давать O(n^2) поведение.

Из-за большого количества рекурсивных вызовов мы будем вызывать каждую из этих функций O(n) раз. Затем, когда мы вызываем valueAtIndex, мы используем оператор (!!) в нашем связанном списке. Это занимает O(n) времени. Тот же эффект дает сканирование всего интервала на предмет минимальной высоты. В худшем случае нам придется просмотреть каждый элемент в списке! Здесь я немного машу рукой, но это основной результат. Когда мы называем эти O(n) фрагментов O(n) раз, мы получаем O(n^2) общего времени.

Концовка Клиффа Вешалки

На самом деле мы можем решить эту проблему за O(n log n) времени, что является значительным улучшением по сравнению с нынешними O(n^2). Но для этого нам придется улучшить наши структуры данных. Во-первых, мы сохраним наши значения, чтобы мы могли перейти от индекса к элементу за сублинейное время. Это легко. Во-вторых, мы должны определить индекс, содержащий минимальный элемент в произвольном интервале. Это немного сложнее сделать в сублинейном времени. Нам понадобится более продвинутая структура данных.

Чтобы узнать, как мы решаем эти проблемы, вам придется дождаться второй части этой серии! Возвращайтесь на следующей неделе в Monday Morning Haskell blog!

Напоминаем, что мы только что опубликовали БЕСПЛАТНЫЙ мини-курс по стеку. Он научит вас основам компоновки проекта и запуска на нем команд с помощью инструмента Stack. Вы должны зарегистрироваться в Академии Monday Morning Haskell Academy, чтобы зарегистрироваться! Это наш первый курс такого рода, поэтому мы будем рады вашим отзывам! Как только вы узнаете о стеке, вам будет намного проще решить эту задачу самостоятельно!

В дополнение к стеку, рекурсия также довольно активно использовалась в нашем решении здесь. Если вы занимались функциональным программированием, вы видели рекурсию в действии. Но если вы хотите закрепить свои знания, скачайте нашу БЕСПЛАТНУЮ Рабочую тетрадь по рекурсии! Он состоит из двух глав, посвященных рекурсии, и содержит 10 практических задач, которые вы можете решить!

Никогда не программировали на Haskell? Без проблем! Вы можете скачать наш Контрольный список для начала работы, и он поможет вам установить Haskell. Это также укажет вам направление некоторых отличных учебных ресурсов. Посмотри!

Hacker Noon — это то, как хакеры начинают свой день. Мы являемся частью семьи @AMI. Сейчас мы принимаем заявки и рады обсудить возможности рекламы и спонсорства.

Чтобы узнать больше, прочитайте нашу страницу о нас, лайкните/отправьте нам сообщение на Facebook или просто твитните/DM @HackerNoon.

Если вам понравилась эта история, мы рекомендуем прочитать наши последние технические истории и актуальные технические истории. До следующего раза, не принимайте реалии мира как должное!