How to pick a random number from a collection that doesn't support indexing?

help
1

I have a variable of a customly-written collection based on BTreeMap. The keys are GUID-s and the values are some structs.

How will I pick a random element from a said collection based on a random number that's been generated somehow or obtained from an external source?

2

If by "based on" you mean given random number 0 ≤ i < map.len(), you want the i-th key, then I don't think there is a direct way.

If you need the key (as well as the element), then a workaround could be to maintain a copy of the keys in an Vec, for example. If you don't plan to mutate the collection after it is built, you can just perform this mapping once upfront, and then keep looking up the keys based on their index.

If you only need the values, or you need to mutate the collection, then another way would be to keep around a copy of the values instead, always push() when a new element is inserted, swap_remove() when one is deleted, and then pick from the values directly.

A third approach could be to design a two-level mapping where instead of storing the values directly in the BTreeMap, you store them in a Vec and you only store their indices in the BTreeMap. This still allows you to index into the Vec, and it will also allow you to access them by key.

1 Like
3

I'll need a key of a map only.

Somebody has suggested me another approach which to me appears better, for some reason:

generate a new GUID and check which of the existing ones (keys) it's the closest to.

Then this begs a question: given a vector of GUIDs and a target GUID, how will I find which of the GUIDs in a vector is the closest to the the target one?

How does one measure how close 2 GUIDs are?

4

Depending on the performance characteristics you need, you might be able to just use BTreeMap's iter method along with the nth combinator. It won't be optimally fast, but it's an option if you only need to find a random value occasionally.

I think you would need lower level access to the data structures inside BTreeMap than what std currently offers to be able to use a strategy like that.

5

You're saying "vector" now, rather than map?

With BTreeMap, you can use range to get iterators near a given value, e.g.:

  • map.range(..=x).next_back() for the closest key <= x
  • map.range(x..).next() for the closest key >= x

If you have indeed switched to a vector, then you can do a similar thing with bisection if it's sorted.

3 Likes
7

Hello,
Depending on your use case you may want to decouple indexed Access from key acces with something like

struct SomeStruct;
struct GuidMap {
map: BtreeMap<Guid, usize>,
data: Vec<SomeStruct>
}

Or something like this crate (not mine)

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.