Máximos locales

José A. Alonso

29-03-2024

Un máximo local de una lista es un elemento de la lista que es mayor que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).

Definir la función

   maximosLocales :: Ord a => [a] -> [a]

tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,

   maximosLocales [3,2,5,3,7,7,1,6,2]  ==  [5,6]
   maximosLocales [1..100]             ==  []
   maximosLocales "adbpmqexyz"         ==  "dpq"

1. Soluciones en Haskell

module Maximos_locales where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

-- 1ª solución
-- ===========

maximosLocales1 :: Ord a => [a] -> [a]
maximosLocales1 (x:y:z:xs)
  | y > x && y > z = y : maximosLocales1 (z:xs)
  | otherwise      = maximosLocales1 (y:z:xs)
maximosLocales1 _ = []

-- 2ª solución
-- ===========

maximosLocales2 :: Ord a => [a] -> [a]
maximosLocales2 xs =
  [y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y > x, y > z]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([Int] -> [Int]) -> Spec
specG maximosLocales = do
  it "e1" $
    maximosLocales [3,2,5,3,7,7,1,6,2]  `shouldBe`  [5,6]
  it "e2" $
    maximosLocales [1..100]             `shouldBe`  []

spec :: Spec
spec = do
  describe "def. 1" $ specG maximosLocales1
  describe "def. 2" $ specG maximosLocales2

-- La verificación es
--    λ> verifica
--
--    4 examples, 0 failures


-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_maximosLocales :: [Int] -> Property
prop_maximosLocales xs =
  maximosLocales1 xs === maximosLocales2 xs

-- La comprobación es
--    λ> quickCheck prop_maximosLocales
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> last (maximosLocales1 (take (6*10^6) (cycle "abc")))
--    'c'
--    (3.26 secs, 1,904,464,984 bytes)
--    λ> last (maximosLocales2 (take (6*10^6) (cycle "abc")))
--    'c'
--    (2.79 secs, 1,616,465,088 bytes)

2. Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución
# ===========

def maximosLocales1(xs: list[int]) -> list[int]:
    if len(xs) < 3:
        return []
    x, y, z, *ys = xs
    if y > x and y > z:
        return [y] + maximosLocales1([z] + ys)
    return maximosLocales1([y, z] + ys)

# 2ª solución
# ===========

def maximosLocales2(xs: list[int]) -> list[int]:
    ys: list[int] = []
    if len(xs) < 3:
        return ys
    for i in range(1, len(xs) - 1):
        if xs[i] > xs[i - 1] and xs[i] > xs[i + 1]:
            ys.append(xs[i])
    return ys

# 3ª solución
# ===========

def maximosLocales3(xs: list[int]) -> list[int]:
    return [y for x, y, z in zip(xs, xs[1:], xs[2:]) if y > x and y > z]

# Verificación
# ============

def test_maximosLocales() -> None:
    for maximosLocales in [maximosLocales1,
                           maximosLocales2,
                           maximosLocales3]:
        assert maximosLocales([3,2,5,3,7,7,1,6,2]) == [5,6]
        assert maximosLocales(list(range(0, 100))) == []
    print("Verificado")

# La verificación es
#    >>> test_maximosLocales()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()))
def test_maximosLocales_equiv(xs: list[int]) -> None:
    r = maximosLocales1(xs)
    assert maximosLocales2(xs) == r
    assert maximosLocales3(xs) == r

# La comprobación es
#    >>> test_maximosLocales_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('maximosLocales1([1,2,3]*(10**4))')
#    3.19 segundos
#    >>> tiempo('maximosLocales2([1,2,3]*(10**4))')
#    0.01 segundos
#    >>> tiempo('maximosLocales3([1,2,3]*(10**4))')
#    0.01 segundos
#
#    >>> tiempo('maximosLocales2([1,2,3]*(10**7))')
#    3.95 segundos
#    >>> tiempo('maximosLocales3([1,2,3]*(10**7))')
#    1.85 segundos