Menu Close

Día: 19 octubre, 2022

Producto escalar

El producto escalar de dos listas de enteros xs y ys de longitud n viene dado por la suma de los productos de los elementos correspondientes.

Definir la función

   productoEscalar :: [Integer] -> [Integer] -> Integer

tal que productoEscalar xs ys es el producto escalar de las listas xs e ys. Por ejemplo,

   productoEscalar [1,2,3] [4,5,6]  ==  32

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Numeric.LinearAlgebra ((<.>), vector)
import Test.QuickCheck (quickCheck)
 
-- 1ª solución
-- ===========
 
productoEscalar1 :: [Integer] -> [Integer] -> Integer
productoEscalar1 xs ys = sum [x*y | (x,y) <- zip xs ys]
 
-- 2ª solución
-- ===========
 
productoEscalar2 :: [Integer] -> [Integer] -> Integer
productoEscalar2 xs ys = sum (zipWith (*) xs ys)
 
-- 3ª solución
-- ===========
 
productoEscalar3 :: [Integer] -> [Integer] -> Integer
productoEscalar3 = (sum .) . zipWith (*)
 
-- 4ª solución
-- ===========
 
productoEscalar4 :: [Integer] -> [Integer] -> Integer
productoEscalar4 [] _          = 0
productoEscalar4 _ []          = 0
productoEscalar4 (x:xs) (y:ys) = x*y + productoEscalar4 xs ys
 
-- 5ª solución
-- ===========
 
productoEscalar5 :: [Integer] -> [Integer] -> Integer
productoEscalar5 (x:xs) (y:ys) = x*y + productoEscalar5 xs ys
productoEscalar5 _ _           = 0
 
-- 6ª solución
-- ===========
 
productoEscalar6 :: [Integer] -> [Integer] -> Integer
productoEscalar6 xs ys =
  round (vector xs' <.> vector ys')
  where xs' = map fromIntegral xs
        ys' = map fromIntegral ys
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_productoEscalar :: [Integer] -> [Integer] -> Bool
prop_productoEscalar xs ys =
  all (== productoEscalar1 xs ys)
      [productoEscalar2 xs ys,
       productoEscalar3 xs ys,
       productoEscalar4 xs ys,
       productoEscalar5 xs ys,
       productoEscalar6 xs' ys']
  where n = min (length xs) (length ys)
        xs' = take n xs
        ys' = take n ys
 
-- La comprobación es
--    λ> quickCheck prop_productoEscalar
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> productoEscalar1 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.37 secs, 803,827,520 bytes)
--    λ> productoEscalar2 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.69 secs, 611,008,272 bytes)
--    λ> productoEscalar3 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.69 secs, 611,008,536 bytes)
--    λ> productoEscalar4 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.64 secs, 742,290,272 bytes)
--    λ> productoEscalar5 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.63 secs, 742,290,064 bytes)
--    λ> productoEscalar6 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.32 secs, 835,679,200 bytes)
--
--    λ> productoEscalar2 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (1.90 secs, 1,831,960,336 bytes)
--    λ> productoEscalar3 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (1.87 secs, 1,831,960,600 bytes)
--    λ> productoEscalar6 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (0.78 secs, 2,573,005,952 bytes)

El código se encuentra en GitHub.


Soluciones en Python

from operator import mul
from sys import setrecursionlimit
from timeit import Timer, default_timer
 
from hypothesis import given
from hypothesis import strategies as st
from numpy import dot
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
def productoEscalar1(xs: list[int], ys: list[int]) -> int:
    return sum(x * y for (x, y) in zip(xs, ys))
 
# 2ª solución
# ===========
 
def productoEscalar2(xs: list[int], ys: list[int]) -> int:
    return sum(map(mul, xs, ys))
 
# 3ª solución
# ===========
 
def productoEscalar3(xs: list[int], ys: list[int]) -> int:
    if xs and ys:
        return xs[0] * ys[0] + productoEscalar3(xs[1:], ys[1:])
    return 0
 
# 4ª solución
# ===========
 
def productoEscalar4(xs: list[int], ys: list[int]) -> int:
    return dot(xs, ys)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(st.integers(min_value=1, max_value=100)),
       st.lists(st.integers(min_value=1, max_value=100)))
def test_productoEscalar(xs: list[int], ys: list[int]) -> None:
    r = productoEscalar1(xs, ys)
    assert productoEscalar2(xs, ys) == r
    assert productoEscalar3(xs, ys) == r
    n = min(len(xs), len(ys))
    xs1 = xs[:n]
    ys1 = ys[:n]
    assert productoEscalar4(xs1, ys1) == r
 
# La comprobación es
#    src> poetry run pytest -q producto_escalar.py
#    1 passed in 0.37s
 
# 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('productoEscalar1([1]*(10**4), [1]*(10**4))')
#    0.00 segundos
#    >>> tiempo('productoEscalar3([1]*(10**4), [1]*(10**4))')
#    0.55 segundos
#
#    >>> tiempo('productoEscalar1([1]*(10**7), [1]*(10**7))')
#    0.60 segundos
#    >>> tiempo('productoEscalar2([1]*(10**7), [1]*(10**7))')
#    0.26 segundos
#    >>> tiempo('productoEscalar4([1]*(10**7), [1]*(10**7))')
#    1.73 segundos

El código se encuentra en GitHub.