Unión conjuntista de listas
Definir la función
|
1 |
union :: Ord a => [a] -> [a] -> [a] |
tal que union xs ys es la unión de las listas, sin elementos repetidos, xs e ys. Por ejemplo,
|
1 |
union [3,2,5] [5,7,3,4] == [3,2,5,7,4] |
Comprobar con QuickCheck que la unión es conmutativa.
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 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 |
import Data.List (nub, sort, union) import qualified Data.Set as S (fromList, toList, union) import Test.QuickCheck -- 1ª solución -- =========== union1 :: Ord a => [a] -> [a] -> [a] union1 xs ys = xs ++ [y | y <- ys, y `notElem` xs] -- 2ª solución -- =========== union2 :: Ord a => [a] -> [a] -> [a] union2 [] ys = ys union2 (x:xs) ys | x `elem` ys = xs `union2` ys | otherwise = x : xs `union2` ys -- 3ª solución -- =========== union3 :: Ord a => [a] -> [a] -> [a] union3 = union -- 4ª solución -- =========== union4 :: Ord a => [a] -> [a] -> [a] union4 xs ys = S.toList (S.fromList xs `S.union` S.fromList ys) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_union :: [Int] -> [Int] -> Bool prop_union xs ys = all (== sort (xs' `union1` ys')) [sort (xs' `union2` ys'), sort (xs' `union3` ys'), xs' `union4` ys'] where xs' = nub xs ys' = nub ys -- La comprobación es -- λ> quickCheck prop_union -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (union1 [0,2..3*10^4] [1,3..3*10^4]) -- 30001 -- (2.37 secs, 7,153,536 bytes) -- λ> length (union2 [0,2..3*10^4] [1,3..3*10^4]) -- 30001 -- (2.38 secs, 6,553,752 bytes) -- λ> length (union3 [0,2..3*10^4] [1,3..3*10^4]) -- 30001 -- (11.56 secs, 23,253,553,472 bytes) -- λ> length (union4 [0,2..3*10^4] [1,3..3*10^4]) -- 30001 -- (0.04 secs, 10,992,056 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_union_conmutativa :: [Int] -> [Int] -> Bool prop_union_conmutativa xs ys = iguales (xs `union1` ys) (ys `union1` xs) -- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo, -- iguales [3,2,3] [2,3] == True -- iguales [3,2,3] [2,3,2] == True -- iguales [3,2,3] [2,3,4] == False -- iguales [2,3] [4,5] == False iguales :: Ord a => [a] -> [a] -> Bool iguales xs ys = S.fromList xs == S.fromList ys -- La comprobación es -- λ> quickCheck prop_union_conmutativa -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.
|
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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
from typing import TypeVar from timeit import Timer, default_timer from sys import setrecursionlimit from hypothesis import given, strategies as st setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== def union1(xs: list[A], ys: list[A]) -> list[A]: return xs + [y for y in ys if y not in xs] # 2ª solución # =========== def union2(xs: list[A], ys: list[A]) -> list[A]: if not xs: return ys if xs[0] in ys: return union2(xs[1:], ys) return [xs[0]] + union2(xs[1:], ys) # 3ª solución # =========== def union3(xs: list[A], ys: list[A]) -> list[A]: zs = ys[:] for x in xs: if x not in ys: zs.append(x) return zs # 4ª solución # =========== def union4(xs: list[A], ys: list[A]) -> list[A]: return list(set(xs) | set(ys)) # Comprobación de equivalencia # ============================ # # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_union(xs, ys): xs1 = list(set(xs)) ys1 = list(set(ys)) assert sorted(union1(xs1, ys1)) ==\ sorted(union2(xs1, ys1)) ==\ sorted(union3(xs1, ys1)) ==\ sorted(union4(xs1, ys1)) # La comprobación es # src> poetry run pytest -q union_conjuntista_de_listas.py # 1 passed in 0.36s # Comparación de eficiencia # ========================= def tiempo(e): """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('union1(list(range(0,30000,2)), list(range(1,30000,2)))') # 1.30 segundos # >>> tiempo('union2(list(range(0,30000,2)), list(range(1,30000,2)))') # 2.84 segundos # >>> tiempo('union3(list(range(0,30000,2)), list(range(1,30000,2)))') # 1.45 segundos # >>> tiempo('union4(list(range(0,30000,2)), list(range(1,30000,2)))') # 0.00 segundos # Comprobación de la propiedad # ============================ # iguales(xs, ys) se verifica si xs e ys son iguales como conjuntos. Por # ejemplo, # iguales([3,2,3], [2,3]) == True # iguales([3,2,3], [2,3,2]) == True # iguales([3,2,3], [2,3,4]) == False # iguales([2,3], [4,5]) == False def iguales(xs: list[A], ys: list[A]) -> bool: return set(xs) == set(ys) # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_union_conmutativa(xs, ys): xs1 = list(set(xs)) ys1 = list(set(ys)) assert iguales(union1(xs1, ys1), union1(ys1, xs1)) # La comprobación es # src> poetry run pytest -q union_conjuntista_de_listas.py # 2 passed in 0.49s |
El código se encuentra en GitHub