python

Function to compute the dot product of two RLE-compressed vectors in a single pass

Each vector is represented as a list of tuples (value, count)

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]

    # Determine the minimum count for the current blocks
    min_count = min(len1 - count1, len2 - count2)

    # Add the product of values multiplied by the number of matching elements
    result += val1 * val2 * min_count

    # Update counters
    count1 += min_count
    count2 += min_count

    # Move to the next block in the first vector if the current block is finished
    if count1 == len1:
        i += 1
        count1 = 0

    # Move to the next block in the second vector if the current block is finished
    if count2 == len2:
        j += 1
        count2 = 0

return result

Example usage

vec1 = [(1, 3), (2, 2), (0, 4)] # corresponds to [1,1,1,2,2,0,0,0,0] vec2 = [(0, 2), (3, 3), (2, 4)] # corresponds to [0,0,3,3,3,2,2,2,2]

print(rle_dot_product(vec1, vec2)) # Outputs the dot product