Máximo de una lista
Definir la función
|
1 |
maximo :: Ord a => [a] -> a |
tal que maximo xs es el máximo de la lista xs. Por ejemplo,
|
1 2 3 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
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) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
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 |