Vectores

Posiciones de máximos locales

PorJosé A. Alonso 28-marzo-20164-abril-2016

Los vectores se definen usando tablas como sigue:

   type Vector a = Array Int a

1	type Vector a = Array Int a

Un elemento de un vector es un máximo local si no tiene ningún elemento adyacente mayor o igual que él.

Definir la función

   posMaxVec :: Ord a => Vector a -> [Int]

1	posMaxVec :: Ord a => Vector a -> [Int]

tal que (posMaxVec p) devuelve las posiciones del vector p en las que p tiene un máximo local. Por ejemplo,

   posMaxVec (listArray (1,6) [3,2,6,7,5,3]) == [1,4]
   posMaxVec (listArray (1,2) [5,5])         == []
   posMaxVec (listArray (1,1) [5])           == [1]

posMaxVec (listArray (1,6) [3,2,6,7,5,3]) == [1,4]

posMaxVec (listArray (1,2) [5,5]) == []

posMaxVec (listArray (1,1) [5]) == [1]

Soluciones

import Data.Array

type Vector a = Array Int a

-- 1ª definición
posMaxVec :: Ord a => Vector a -> [Int]
posMaxVec p 
    | n == 1 = [1]
    | otherwise = 
        (if p!1 > p!2 then [1] else []) ++ 
        [i | i <- [2..n-1], p!(i-1) < p!i && p!(i+1) < p!i] ++
        (if p!(n-1) < p!n then [n] else [])
    where (_,n) = bounds p

-- 2ª definición
posMaxVec2 :: Ord a => Vector a -> [Int]
posMaxVec2 p  
    | n == 1 = [1]
    | otherwise = 
        [1 | p ! 1 > p ! 2] ++ 
        [i | i <- [2..n-1], p!(i-1) < p!i && p!(i+1) < p!i] ++
        [n | p ! (n - 1) < p ! n]
    where (_,n) = bounds p

-- 3ª definición
posMaxVec3 :: Ord a => Vector a -> [Int]
posMaxVec3 p  
    | n == 1    = [1]
    | otherwise = [i | i <- [1..n],
                       all (<p!i) [p!j | j <- vecinos i]]
    where (_,n) = bounds p
          vecinos 1 = [2]
          vecinos j | j == n    = [n-1]
                    | otherwise = [j-1,j+1]

-- 4ª definición
posMaxVec4 :: Ord a => Vector a -> [Int]
posMaxVec4 p = [i | (i,x) <- assocs p
                  , i == a || p!(i-1) < x
                  , i == b || p!(i+1) < x ]
    where (a,b) = bounds p

import Data.Array

type Vector a = Array Int a

-- 1ª definición

posMaxVec :: Ord a => Vector a -> [Int]

posMaxVec p

| n == 1 = [1]

| otherwise =

(if p!1 > p!2 then [1] else []) ++

[i | i <- [2..n-1], p!(i-1) < p!i && p!(i+1) < p!i] ++

(if p!(n-1) < p!n then [n] else [])

where (_,n) = bounds p

-- 2ª definición

posMaxVec2 :: Ord a => Vector a -> [Int]

posMaxVec2 p

| n == 1 = [1]

| otherwise =

[1 | p ! 1 > p ! 2] ++

[i | i <- [2..n-1], p!(i-1) < p!i && p!(i+1) < p!i] ++

[n | p ! (n - 1) < p ! n]

where (_,n) = bounds p

-- 3ª definición

posMaxVec3 :: Ord a => Vector a -> [Int]

posMaxVec3 p

| n == 1 = [1]

| otherwise = [i | i <- [1..n],

all (<p!i) [p!j | j <- vecinos i]]

where (_,n) = bounds p

vecinos 1 = [2]

vecinos j | j == n = [n-1]

| otherwise = [j-1,j+1]

-- 4ª definición

posMaxVec4 :: Ord a => Vector a -> [Int]

posMaxVec4 p = [i | (i,x) <- assocs p

, i == a || p!(i-1) < x

, i == b || p!(i+1) < x ]

where (a,b) = bounds p

Actualización de una lista

PorJosé A. Alonso 10-marzo-20152-mayo-2016

Definir la función

   actualiza :: [a] -> [(Int,a)] -> [a]

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,

   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

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

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)

Posición del primer falso en un vector

PorJosé A. Alonso 29-enero-201526-marzo-2022

Excercitium

Definir la función

   posicion :: Array Int Bool -> Maybe Int

1	posicion :: Array Int Bool -> Maybe Int

tal que (posicion v) es la menor posición del vector de booleanos v cuyo valor es falso y es Nothing si todos los valores son verdaderos. Por ejemplo,

   posicion (listArray (0,4) [True,True,False,True,False]) == Just 2
   posicion (listArray (0,4) [i <= 2 | i <- [0..4]])       == Just 3
   posicion (listArray (0,4) [i <= 7 | i <- [0..4]])       == Nothing

posicion (listArray (0,4) [True,True,False,True,False]) == Just 2

posicion (listArray (0,4) [i <= 2 | i <- [0..4]]) == Just 3

posicion (listArray (0,4) [i <= 7 | i <- [0..4]]) == Nothing

Soluciones

import Data.Array 

-- 1ª definición:
posicion :: Array Int Bool -> Maybe Int
posicion v | p > n     = Nothing
           | otherwise = Just p
    where p = (length . takeWhile id . elems) v
          (_,n) = bounds v 

-- 2ª posición:
posicion2 :: Array Int Bool -> Maybe Int
posicion2 v | null xs   = Nothing
            | otherwise = Just (head xs)
    where xs = [i | i <- indices v, v!i]

import Data.Array

-- 1ª definición:

posicion :: Array Int Bool -> Maybe Int

posicion v | p > n = Nothing

| otherwise = Just p

where p = (length . takeWhile id . elems) v

(_,n) = bounds v

-- 2ª posición:

posicion2 :: Array Int Bool -> Maybe Int

posicion2 v | null xs = Nothing

| otherwise = Just (head xs)

where xs = [i | i <- indices v, v!i]

Posiciones de máximos locales

Soluciones

Actualización de una lista

Soluciones

Posición del primer falso en un vector

Excercitium

Soluciones

Entradas recientes

Buscar

Correo electrónico