Segmentos cuyos elementos cumplen una propiedad
Definir la función
|
1 |
segmentos :: (a -> Bool) -> [a] -> [[a]] |
tal que segmentos p xs es la lista de los segmentos de xs cuyos elementos verifican la propiedad p. Por ejemplo,
|
1 2 |
segmentos even [1,2,0,4,9,6,4,5,7,2] == [[2,0,4],[6,4],[2]] segmentos odd [1,2,0,4,9,6,4,5,7,2] == [[1],[9],[5,7]] |
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 |
import Data.List.Split (splitWhen) import Test.QuickCheck.HigherOrder (quickCheck') -- 1ª solución -- =========== segmentos1 :: (a -> Bool) -> [a] -> [[a]] segmentos1 _ [] = [] segmentos1 p (x:xs) | p x = takeWhile p (x:xs) : segmentos1 p (dropWhile p xs) | otherwise = segmentos1 p xs -- 2ª solución -- =========== segmentos2 :: (a -> Bool) -> [a] -> [[a]] segmentos2 p xs = filter (not .null) (splitWhen (not . p) xs) -- 3ª solución -- =========== segmentos3 :: (a -> Bool) -> [a] -> [[a]] segmentos3 = (filter (not . null) .) . splitWhen . (not .) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_segmentos :: (Int -> Bool) -> [Int] -> Bool prop_segmentos p xs = all (== segmentos1 p xs) [segmentos2 p xs, segmentos3 p xs] -- La comprobación es -- λ> quickCheck' prop_segmentos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (segmentos1 even [1..5*10^6]) -- 2500000 -- (2.52 secs, 2,080,591,088 bytes) -- λ> length (segmentos2 even [1..5*10^6]) -- 2500000 -- (0.78 secs, 2,860,591,688 bytes) -- λ> length (segmentos3 even [1..5*10^6]) -- 2500000 -- (0.82 secs, 2,860,592,000 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 |
from itertools import dropwhile, takewhile from sys import setrecursionlimit from timeit import Timer, default_timer from typing import Callable, TypeVar from more_itertools import split_at setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== def segmentos1(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]: if not xs: return [] if p(xs[0]): return [list(takewhile(p, xs))] + \ segmentos1(p, list(dropwhile(p, xs[1:]))) return segmentos1(p, xs[1:]) # 2ª solución # =========== def segmentos2(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]: return list(filter((lambda x: x), split_at(xs, lambda x: not p(x)))) # 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('segmentos1(lambda x: x % 2 == 0, range(10**4))') # 0.55 segundos # >>> tiempo('segmentos2(lambda x: x % 2 == 0, range(10**4))') # 0.00 segundos |