Menu Close

Día: 22 noviembre, 2022

Máximo de una lista

José A. Alonso, ,

Definir la función

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

tal que maximo xs es el máximo de la lista xs. Por ejemplo,

   maximo [3,7,2,5]                  ==  7
   maximo ["todo","es","falso"]      ==  "todo"
   maximo ["menos","alguna","cosa"]  ==  "menos"

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Data.List (foldl1')
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
maximo1 :: Ord a => [a] -> a
maximo1 [x]      = x
maximo1 (x:y:ys) = max x (maximo1 (y:ys))
 
-- 2ª solución
-- ===========
 
maximo2 :: Ord a => [a] -> a
maximo2 = foldr1 max
 
-- 3ª solución
-- ===========
 
maximo3 :: Ord a => [a] -> a
maximo3 = foldl1' max
 
-- 4ª solución
-- ===========
 
maximo4 :: Ord a => [a] -> a
maximo4 = maximum
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_maximo :: NonEmptyList Int -> Bool
prop_maximo (NonEmpty xs) =
  all (== maximo1 xs)
      [maximo2 xs,
       maximo3 xs]
 
-- La comprobación es
--    λ> quickCheck prop_maximo
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> maximo1 [0..5*10^6]
--    5000000
--    (3.42 secs, 1,783,406,728 bytes)
--    λ> maximo2 [0..5*10^6]
--    5000000
--    (0.80 secs, 934,638,080 bytes)
--    λ> maximo3 [0..5*10^6]
--    5000000
--    (0.12 secs, 360,591,360 bytes)
--    λ> maximo4 [0..5*10^6]
--    5000000
--    (1.40 secs, 892,891,608 bytes)


Soluciones en Python

from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar, Union
 
from hypothesis import given
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
A = TypeVar('A', bound=Union[int, float, str])
 
# 1ª solución
# ===========
 
def maximo1(xs: list[A]) -> A:
    if len(xs) == 1:
        return xs[0]
    return max(xs[0], maximo1(xs[1:]))
 
# 2ª solución
# ===========
 
def maximo2(xs: list[A]) -> A:
    return reduce(max, xs)
 
# 3ª solución
# ===========
 
def maximo3(xs: list[A]) -> A:
    return max(xs)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(st.integers(), min_size=2))
def test_maximo(xs: list[int]) -> None:
    r = maximo1(xs)
    assert maximo2(xs) == r
    assert maximo3(xs) == r
 
# La comprobación es
#    src> poetry run pytest -q maximo_de_una_lista.py
#    1 passed in 0.33s
 
# 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('maximo1(range(2*10**4))')
#    0.03 segundos
#    >>> tiempo('maximo2(range(2*10**4))')
#    0.00 segundos
#    >>> tiempo('maximo3(range(2*10**4))')
#    0.00 segundos
#
#    >>> tiempo('maximo2(range(5*10**6))')
#    0.38 segundos
#    >>> tiempo('maximo3(range(5*10**6))')
#    0.21 segundos
Leer más →