Intersección conjuntista de listas
Definir la función
|
1 |
interseccion :: Eq a => [a] -> [a] -> [a] |
tal que interseccion xs ys es la intersección de las listas sin elementos repetidos xs e ys. Por ejemplo,
|
1 2 |
interseccion [3,2,5] [5,7,3,4] == [3,5] interseccion [3,2,5] [9,7,6,4] == [] |
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 |
import Data.List (nub, sort, intersect) import qualified Data.Set as S (fromList, toList, intersection ) import Test.QuickCheck -- 1ª solución -- =========== interseccion1 :: Eq a => [a] -> [a] -> [a] interseccion1 xs ys = [x | x <- xs, x `elem` ys] -- 2ª solución -- =========== interseccion2 :: Ord a => [a] -> [a] -> [a] interseccion2 [] _ = [] interseccion2 (x:xs) ys | x `elem` ys = x : xs `interseccion2` ys | otherwise = xs `interseccion2` ys -- 3ª solución -- =========== interseccion3 :: Ord a => [a] -> [a] -> [a] interseccion3 = intersect -- 4ª solución -- =========== interseccion4 :: Ord a => [a] -> [a] -> [a] interseccion4 xs ys = S.toList (S.fromList xs `S.intersection` S.fromList ys) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_interseccion :: [Int] -> [Int] -> Bool prop_interseccion xs ys = all (== sort (xs' `interseccion1` ys')) [sort (xs' `interseccion2` ys'), sort (xs' `interseccion3` ys'), xs' `interseccion4` ys'] where xs' = nub xs ys' = nub ys -- La comprobación es -- λ> quickCheck prop_interseccion -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (interseccion1 [0..3*10^4] [1,3..3*10^4]) -- 15000 -- (2.94 secs, 6,673,360 bytes) -- λ> length (interseccion2 [0..3*10^4] [1,3..3*10^4]) -- 15000 -- (3.04 secs, 9,793,440 bytes) -- λ> length (interseccion3 [0..3*10^4] [1,3..3*10^4]) -- 15000 -- (5.39 secs, 6,673,472 bytes) -- λ> length (interseccion4 [0..3*10^4] [1,3..3*10^4]) -- 15000 -- (0.04 secs, 8,593,176 bytes) |
El código se encuentra en GitHub.
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 |
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 interseccion1(xs: list[A], ys: list[A]) -> list[A]: return [x for x in xs if x in ys] # 2ª solución # =========== def interseccion2(xs: list[A], ys: list[A]) -> list[A]: if not xs: return [] if xs[0] in ys: return [xs[0]] + interseccion2(xs[1:], ys) return interseccion2(xs[1:], ys) # 3ª solución # =========== def interseccion3(xs: list[A], ys: list[A]) -> list[A]: zs = [] for x in xs: if x in ys: zs.append(x) return zs # 4ª solución # =========== def interseccion4(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_interseccion(xs, ys): xs1 = list(set(xs)) ys1 = list(set(ys)) assert sorted(interseccion1(xs1, ys1)) ==\ sorted(interseccion2(xs1, ys1)) ==\ sorted(interseccion3(xs1, ys1)) ==\ sorted(interseccion4(xs1, ys1)) # La comprobación es # src> poetry run pytest -q interseccion_conjuntista_de_listas.py # 1 passed in 0.33s # 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('interseccion1(list(range(0,20000)), list(range(1,20000,2)))') # 0.98 segundos # >>> tiempo('interseccion2(list(range(0,20000)), list(range(1,20000,2)))') # 2.13 segundos # >>> tiempo('interseccion3(list(range(0,20000)), list(range(1,20000,2)))') # 0.87 segundos # >>> tiempo('interseccion4(list(range(0,20000)), list(range(1,20000,2)))') # 0.00 segundos |
El código se encuentra en GitHub.