Máximos locales
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
|
1 |
maximosLocales :: Ord a => [a] -> [a] |
tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,
|
1 2 3 |
maximosLocales [3,2,5,3,7,7,1,6,2] == [5,6] maximosLocales [1..100] == [] maximosLocales "adbpmqexyz" == "dpq" |
1. Soluciones en Haskell
|
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 67 |
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
|
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
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 |