Реализация класса SparseVector для скалярного произведения разреженных векторов

Решение

Задача и контекст

Необходимо реализовать класс для работы с разреженными векторами (sparse vectors) — векторами, содержащими много нулевых элементов. Эта задача критична в обработке данных, так как реальные данные часто имеют высокую разреженность (тексты, пользовательские рейтинги, сетевые графы). Наивное хранение всех элементов может привести к огромным потерям памяти.

Базовое решение

Начнём с простого подхода, используя встроенные структуры Python:

class SparseVector:
    def __init__(self, nums: list[int]):
        self.nums = nums
    
    def dotProduct(self, vec: "SparseVector") -> int:
        return sum(a * b for a, b in zip(self.nums, vec.nums))

# Пример использования
nums1 = [1, 2, 0, 4]
nums2 = [8, 0, 3, 5]
vec1 = SparseVector(nums1)
vec2 = SparseVector(nums2)
print(vec1.dotProduct(vec2))  # 28

Анализ базового решения:

• Временная сложность: O(n), где n — длина вектора
• Пространственная сложность: O(n) для хранения
• Проблема: при векторе длиной 1 млн элементов будет выполнено 1 млн операций умножения, даже если оненулевых элементов всего 100

Оптимизированное решение (рекомендуется)

Хранимся только ненулевые элементы в словаре, где ключ — индекс, значение — число:

class SparseVector:
    def __init__(self, nums: list[int]):
        # Храним только индексы и значения ненулевых элементов
        self.pairs = {i: num for i, num in enumerate(nums) if num != 0}
    
    def dotProduct(self, vec: "SparseVector") -> int:
        # Итерируем по вектору с меньшим числом ненулевых элементов
        if len(self.pairs) > len(vec.pairs):
            return vec.dotProduct(self)
        
        result = 0
        for idx, val in self.pairs.items():
            if idx in vec.pairs:
                result += val * vec.pairs[idx]
        return result

# Пример использования
nums1 = [1, 2, 0, 4]
nums2 = [8, 0, 3, 5]
vec1 = SparseVector(nums1)
vec2 = SparseVector(nums2)
print(vec1.dotProduct(vec2))  # 28

Сравнение сложностей

Базовое решение:

• Время: O(n) — всегда проходит по всем элементам
• Память: O(n) — хранит все элементы

Оптимизированное решение:

• Время: O(k), где k — количество ненулевых элементов в меньшем векторе. Для разреженных данных это может быть k ≪ n
• Память: O(k) — хранит только ненулевые элементы
• Инициализация: O(n) один раз при создании объекта

Реальный пример производительности

Для вектора длины 1 млн с 0.01% ненулевыми элементами (10 000 элементов):

• Базовое: ~1 млн операций
• Оптимизированное: ~10 000 операций
• Выигрыш: в 100 раз

Ключевые оптимизации в коде

1. Ленивая инициализация — словарь создаётся только при необходимости
2. Выбор меньшего вектора — если у текущего вектора больше ненулевых элементов, делегируем вычисление другому вектору
3. Ранние проверки — проверяем наличие индекса в vec.pairs перед умножением

Применение в Data Engineering

Этот подход используется в:

• Рекомендательные системы — матрицы оценок пользователей/товаров
• NLP — TF-IDF векторы документов
• Графовые БД — матрицы смежности больших графов
• Apache Spark MLlib — SparseVector для машинного обучения