Los sufijos de la lista [3,7,2,5,4,6] son
|
1 2 3 4 5 6 7 |
[3,7,2,5,4,6] [7,2,5,4,6] [2,5,4,6] [5,4,6] [4,6] [6] [] |
y la lista de sus sumas es [27,24,17,15,10,6,0].
Definir la función
|
1 |
sumasParciales :: [Integer] -> [Integer] |
tal que (sumasParciales xs) es la lista de las sumas de los sufijos de xs. Por ejemplo,
|
1 2 3 |
sumasParciales [3,7,2,5,4,6] == [27,24,17,15,10,6,0] sumasParciales [1..10] == [55,54,52,49,45,40,34,27,19,10,0] sum (sumasParciales [1..5*10^6]) == 41666679166667500000 |
|
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 |
import Data.List (tails) -- 1ª solución sumasParciales1 :: [Integer] -> [Integer] sumasParciales1 xs = map sum (tails xs) -- 2ª solución sumasParciales2 :: [Integer] -> [Integer] sumasParciales2 [] = [0] sumasParciales2 (x:xs) = (x + s):s:ss where (s:ss) = sumasParciales2 xs -- 3ª solución sumasParciales3 :: [Integer] -> [Integer] sumasParciales3 = foldr (\x (s:ss) -> (x + s) : (s:ss)) [0] -- 4ª solución sumasParciales4 :: [Integer] -> [Integer] sumasParciales4 xs = scanl (-) (sum xs) xs -- 5ª solución sumasParciales5 :: [Integer] -> [Integer] sumasParciales5 xs = reverse (0 : scanl1 (+) (reverse xs)) -- 6ª solución sumasParciales6 :: [Integer] -> [Integer] sumasParciales6 = scanr (+) 0 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sum (sumasParciales1 [1..3*10^4]) -- 9000450005000 -- (19.70 secs, 40,132,872,616 bytes) -- λ> sum (sumasParciales2 [1..3*10^4]) -- 9000450005000 -- (0.04 secs, 16,932,840 bytes) -- λ> sum (sumasParciales3 [1..3*10^4]) -- 9000450005000 -- (0.02 secs, 13,880,608 bytes) -- λ> sum (sumasParciales4 [1..3*10^4]) -- 9000450005000 -- (0.03 secs, 12,178,080 bytes) -- λ> sum (sumasParciales5 [1..3*10^4]) -- 9000450005000 -- (0.02 secs, 9,974,600 bytes) -- λ> sum (sumasParciales6 [1..3*10^4]) -- 9000450005000 -- (0.02 secs, 10,694,368 bytes) -- -- λ> sum (sumasParciales2 [1..3*10^6]) -- 9000004500000500000 -- (3.13 secs, 1,685,139,696 bytes) -- λ> sum (sumasParciales3 [1..3*10^6]) -- 9000004500000500000 -- (2.37 secs, 1,380,492,448 bytes) -- λ> sum (sumasParciales4 [1..3*10^6]) -- 9000004500000500000 -- (1.84 secs, 1,211,188,264 bytes) -- λ> sum (sumasParciales5 [1..3*10^6]) -- 9000004500000500000 -- (1.22 secs, 987,790,392 bytes) -- λ> sum (sumasParciales6 [1..3*10^6]) -- 9000004500000500000 -- (1.34 secs, 1,059,792,344 bytes) -- -- λ> sum (sumasParciales5 [1..5*10^6]) -- 41666679166667500000 -- (2.36 secs, 1,844,332,576 bytes) -- λ> sum (sumasParciales6 [1..5*10^6]) -- 41666679166667500000 -- (2.03 secs, 1,964,365,912 bytes) |