Definir la función
actualiza :: [a] -> [(Int,a)] -> [a] |
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,
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 |
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
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) |
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)