Понимание списка не даст правильного результата в Haskell - PullRequest
Новая
       6

Понимание списка не даст правильного результата в Haskell

2 голосов
/ 29 ноября 2009

Я делаю вопрос проекта Эйлера 136 , и придумал следующее, чтобы проверить приведенный пример: 

module Main where
import Data.List

unsum x y z n = (y > 0) && (z > 0) && (((x*x)  - (y*y)- (z*z)) == n) && ((x - y) == (y - z))
answer = snub $ takeWhile (<100) [n|x<-[1..],d<-[1..x`div`2],n<-[x..100],y<-[x-d],z<-[y-d], unsum x y z n ]
    where 
      snub [] = []
      snub (x:xs) | elem x xs = snub (filter (/=x) xs)
                  | otherwise = x : snub xs

snub удалит все дубликаты из списка.

Пример должен дать 25 решений для n, где x^2 - y^2 - z^2 == n, и все числа положительны (или я так понял из вопроса) и представляют собой арифметическую прогрессию, такую ​​что x-y == y-z. Но когда я использую код, возвращается список из 11 решений для n.

Что я сделал неправильно в моем понимании списка, и есть ли какие-то оптимизации, которые я пропустил?

1 Ответ

2 голосов
/ 30 ноября 2009

точка 1

Я попытался ответить на этот вопрос и обнаружил, что это была последовательность n с, которую я придумал 

[4,3,16,12,7,20,11,48,28,19,80,44,23,52,112,31,68,76,1156,43,176,559...

, что потенциально означает, что ваша takeWhile (<100) - это неправильная функция фильтрации, используемая для определения момента остановки. В связанной заметке я попытался запустить это: 

answer = snub $ filter (<=100) $ takeWhile (<200) [...listcomprehension...]

Но я сдался, потому что это заняло слишком много времени. Что приводит меня к пункту 2.

точка 2

С точки зрения оптимизации посмотрите на то, что дает ваше понимание списка с точки зрения необработанного вывода. 

Main> take 30 [(x,y,z,n) | x<-[1..], d<-[1..x`div`2], n<-[x..100], y<-[x-d], z<-[y-d]]
[(2,1,0,2),(2,1,0,3),(2,1,0,4),(2,1,0,5),(2,1,0,6),(2,1,0,7),(2,1,0,8),(2,1,0,9),
(2,1,0,10),(2,1,0,11),(2,1,0,12),(2,1,0,13),(2,1,0,14),(2,1,0,15),(2,1,0,16),(2,1,0,17),
(2,1,0,18),(2,1,0,19),(2,1,0,20),(2,1,0,21),(2,1,0,22),(2,1,0,23),(2,1,0,24),(2,1,0,25),
(2,1,0,26),(2,1,0,27),(2,1,0,28),(2,1,0,29),(2,1,0,30),(2,1,0,31)]

Это означает, что unsum вызывается для каждой комбинации x y z и n, что немного избыточно, так как мы знаем, что 2^2 - 1^2 - 0^2 = 3.

Также намного проще и гораздо менее избыточно перенести вычисление n из понимания списка (медленно из-за вышеописанного) в функцию и просто понять список комбинаций (x,y,z), которые действительны. 

ns = map nsum [(x, x-d, x-d-d) | x <- [1..], d <- [1..x`div`2]]
nsum (x,y,z) = x^2 - y^2 - z^2

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

...