python

Функция для вычисления скалярного произведения двух RLE-сжатых векторов за один проход

Каждый вектор представлен списком кортежей (значение, количество)

def rle_dot_product(rle_vec1, rle_vec2): i, j = 0, 0 result = 0 count1, count2 = 0, 0

while i < len(rle_vec1) and j < len(rle_vec2):
    val1, len1 = rle_vec1[i]
    val2, len2 = rle_vec2[j]

    # Определяем минимальное количество для текущих блоков
    min_count = min(len1 - count1, len2 - count2)

    # Добавляем произведение значений, умноженное на количество совпадающих элементов
    result += val1 * val2 * min_count

    # Обновляем счетчики
    count1 += min_count
    count2 += min_count

    # Если достигли конца блока в первом векторе, переходим к следующему
    if count1 == len1:
        i += 1
        count1 = 0

    # Если достигли конца блока во втором векторе, переходим к следующему
    if count2 == len2:
        j += 1
        count2 = 0

return result

Пример использования

vec1 = [(1, 3), (2, 2), (0, 4)] # соответствует [1,1,1,2,2,0,0,0,0] vec2 = [(0, 2), (3, 3), (2, 4)] # соответствует [0,0,3,3,3,2,2,2,2]

print(rle_dot_product(vec1, vec2)) # Выводит скалярное произведение