Efficient Cosine Similarity

MediumPython

Problem

Andela's machine learning systems may compare high-dimensional feature embeddings where most dimensions are zero. Given two sparse vectors, compute their cosine similarity without expanding them into dense arrays.

Represent each vector as a Python dictionary mapping a nonzero dimension index to its numeric value. Return the cosine similarity:

cosine_similarity(a, b) = (a · b) / (||a|| ||b||)

The dot product should include only dimensions present in both dictionaries. If either vector has zero magnitude, return 0.0.

Formal Specification

Implement cosine_similarity(a, b), where a and b are dictionaries with integer keys and numeric values. Return a floating-point number. The input dictionaries contain only nonzero values, and their dimension ranges do not need to be identical.

Your solution should avoid iterating over the entire possible dimension range. Aim for time proportional to the number of stored nonzero entries, and use dictionary lookup for shared dimensions.

Constraints

Each dictionary contains at most 10^5 nonzero entries
Dimension keys are nonnegative integers
Values are finite integers or floating-point numbers
Either dictionary may be empty
Values may be negative

Function Signature

def cosine_similarity(a, b):

Represent each vector as a Python dictionary mapping a nonzero dimension index to its numeric value. Return the cosine similarity:

cosine_similarity(a, b) = (a · b) / (||a|| ||b||)

The dot product should include only dimensions present in both dictionaries. If either vector has zero magnitude, return 0.0.

Formal Specification

Your solution should avoid iterating over the entire possible dimension range. Aim for time proportional to the number of stored nonzero entries, and use dictionary lookup for shared dimensions.