Diferencia conjuntista de listas
Definir la función
|
1 |
diferencia :: Eq a => [a] -> [a] -> [a] |
tal que diferencia xs ys es la diferencia de las listas sin elementos repetidos xs e ys. Por ejemplo,
|
1 2 |
diferencia [3,2,5,6] [5,7,3,4] == [2,6] diferencia [3,2,5] [5,7,3,2] == [] |
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 |
import Data.List (nub, sort, (\\)) import qualified Data.Set as S (fromList, toList, (\\) ) import Test.QuickCheck -- 1ª solución -- =========== diferencia1 :: Eq a => [a] -> [a] -> [a] diferencia1 xs ys = [x | x <- xs, x `notElem` ys] -- 2ª solución -- =========== diferencia2 :: Ord a => [a] -> [a] -> [a] diferencia2 [] _ = [] diferencia2 (x:xs) ys | x `elem` ys = xs `diferencia2` ys | otherwise = x : xs `diferencia2` ys -- 3ª solución -- =========== diferencia3 :: Ord a => [a] -> [a] -> [a] diferencia3 = (\\) -- 4ª solución -- =========== diferencia4 :: Ord a => [a] -> [a] -> [a] diferencia4 xs ys = S.toList (S.fromList xs S.\\ S.fromList ys) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_diferencia :: [Int] -> [Int] -> Bool prop_diferencia xs ys = all (== sort (xs' `diferencia1` ys')) [sort (xs' `diferencia2` ys'), sort (xs' `diferencia3` ys'), xs' `diferencia4` ys'] where xs' = nub xs ys' = nub ys -- La comprobación es -- λ> quickCheck prop_diferencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (diferencia1 [0..3*10^4] [1,3..3*10^4]) -- 15001 -- (3.39 secs, 9,553,528 bytes) -- λ> length (diferencia2 [0..3*10^4] [1,3..3*10^4]) -- 15001 -- (2.98 secs, 9,793,528 bytes) -- λ> length (diferencia3 [0..3*10^4] [1,3..3*10^4]) -- 15001 -- (3.61 secs, 11,622,502,792 bytes) -- λ> length (diferencia4 [0..3*10^4] [1,3..3*10^4]) -- 15001 -- (0.02 secs, 10,092,832 bytes) |
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 |
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 diferencia1(xs: list[A], ys: list[A]) -> list[A]: return [x for x in xs if x not in ys] # 2ª solución # =========== def diferencia2(xs: list[A], ys: list[A]) -> list[A]: if not xs: return [] if xs[0] in ys: return diferencia2(xs[1:], ys) return [xs[0]] + diferencia2(xs[1:], ys) # 3ª solución # =========== def diferencia3(xs: list[A], ys: list[A]) -> list[A]: zs = [] for x in xs: if x not in ys: zs.append(x) return zs # 4ª solución # =========== def diferencia4(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_diferencia(xs, ys): xs1 = list(set(xs)) ys1 = list(set(ys)) assert sorted(diferencia1(xs1, ys1)) ==\ sorted(diferencia2(xs1, ys1)) ==\ sorted(diferencia3(xs1, ys1)) ==\ sorted(diferencia4(xs1, ys1)) # La comprobación es # src> poetry run pytest -q diferencia_conjuntista_de_listas.py # 1 passed in 0.39s # 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('diferencia1(list(range(0,20000)), list(range(1,20000,2)))') # 0.89 segundos # >>> tiempo('diferencia2(list(range(0,20000)), list(range(1,20000,2)))') # 2.11 segundos # >>> tiempo('diferencia3(list(range(0,20000)), list(range(1,20000,2)))') # 1.06 segundos # >>> tiempo('diferencia4(list(range(0,20000)), list(range(1,20000,2)))') # 0.01 segundos |
El código se encuentra en GitHub.