Условие

Допиши этот метод

def init(self, nums: List[float]): pass

Допиши этот метод

def dot_product(self, vec: 'SparseVector') -> float: pass

Ответ

Для разреженного вектора сохраните только ненулевые координаты в словаре. Скалярное произведение вычисляйте по меньшему словарю, находя совпадающие индексы в другом.

Построение занимает O(n), память — O(s), где s — число ненулевых элементов. Произведение требует в среднем O(min(s₁,s₂)) словарных обращений. Ниже предполагаются конечные числа и одинаковая размерность векторов.

from typing import List

class SparseVector:
    def __init__(self, nums: List[float]):
        self.size = len(nums)
        self.values = {i: x for i, x in enumerate(nums) if x != 0}

    def dot_product(self, vec: 'SparseVector') -> float:
        if self.size != vec.size:
            raise ValueError('Размерности не совпадают')
        small, large = self.values, vec.values
        if len(small) > len(large):
            small, large = large, small
        return sum((x * large.get(i, 0.0) for i, x in small.items()), 0.0)