Máximos locales

José A. Alonso

19-02-2025

Un máximo local de una lista es un elemento de la lista que es 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"

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Soluciones

A continuación se muestran

las soluciones en Haskell,
las soluciones en Python y
las soluciones en Common Lisp

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

3. Soluciones en Common Lisp

(ql:quickload "fiveam" :silent t)

(defpackage :maximos-locales
  (:use :cl
        :fiveam))

(in-package :maximos-locales)

;;; 1ª solución
;;; ===========

(defun maximos-locales1 (xs)
  (cond
    ((>= (length xs) 3)
     (let ((x (first xs))
           (y (second xs))
           (z (third xs)))
       (if (and (> y x) (> y z))
           (cons y (maximos-locales1 (cddr xs)))
           (maximos-locales1 (cdr xs)))))
    (t ())))

;;; 2ª solución
;;; ===========

(defun maximos-locales2 (xs)
  (cond
    ((null (cddr xs)) nil)
    (t (let ((x (first xs))
             (y (second xs))
             (z (third xs)))
         (if (and (> y x) (> y z))
             (cons y (maximos-locales2 (cddr xs)))
             (maximos-locales2 (cdr xs)))))))

;;; 3ª solución
;;; ===========

;;; (zip l1 ... ln) es la lista de las listas de los elementos de las
;;; listas l1,..., ln en la misma posición. Por ejemplo,
;;;    > (zip '(1 2 3 4) '(a b c) '("x" "y" "z"))
;;;    ((1 A "x") (2 B "y") (3 C "z"))
(defun zip (&rest listas)
  (apply #'mapcar #'list listas))

(defun maximos-locales3 (lista)
  (let ((ternas (zip lista (cdr lista) (cddr lista))))
    (loop for (x y z) in ternas
          when (and (> y x) (> y z))
            collect y)))

;;; 4ª solución
;;; ===========

(defun maximos-locales4 (xs)
  (let ((resultado '()))
    (loop for (x y z) on xs
          while (and y z)
          do (cond ((and (> y x) (> y z))
                    (push y resultado)
                    (setf xs (cddr xs)))
                   (t (setf xs (cdr xs)))))
    (nreverse resultado)))

;;; Verificación
;;; ============

(test maximos-locales
  (mapc (lambda (maximos-locales)
          (is (equal (funcall maximos-locales '(3 2 5 3 7 7 1 6 2))
                     '(5 6)))
          (is (equal (funcall maximos-locales '(7 1 2 3))
                     nil)))
        '(maximos-locales1
          maximos-locales2
          maximos-locales3
          maximos-locales4
          )))

(defun verifica ()
  (run 'maximos-locales))

;;; La verificación es
;;;    (verifica)
;;;
;;;    Running test MAXIMOS-LOCALES ........

;;; Comprobación de equivalencia
;;; ============================

;;; La propiedad es
(test maximos-locales-equiv
  (for-all ((xs (gen-list)))
    (let ((ys (maximos-locales1 xs)))
      (is (equal ys (maximos-locales2 xs)))
      (is (equal ys (maximos-locales3 xs)))
      (is (equal ys (maximos-locales4 xs))))))

(defun comprueba ()
  (run 'maximos-locales-equiv))

;;; La comprobación es
;;;    > (comprueba)
;;;
;;;    Running test MAXIMOS-LOCALES-EQUIV ...

;;; Comparación de eficiencia
;;; =========================

;;; (ejemplo n) es la lista obtenida repitiendo n veces los elementos 1,
;;; 2 y 3. Por ejemplo,
;;;    > (ejemplo 2)
;;;    (1 2 3 1 2 3)
(defun ejemplo (n)
  (reduce #'append
          (make-list n :initial-element '(1 2 3))
          :initial-value '()
          :from-end t))

;;; La comparación es
;;;    > (time (last (maximos-locales1 (ejemplo 10000))))
;;;    0.600 seconds of real time
;;;    > (time (last (maximos-locales2 (ejemplo 10000))))
;;;    0.003 seconds of real time
;;;    > (time (last (maximos-locales3 (ejemplo 10000))))
;;;    0.005 seconds of real time
;;;    > (time (last (maximos-locales4 (ejemplo 10000))))
;;;    0.001 seconds of real time
;;;
;;;    > (time (last (maximos-locales3 (ejemplo 2000000))))
;;;    1.161 seconds of real time
;;;    > (time (last (maximos-locales4 (ejemplo 2000000))))
;;;    0.588 seconds of real time