RBST
Randomized Binary Search Tree
Ordered multisets can be processed quickly by using C++ multisets, etc.
and therefore, what is the equivalent of multiset in C++ in Python? and the topic was raised
I felt it would be a good idea to have it as my own library...
Implementations that make nodes as objects are generally bad.
Because of the high cost of generating objects.
Implement in arrays and make with the policy to compile in numba.
--- Development
C++ implementation ported to Python
Implementation in phoenix tree 4.83sec
Implementation in RBST 105.47sec
20 times slower
Remove class
67.01sec
About 60% faster.
Remove recurrence call and compile with [numba
10.13sec
Sequential addition in list changed to batch allocation in np.array
4.60sec
---
This page is auto-translated from /nishio/RBST. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.