T-Digest Centroid Compression

Problem

Merge adjacent t-digest centroids while respecting a maximum centroid weight.

centroids is a list of [mean, weight] pairs sorted by mean. Fold each next centroid into the current one when their combined weight is at most max_weight using the weighted mean, otherwise start a new centroid. Return the reduced list of [mean, weight] pairs.

Hint

Compression scans once, greedily absorbing the next centroid while the weight budget allows.

Test cases

case 1

in: [[[1,1],[2,1],[3,1],[10,5]],2]

expected: [[1.5,2],[3,1],[10,5]]

case 2

in: [[[5,3],[9,2]],5]

expected: [[6.6,5]]

case 3

in: [[],4]

expected: []

case 4

in: [[[0,1]],1]

expected: [[0,1]]

case 5

in: [[[1,2],[2,2],[3,2]],4]

expected: [[1.5,4],[3,2]]

Starter codePython

def tdigest_compress(centroids, max_weight):
    # Your code here
    pass

5 test cases · run your code against them in the editor