Menu Close

Día: 21 octubre, 2022

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

   densa :: [Int] -> [(Int,Int)]

tal que densa xs es la representación densa del polinomio cuya representación dispersa es xs. Por ejemplo,

   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.


Soluciones en Haskell

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.


Soluciones en Python

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