Get a random element from a BTree

[azmeuk]

I would love to have a performant way to get a random element out of a BTree.

At the moment I use random.choice (random.choice(mybtree.keys())), but internally it calls len on the ITreeItems, and on large BTrees (>200k items) the operation is long enough (3~4s on my computer) to not fit a web request expectations.

Due to the nature of BTrees, I would expect that this would not be hard to build a pseudo-random method that would go through random child BTrees until it meets a leaf bucket, and then choose a random item in it. This would not exactly be randomness if the tree is not perfectly balanced but this would be good enough in my opinion.

What do you think? Did I miss a simpler way to get a random element? Would such a PR be OK?

[d-maurer]

Éloi Rivard wrote at 2022-9-19 05:30 -0700:

... I would love to have a performant way to get a random element out of a BTree. ... Due to the nature of BTrees, I would expect that this would not be hard to build a pseudo-random method that would go through random child buckets until it meets a leaf. This would not *exactly* be randomness if the tree is not perfectly balanced but this would be good enough in my opinion. ... What do you think? Did I miss a simpler way to get a random element? Would such a PR be OK?

`Bucket`s are the leaves of a `BTree`. Thus, your terminology is not optimal. The `BTrees` package contains the module `check`. It contains functions which let you decompose a large `BTree` into its components (sub-`BTree`s and `Bucket`s). You could use them to implement your idea and check whether it is good enough for you.

[azmeuk]

Buckets are the leaves of a BTree. Thus, your terminology is not optimal.

Indeed. Maybe go through random child BTrees until it meets a leaf bucket, and then choose a random item in it is a better reformulation.

I will have a look at the check module.