datasketch/lshensemble_partition.py
def _compute_best_partitions(num_part, sizes, nfps):
    """Computes the optimal partitions given the size distributions
    and computed number of expected false positives for all sub-intervals.

    Args:
        num_part (int): The number of partitions to create.
        sizes (numpy.array): The complete domain of set sizes in sorted order.
        nfps (numpy.array): The computed number of expected false positives
            for all sub-intervals; axis-0 is for the indexes of lower bounds and
            axis-1 is for the indexes of upper bounds.

    Returns:
        partitions (list): list of lower and upper bounds of set sizes for
            all partitions.
        total_nfps (float): total number of expected false positives from all
            partitions.
        cost (numpy.array): a N x p-1 matrix of the computed optimal NFPs for
            all sub-problems given upper bound set size and number of partitions.
    """

    if num_part < 2:
        raise ValueError("num_part cannot be less than 2")
    if num_part > len(sizes):
        raise ValueError("num_part cannot be greater than the domain size of "
                "all set sizes")

    # If number of partitions is 2, then simply find the upper bound
    # of the first partition.
    if num_part == 2:
        total_nfps, u = min((nfps[0, u1]+nfps[u1+1, len(sizes)-1], u1)
            for u1 in range(0, len(sizes)-1))
        return [(sizes[0], sizes[u]), (sizes[u+1], sizes[-1]),], \
                total_nfps, None

    # Initialize subproblem total NFPs.
    cost = np.zeros((len(sizes), num_part-2))

    # Note: p is the number of partitions in the subproblem.
    # p2i translates the number of partition into the index in the matrix.
    p2i = lambda p : p - 2

    # Compute p >= 2 until before p = num_part.
    for p in range(2, num_part):
        # Compute best partition for subproblems with increasing
        # max index u, starting from the smallest possible u given the p.
        # The smallest possible u can be considered as the max index that
        # generates p partitions each with only one size.
        for u in range(p-1, len(sizes)):
            if p == 2:
                cost[u, p2i(p)] = min(nfps[0, u1]+nfps[u1+1,u]
                        for u1 in range(u))
            else:
                cost[u, p2i(p)] = min(cost[u1, p2i(p-1)] + nfps[u1+1, u]
                        for u1 in range((p-1)-1, u))
    p = num_part
    # Find the optimal upper bound index of the 2nd right-most partition given
    # the number of partitions (p).
    total_nfps, u = min((cost[u1, p2i(p-1)]+nfps[u1+1, len(sizes)-1], u1)
            for u1 in range((p-1)-1, len(sizes)-1))
    partitions = [(sizes[u+1], sizes[-1]),]
    p -= 1
    # Back track to find the best partitions.
    while p > 1:
        # Find the optimal upper bound index of the 2nd right-most partition
        # givne the number of partitions (p) and upper bound index (u) in this
        # sub-problem.
        _, u1_best = min((cost[u1, p2i(p)]+nfps[u1+1, u], u1)
                for u1 in range((p-1)-1, u))
        partitions.insert(0, (sizes[u1_best+1], sizes[u]))
        u = u1_best
        p -= 1
    partitions.insert(0, (sizes[0], sizes[u]))
    return [partitions, total_nfps, cost]
def _compute_best_partitions(num_part, sizes, nfps):
    if num_part < 2:
        raise ValueError("num_part cannot be less than 2")
    if num_part > len(sizes):
        raise ValueError("num_part cannot be greater than the domain size of "
                "all set sizes")

    # If number of partitions is 2, then simply find the upper bound
    # of the first partition.
    if num_part == 2:
        total_nfps, u = min((nfps[0, u1]+nfps[u1+1, len(sizes)-1], u1)
            for u1 in range(0, len(sizes)-1))
        return [(sizes[0], sizes[u]), (sizes[u+1], sizes[-1]),], \
                total_nfps, None

    # Initialize subproblem total NFPs.
    cost = np.zeros((len(sizes), num_part-2))

    # Note: p is the number of partitions in the subproblem.
    # p2i translates the number of partition into the index in the matrix.
    p2i = lambda p : p - 2

    # Compute p >= 2 until before p = num_part.
    for p in range(2, num_part):
        # Compute best partition for subproblems with increasing
        # max index u, starting from the smallest possible u given the p.
        # The smallest possible u can be considered as the max index that
        # generates p partitions each with only one size.
        for u in range(p-1, len(sizes)):
            if p == 2:
                cost[u, p2i(p)] = min(nfps[0, u1]+nfps[u1+1,u]
                        for u1 in range(u))
            else:
                cost[u, p2i(p)] = min(cost[u1, p2i(p-1)] + nfps[u1+1, u]
                        for u1 in range((p-1)-1, u))
    p = num_part
    # Find the optimal upper bound index of the 2nd right-most partition given
    # the number of partitions (p).
    total_nfps, u = min((cost[u1, p2i(p-1)]+nfps[u1+1, len(sizes)-1], u1)
            for u1 in range((p-1)-1, len(sizes)-1))
    partitions = [(sizes[u+1], sizes[-1]),]
    p -= 1
    # Back track to find the best partitions.
    while p > 1:
        # Find the optimal upper bound index of the 2nd right-most partition
        # givne the number of partitions (p) and upper bound index (u) in this
        # sub-problem.
        _, u1_best = min((cost[u1, p2i(p)]+nfps[u1+1, u], u1)
                for u1 in range((p-1)-1, u))
        partitions.insert(0, (sizes[u1_best+1], sizes[u]))
        u = u1_best
        p -= 1
    partitions.insert(0, (sizes[0], sizes[u]))
    return [partitions, total_nfps, cost]
def _compute_best_partitions ( num_part , sizes , nfps ) : if num_part < 2 : raise ValueError ( "num_part cannot be less than 2" ) if num_part > len ( sizes ) : raise ValueError ( "num_part cannot be greater than the domain size of " "all set sizes" ) # If number of partitions is 2, then simply find the upper bound # of the first partition. if num_part == 2 : total_nfps , u = min ( ( nfps [ 0 , u1 ] + nfps [ u1 + 1 , len ( sizes ) - 1 ] , u1 ) for u1 in range ( 0 , len ( sizes ) - 1 ) ) return [ ( sizes [ 0 ] , sizes [ u ] ) , ( sizes [ u + 1 ] , sizes [ - 1 ] ) , ] , total_nfps , None # Initialize subproblem total NFPs. cost = np . zeros ( ( len ( sizes ) , num_part - 2 ) ) # Note: p is the number of partitions in the subproblem. # p2i translates the number of partition into the index in the matrix. p2i = lambda p : p - 2 # Compute p >= 2 until before p = num_part. for p in range ( 2 , num_part ) : # Compute best partition for subproblems with increasing # max index u, starting from the smallest possible u given the p. # The smallest possible u can be considered as the max index that # generates p partitions each with only one size. for u in range ( p - 1 , len ( sizes ) ) : if p == 2 : cost [ u , p2i ( p ) ] = min ( nfps [ 0 , u1 ] + nfps [ u1 + 1 , u ] for u1 in range ( u ) ) else : cost [ u , p2i ( p ) ] = min ( cost [ u1 , p2i ( p - 1 ) ] + nfps [ u1 + 1 , u ] for u1 in range ( ( p - 1 ) - 1 , u ) ) p = num_part # Find the optimal upper bound index of the 2nd right-most partition given # the number of partitions (p). total_nfps , u = min ( ( cost [ u1 , p2i ( p - 1 ) ] + nfps [ u1 + 1 , len ( sizes ) - 1 ] , u1 ) for u1 in range ( ( p - 1 ) - 1 , len ( sizes ) - 1 ) ) partitions = [ ( sizes [ u + 1 ] , sizes [ - 1 ] ) , ] p -= 1 # Back track to find the best partitions. while p > 1 : # Find the optimal upper bound index of the 2nd right-most partition # givne the number of partitions (p) and upper bound index (u) in this # sub-problem. _ , u1_best = min ( ( cost [ u1 , p2i ( p ) ] + nfps [ u1 + 1 , u ] , u1 ) for u1 in range ( ( p - 1 ) - 1 , u ) ) partitions . insert ( 0 , ( sizes [ u1_best + 1 ] , sizes [ u ] ) ) u = u1_best p -= 1 partitions . insert ( 0 , ( sizes [ 0 ] , sizes [ u ] ) ) return [ partitions , total_nfps , cost ]
Computes the optimal partitions given the size distributions
    and computed number of expected false positives for all sub-intervals.

    Args:
        num_part (int): The number of partitions to create.
        sizes (numpy.array): The complete domain of set sizes in sorted order.
        nfps (numpy.array): The computed number of expected false positives
            for all sub-intervals; axis-0 is for the indexes of lower bounds and
            axis-1 is for the indexes of upper bounds.

    Returns:
        partitions (list): list of lower and upper bounds of set sizes for
            all partitions.
        total_nfps (float): total number of expected false positives from all
            partitions.
        cost (numpy.array): a N x p-1 matrix of the computed optimal NFPs for
            all sub-problems given upper bound set size and number of partitions.
Computes the optimal partitions given the size distributions and computed number of expected false positives for all sub - intervals .