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

Я решал довольно простую задачу: генерация всех убывающих последовательностей длиной 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 или есть какая-то другая причина?


combinatorics haskell pattern-matching do-notation
person Zhiltsoff Igor    schedule 03.03.2019    source источник
comment
1. Почему True <- return foo вместо guard foo? 2. Зачем передавать a, если оно никогда не меняется по сравнению с его первоначальным значением 1? 3. Почему n <- [1..b]; guard (l-1 <= n) вместо n <- [max 1 (l-1)..n] или даже n <- [l-1 .. n], если вы не боитесь таких рефакторингов?   -  person Daniel Wagner    schedule 04.03.2019
comment
@DanielWagner Я понимаю, что второй фрагмент написан крайне плохо, меня интересовало именно ядро. Тем не менее, ошибка была чрезвычайно неловкой. Спасибо за вашу помощь!   -  person Zhiltsoff Igor    schedule 05.03.2019

Ответы (2)


arrow_upward
1
arrow_downward

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

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

person Daniel Wagner    schedule 04.03.2019

arrow_upward
2
arrow_downward

Две функции, похоже, имеют совершенно разную реализацию:

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 только для того, чтобы отбросить эти варианты в следующей строке. Генерация вариантов только для того, чтобы отбросить их, может замедлить работу вашей программы.

person chi    schedule 03.03.2019
comment
Почему, привет. Извините за странный вид моего кода :). Единственная разница в этих двух алгоритмах заключается в том, что один изменяет правую и левую границы, а второй изменяет правую границу и отфильтровывает неподходящие значения n посредством сопоставления с образцом. Вы сказали, что я вызываю дополнительные рекурсивные вызовы, но это не кажется правильным, поскольку мы каждый раз отфильтровываем одни и те же значения, но используем для этого разные инструменты. Таким образом, я думаю, мой код был слишком плох, чтобы это увидеть, но, похоже, это не так. (У меня закончились слова, будет вторая половина этого комментария). - person Zhiltsoff Igor; 03.03.2019
comment
(Часть 2: извините за это). ›Генерация вариантов выбора только для того, чтобы их отбросить, может замедлить работу вашей программы. Да, это то, что я пытался выразить, когда говорил об избыточном использовании функции enumFromTo, но меня просто застали врасплох +65 секунд. Просто мне кажется, что есть какая-то другая проблема, которую я не могу обнаружить. Огромное спасибо за ваше время! - person Zhiltsoff Igor; 03.03.2019
comment
@ZhiltsoffIgor Возможно, вы могли бы попытаться выяснить, сколько значений на самом деле отбрасывается. Если их много, они могут сделать код намного медленнее. Например. [1..100] намного быстрее, чем filter (>0) [-1000000000..100] - person chi; 03.03.2019
comment
Выяснение количества отброшенных значений звучит как приятное упражнение, но не такое уж простое, по крайней мере для меня, поскольку, очевидно, мы не можем одновременно использовать и List, и State Monad. Было предположение, что может существовать какой-то силовой метод подсчета с помощью GHCi, но еще предстоит провести некоторые исследования. Возможно, вы знаете какой-нибудь более элегантный способ? В любом случае, я думаю, мы получили ответ от @DanielWagner. Не знаю, как l перепутали с l - 1, но так, в конце концов, и было. Спасибо за ваше время! - person Zhiltsoff Igor; 05.03.2019
comment
@ZhiltsoffIgor В этом конкретном случае вы можете напечатать a и l-1, используя Debug.Trace.trace, чтобы увидеть, сильно ли они отличаются. Это может привести к большому объему отладочной информации, если вызовов много. - person chi; 05.03.2019
comment
По-моему, 23527350 значений. Около 10^7; кажется правильным. - person Zhiltsoff Igor; 06.03.2019