Suma de conjuntos de polinomios
Los conjuntos de polinomios se pueden representar por listas de listas de la misma longitud. Por ejemplo, los polinomios 3x²+5x+9, 10x³+9 y 8x³+5x²+x-1 se pueden representar por las listas [0,3,5,9], [10,0,0,9] y [8,5,1,-1].
Definir la función
|
1 |
sumaPolinomios :: Num a => [[a]] -> [a] |
tal que (sumaPolinomios ps) es la suma de los polinomios ps. Por ejemplo,
|
1 2 3 4 |
ghci> sumaPolinomios1 [[0,3,5,9],[10,0,0,9],[8,5,1,-1]] [18,8,6,17] ghci> sumaPolinomios6 (replicate 1000000 (replicate 3 1)) [1000000,1000000,1000000] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
import Data.List (transpose) import Data.Array ((!),accumArray,elems,listArray) -- 1ª definición (por recursión): sumaPolinomios1 :: Num a => [[a]] -> [a] sumaPolinomios1 [] = [] sumaPolinomios1 [xs] = xs sumaPolinomios1 (xs:ys:zss) = suma xs (sumaPolinomios1 (ys:zss)) -- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo, -- suma [4,7,3] [1,2,5] == [5,9,8] suma :: Num a => [a] -> [a] -> [a] suma [] [] = [] suma (x:xs) (y:ys) = x+y : suma xs ys -- 2ª definición (por recursión con zipWith): sumaPolinomios2 :: Num a => [[a]] -> [a] sumaPolinomios2 [] = [] sumaPolinomios2 [xs] = xs sumaPolinomios2 (xs:xss) = zipWith (+) xs (sumaPolinomios2 xss) -- 3ª definición (por plegado) sumaPolinomios3 :: Num a => [[a]] -> [a] sumaPolinomios3 = foldr1 (zipWith (+)) -- 4ª definición (por comprensión con transpose): sumaPolinomios4 :: Num a => [[a]] -> [a] sumaPolinomios4 xss = [sum xs | xs <- transpose xss] -- 5ª definición (con map y transpose): sumaPolinomios5 :: Num a => [[a]] -> [a] sumaPolinomios5 = map sum . transpose -- 6ª definición (con array) sumaPolinomios6 :: Num a => [[a]] -> [a] sumaPolinomios6 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]] where m = length xss n = length (head xss) p = listArray ((1,1),(m,n)) (concat xss) -- 7ª definición (con accumArray) sumaPolinomios7 :: Num a => [[a]] -> [a] sumaPolinomios7 xss = elems $ accumArray (+) 0 (1,n) (concat [zip [1..] xs | xs <- xss]) where n = length (head xss) -- Comparación de eficiencia -- ghci> sumaPolinomios1 (replicate 300000 (replicate 5 1)) -- [300000,300000,300000,300000,300000] -- (3.94 secs, 354713532 bytes) -- -- ghci> sumaPolinomios2 (replicate 300000 (replicate 5 1)) -- [300000,300000,300000,300000,300000] -- (2.08 secs, 185506908 bytes) -- -- ghci> sumaPolinomios3 (replicate 300000 (replicate 5 1)) -- [300000,300000,300000,300000,300000] -- (1.48 secs, 167026728 bytes) -- -- ghci> sumaPolinomios4 (replicate 300000 (replicate 5 1)) -- [300000,300000,300000,300000,300000] -- (1.08 secs, 148564752 bytes) -- -- ghci> sumaPolinomios5 (replicate 300000 (replicate 5 1)) -- [300000,300000,300000,300000,300000] -- (1.02 secs, 148062764 bytes) -- -- ghci> sumaPolinomios6 (replicate 300000 (replicate 5 1)) -- [300000,300000,300000,300000,300000] -- (3.17 secs, 463756028 bytes) -- -- ghci> sumaPolinomios7 (replicate 300000 (replicate 5 1)) -- [300000,300000,300000,300000,300000] -- (1.50 secs, 291699548 bytes) |