_compute_centroid_quantile can cause a runtime error in cython_trees about tdigest HOT 6 CLOSED

Thanks for the detailed issue @pgr. I can confirm the error on my own machine.

Interestingly, I just made an issue today that will resolve this: #4. The problem is the data is in sorted order.

import random
random.shuffle(problem_data)

td = tdigest.TDigest()
td.batch_update(problem_data)

works fine. I'll add this as an additional constraint/problem to be addressed in #4.

from tdigest.

Oh wait, I was wrong; the data is not sorted. Strange then that the shuffle solves the issue...

from tdigest.

I can narrow it down to just this data: https://gist.github.com/CamDavidsonPilon/2357b9d1b2d1401640fc

from tdigest.

K got it. It was because I was using an unbalanced binary tree in bintrees: https://github.com/CamDavidsonPilon/tdigest/blob/master/tdigest/tdigest.py#L4

If ordered data was passed in, as it was in both our examples (a subset in yours), then the tree becomes very lopsided. When we try to call iter_items on the tree, we hit the upper limit of 64 depth (hardcoded in bintrees as MAXSTACK). You can see the calls here: https://searchcode.com/codesearch/view/55567668/

Solution is the change to FastRBTree in bintrees. I tested this and it works on our data. Only downside is is that it will be slightly slower. I feel this is a fair tradeoff.

from tdigest.

Fixed in latest commit!

from tdigest.

Confirmed, cheers!.

from tdigest.