import math


def sparse_cosine_similarity(A, B):
    """
    Function computing cosine similarity on sparse weighted sets represented
    as python dicts.

    Runs in O(n), n being the sum of A & B's sizes.

    Args:
        A (Counter): First weighted set.
        B (Counter): Second weighted set.

    Returns:
        float: Cosine similarity between A & B.

    Example:
        from fog.metrics import sparse_cosine_similarity

        # Basic
        sparse_cosine_similarity({'apple': 34, 'pear': 3}, {'pear': 1, 'orange': 1})
        >>> ~0.062

    """

    # Early termination
    if A is B:
        return 1.0

    if len(A) == 0 or len(B) == 0:
        return 0.0

    xx = 0.0
    xy = 0.0
    yy = 0.0

    # Swapping to iterate over smaller set and minimize lookups
    if len(A) > len(B):
        A, B = B, A

    for k, v in A.items():
        weight = v
        xx += weight ** 2

        v2 = B.get(k)

        if v2 is not None:
            xy += weight * v2

    for v in B.values():
        weight = v
        yy += weight ** 2

    return xy / math.sqrt(xx * yy)