Haskell — понимание списка не может перечислить N × N

Мне нужно написать функцию, которая возвращает список всех пар (x,y), где x, y ∈ N , и:

  • x — произведение двух натуральных чисел (x = a • b, где a, b ∈ N) и
  • x действительно больше 5, но меньше 500, и
  • y — квадратное число (y = c², где c ∈ N), НЕ превышающее 1000, и
  • х является делителем у.

Моя попытка:

listPairs :: [(Int, Int)] 
listPairs = [(a*b, y) | y <- [0..], a <- [0..], b <- [0..], 
                        (a*b) > 5, (a*b) < 500, (y*y) < 1001, 
                        mod y (a*b) == 0]

Но он ничего не возвращает и компьютер много работает на нем.

Однако, если я выберу меньший диапазон для a, b и y e. грамм. [0..400], это занимает до минуты, но возвращает правильный результат.

Итак, как я могу решить проблему с производительностью?


list performance list-comprehension haskell
person John    schedule 14.05.2013    source источник
comment
-1 вы уже получили массу помощи от Haskell Cafe, пожалуйста, не переходите с сайта на сайт с просьбой о помощи (Дэнни Гратцер)   -  person Daniel Gratzer    schedule 15.05.2013
comment
Для справки для тех, кто не знает, о чем я говорю, ОП задал этот вопрос и подробно ответил уже сегодня днем ​​(groups.google.com/forum/?fromgroups=#!topic/haskell-cafe/)   -  person Daniel Gratzer    schedule 15.05.2013
comment
400 слишком низкий. вы должны убедиться, что не пропустили ни одного правильного решения: (a*b)<500, (a*b)>5, a==1, b==499 непротиворечиво. Поэтому используйте [1..499] (0*x > 5 никогда не бывает истинным). OTOH (y*y) < 1001 ==> y < 32 поэтому используйте y<-[1..31], a<-[1..499]. Должно сделать это в 32 раза быстрее. Затем a*b < 500 и a*b==b*a, поэтому используйте b<-[a..min 499 (div 500 a)], что дает нам еще одно значительное уменьшение размера задачи. Теперь это занимает меньше секунды.   -  person Will Ness    schedule 15.05.2013
comment
Кстати, согласно вашему описанию, вы должны вернуть [(a*b, y*y) | .... y вашего кода соответствует вашему описанию.   -  person Will Ness    schedule 15.05.2013
comment
указанный дубликат отвечает на другой вопрос. Этот вопрос конкретный, тот общий.   -  person Will Ness    schedule 15.05.2013
comment
@WillNess: опубликуйте свой комментарий в качестве ответа!   -  person sclv    schedule 21.05.2013
comment
@sclv готово! (раньше он был закрыт, не так ли?)   -  person Will Ness    schedule 21.05.2013
comment
@WillNess: вполне возможно :-)   -  person sclv    schedule 21.05.2013

Ответы (1)


arrow_upward
1
arrow_downward

Итак, конечно, вложенные списки в бесконечных списках не прекращаются.

К счастью, ваши списки не бесконечны. Есть предел. Если x = a*b < 500, то мы знаем, что это должны быть a < 500 и b < 500. Кроме того, c = y*y < 1001 — это просто y < 32. Так,

listPairs :: [(Int, Int)] 
listPairs = 
    [(x, c*c) | c <- [1..31], a <- [1..499],    -- a*b < 500 ==> b<500/a ,
                b <- [a..min 499 (div 500 a)],  -- a*b==b*a  ==> b >= a
                let x = a*b, x > 5,  
                -- (a*b) < 500, (c*c) < 1001,   -- no need to test this
                rem (c*c) x == 0]

mod 0 n == 0 тривиально выполняется, поэтому я исключаю здесь 0 из «натуральных чисел».

Здесь по-прежнему создаются дубликаты, даже несмотря на то, что мы ограничили значение b значением b >= a в x=a*b, потому что x может иметь несколько представлений (например, 1*6 == 2*3).

Вы можете использовать Data.List.nub, чтобы избавиться от них.

person Will Ness    schedule 21.05.2013