Может ли сопоставление с образцом в do-notation / enumFromTo замедлить код на Haskell? - PullRequest
Новая
       53

Может ли сопоставление с образцом в do-notation / enumFromTo замедлить код на Haskell?

0 голосов
/ 03 марта 2019

Я решил довольно простую задачу: создание всех убывающих последовательностей длиной L, состоящих из натуральных чисел от 1 до M в лексикографическом порядке.Тем не менее, я столкнулся с довольно странной проблемой.Взгляните: 

c :: (Ord a, Num a, Enum a) => a -> a -> [[a]]
c m 1 = map return [1..m]
c m l = do
          n   <- [l..m]
          res <- c (n - 1) (l - 1)
          return $ n:res

c' :: (Ord a, Num a, Enum a) => a -> a -> [[a]]
c' m = helper 1 m where
 helper :: (Ord a, Num a, Enum a) => a -> a -> a -> [[a]]
 helper a b 1 = map return [a..b]
 helper a b l = do
                  n    <- [a..b]
                  True <- return $ (l - 1 <= n)
                  res  <- helper a (n - 1) (l - 1)
                  return (n:res)

Итак, очевидно, что эти две функции делают абсолютно одно и то же (я проверял их на нескольких тестах, они обе дают правильные результаты на каждой), но если вы попытаетесь оценитьc 100 98 и c' 100 98 в GHCi, вы увидите огромную разницу во времени, которое требуется:

c 100 98: около 5 секунд ;

c '100 98: около 70 секунд ;

Как я уже упоминал, результат тот же .

Так что, мне немного неловкогенерируя [a..b] каждый раз, но я немного расспросил, и было предположение, что Haskell не сопоставляет с образцом сразу, а задерживает его из-за ленивых вычислений, что вызывает огромное количестводополнительные звонки c'.Однако вторая теория не совсем верна: я установил точку останова в своем коде непосредственно из командной строки GHCi, чтобы отслеживать значение n, которое показало, что задержанное сопоставление с образцом не имело место.

Может ли проблема быть на самом деле с функцией enumFromTo, или есть какая-то другая причина?

Ответы [ 2 ]

0 голосов
/ 04 марта 2019

Изменение вашего True <- return $ (l - 1 <= n) на True <- return $ (l <= n) в соответствии с тем, что делает первый фрагмент, уравнивает для меня время двух (без изменения ответа).

Без этого изменения ваш второй фрагмент теряетМного времени пытался найти убывающие последовательности длины l среди чисел [1..l-1] (для многих различных значений l), обреченная задача.

0 голосов
/ 03 марта 2019

Кажется, что две функции имеют совершенно разную реализацию: 

c m l = do
      n   <- [l..m]
      res <- c (n - 1) (l - 1)
      return $ n:res

Здесь при каждом рекурсивном вызове параметр l уменьшается, а параметр m становится n <- [l--m].

Для сравнения: 

helper a b l = do
    n    <- [a..b]
    True <- return $ (l - 1 <= n)
    res  <- helper a (n - 1) (l - 1)
    return (n:res)

Здесь интервал составляет [a..b] вместо [l..m] (кстати, почему вы используете разные имена? Сложнее сравнить два фрагмента в этомпуть.) Итак, рассмотрим, как меняются параметры a и b.Параметр a не изменяется, а b становится n-1.

Также есть третий аргумент l, которого не было в первом фрагменте.

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

Кроме того, эта часть 

    n    <- [a..b]
    True <- return $ (l - 1 <= n)

выглядит очень подозрительно.Это должно быть что-то вроде 

    n    <- [max a (l-1) .. b]

, так как выше будет учитываться от a до l-2 только для того, чтобы отбросить эти варианты в следующей строке.Создание вариантов только для их отмены может замедлить вашу программу.

...