Representación densa de polinomios
Los polinomios pueden representarse de forma dispersa o densa. Por ejemplo, el polinomio 6x^4-5x^2+4x-7 se puede representar de forma dispersa por [6,0,-5,4,-7] y de forma densa por [(4,6),(2,-5),(1,4),(0,-7)].
Definir la función
|
1 |
densa :: [Int] -> [(Int,Int)] |
tal que densa xs es la representación densa del polinomio cuya representación dispersa es xs. Por ejemplo,
|
1 2 3 |
densa [6,0,-5,4,-7] == [(4,6),(2,-5),(1,4),(0,-7)] densa [6,0,0,3,0,4] == [(5,6),(2,3),(0,4)] densa [0] == [(0,0)] |
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 |
import Test.QuickCheck -- 1ª solución -- =========== densa1 :: [Int] -> [(Int,Int)] densa1 xs = [(x,y) | (x,y) <- zip [n-1,n-2..1] xs, y /= 0] ++ [(0, last xs)] where n = length xs -- 2ª solución -- =========== densa2 :: [Int] -> [(Int,Int)] densa2 xs = filter (\ (_,y) -> y /= 0) (zip [n-1,n-2..1] xs) ++ [(0, last xs)] where n = length xs -- 3ª solución -- =========== densa3 :: [Int] -> [(Int,Int)] densa3 xs = filter ((/= 0) . snd) (zip [n-1,n-2..1] xs) ++ [(0, last xs)] where n = length xs -- 4ª solución -- =========== densa4 :: [Int] -> [(Int,Int)] densa4 xs = aux xs (length xs - 1) where aux [y] 0 = [(0, y)] aux (y:ys) n | y == 0 = aux ys (n-1) | otherwise = (n,y) : aux ys (n-1) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_densa :: NonEmptyList Int -> Bool prop_densa (NonEmpty xs) = all (== densa1 xs) [densa2 xs, densa3 xs, densa4 xs] -- La comprobación es -- λ> quickCheck prop_densa -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (densa1 [1..2*10^6]) -- (0,2000000) -- (0.95 secs, 880,569,400 bytes) -- λ> last (densa2 [1..2*10^6]) -- (0,2000000) -- (0.52 secs, 800,569,432 bytes) -- λ> last (densa3 [1..2*10^6]) -- (0,2000000) -- (0.53 secs, 752,569,552 bytes) -- λ> last (densa4 [1..2*10^6]) -- (0,2000000) -- (3.05 secs, 1,267,842,032 bytes) -- -- λ> last (densa1 [1..10^7]) -- (0,10000000) -- (5.43 secs, 4,400,570,128 bytes) -- λ> last (densa2 [1..10^7]) -- (0,10000000) -- (3.03 secs, 4,000,570,160 bytes) -- λ> last (densa3 [1..10^7]) -- (0,10000000) -- (2.34 secs, 3,760,570,280 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 |
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 densa1(xs: list[int]) -> list[tuple[int, int]]: n = len(xs) return [(x, y) for (x, y) in zip(range(n-1, 0, -1), xs) if y != 0] + [(0, xs[-1])] # 2ª solución # =========== def densa2(xs: list[int]) -> list[tuple[int, int]]: n = len(xs) return list(filter(lambda p: p[1] != 0, zip(range(n-1, 0, -1), xs))) + [(0, xs[-1])] # 3ª solución # =========== def densa3(xs: list[int]) -> list[tuple[int, int]]: def aux(ys: list[int], n: int) -> list[tuple[int, int]]: if n == 0: return [(0, ys[0])] if ys[0] == 0: return aux(ys[1:], n-1) return [(n, ys[0])] + aux(ys[1:], n-1) return aux(xs, len(xs) - 1) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.integers(), min_size=1)) def test_densa(xs: list[int]) -> None: r = densa1(xs) assert densa2(xs) == r assert densa3(xs) == r # La comprobación es # src> poetry run pytest -q representacion_densa_de_polinomios.py # 1 passed in 0.27s # 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('densa1(range(1, 10**4))') # 0.00 segundos # >>> tiempo('densa2(range(1, 10**4))') # 0.00 segundos # >>> tiempo('densa3(range(1, 10**4))') # 0.25 segundos # # >>> tiempo('densa1(range(1, 10**7))') # 1.87 segundos # >>> tiempo('densa2(range(1, 10**7))') # 2.15 segundos |
El código se encuentra en GitHub