Actualización de una lista
Definir la función
|
1 |
actualiza :: [a] -> [(Int,a)] -> [a] |
tal que (actualiza xs ps) es la lista obtenida sustituyendo en xs los elementos cuyos índices son las primeras componentes de ps por las segundas. Por ejemplo,
|
1 2 |
actualiza [3,5,2,4] [(2,1),(0,7)] == [7,5,1,4] sum (actualiza [1..10^4] [(i,2*i) | i <- [0..10^4-1]]) == 99990000 |
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 |
import qualified Data.Vector as V import Data.Array -- 1ª solución (por recursión) -- =========================== actualiza :: [a] -> [(Int,a)] -> [a] actualiza xs [] = xs actualiza xs ((n,y):ps) = actualiza (actualizaE xs (n,y)) ps -- (actualizaE xs (n,y)) es la lista obtenida sustituyendo el elemento -- n-ésimo de xs por y. Por ejemplo, -- actualiza [3,5,2,4] (2,1) == [3,5,1,4] actualizaE :: [a] -> (Int,a) -> [a] actualizaE xs (n,y) = take n xs ++ y : drop (n+1) xs -- 2ª solución (por tablas) -- ======================== actualiza2 :: [a] -> [(Int,a)] -> [a] actualiza2 xs ps = elems (listArray (0,length xs - 1) xs // ps) -- 3ª solución (por vectores) -- ========================== actualiza3 :: [a] -> [(Int,a)] -> [a] actualiza3 xs ps = V.toList (V.fromList xs V.// ps) -- Comparación de eficiencia -- ghci> let n = 10^2 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]] -- 9900 -- (0.02 secs, 4668984 bytes) -- ghci> let n = 10^3 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]] -- 999000 -- (0.28 secs, 77454496 bytes) -- ghci> let n = 10^4 in sum $ actualiza [1..n] [(i,2*i) | i <- [0..n-1]] -- 99990000 -- (63.46 secs, 8769501704 bytes) -- -- ghci> let n = 10^2 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]] -- 9900 -- (0.02 secs, 4147304 bytes) -- ghci> let n = 10^3 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]] -- 999000 -- (0.02 secs, 4694784 bytes) -- ghci> let n = 10^4 in sum $ actualiza2 [1..n] [(i,2*i) | i <- [0..n-1]] -- 99990000 -- (0.05 secs, 12276800 bytes) -- -- ghci> let n = 10^2 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]] -- 9900 -- (0.01 secs, 4147304 bytes) -- ghci> let n = 10^3 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]] -- 999000 -- (0.02 secs, 4682680 bytes) -- ghci> let n = 10^4 in sum $ actualiza3 [1..n] [(i,2*i) | i <- [0..n-1]] -- 99990000 -- (0.04 secs, 12595224 bytes) |