faster binary tree implementations available

[jonathanstrong]

hey -

Thanks for your work on this - has been very helpful.

Wanted to send along a note that I identified some faster binary tree implementations while trying to speed this up.

For my use case, I'm finding banyan.SortedDict with alg set to banyan.SPLAY_TREE is the fastest. There's another library called sortedcontainers that is also very fast.

[danielktaylor]

Hi Jonathan,

Thanks for the heads up - when I have time I can see how easy it would be to replace bintrees with banyan.SortedDict.

If you have any code, feel free to PR.

Thanks,
Daniel

[jonathanstrong]

the biggest difference is the special remove and insert methods you're using for the bintrees version don't apply to the others.

one other note - I was using Decimal types as keys in my implementation, but found a 15x speedup by converting the keys back and forth to ints (ie int(x*1e8) or Decimal(x)/1e8). The banyan SortedDict allows you to specify key_type and this can be a massive speed boost.

[fatestapestry]

banyan isn't working with Py3.7 sadly. Won't install with pip