gacha 0.0.1

Efficient gacha algorithm for high performance game servers
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#![allow(clippy::wrong_self_convention)]

mod builder;
mod display;
mod sample;

use rand::Rng;
use std::{collections::BTreeMap, mem::take, ops::AddAssign};

#[derive(Debug)]
pub struct WeightedElement<T> {
    pub key: T,
    pub weight: f64,
    pub accumulated: f64,
}

#[derive(Debug)]
pub struct WeightedList<T> {
    items: Vec<WeightedElement<T>>,
    total: f64,
}

impl<T> WeightedList<T> {
    /// Get the total weight of all elements
    pub fn total_weight(&self) -> f64 {
        self.total
    }
    /// Reorganize and merge elements with the same name to speed up sampling
    pub fn merge(&mut self)
    where
        T: Ord,
    {
        if self.items.is_empty() {
            return;
        }
        let mut new = BTreeMap::default();
        for item in take(&mut self.items) {
            new.entry(item.key).and_modify(|e: &mut f64| *e += item.weight).or_insert(item.weight);
        }
        self.items = WeightedList::from_iter(new).items;
    }
    /// Randomly select an element based on weight, the higher the weight, the easier it is to be selected.
    pub fn random(&self, mut rng: impl Rng) -> Option<&T> {
        if self.items.is_empty() {
            return None;
        }
        let total_weight = self.total_weight();
        let random_weight = rng.gen_range(0.0..total_weight);
        let index =
            self.items.binary_search_by(|elem| elem.accumulated.partial_cmp(&random_weight).unwrap()).unwrap_or_else(|i| i);
        Some(&self.items[index].key)
    }
    /// Rearrange all elements according to weight, the higher the weight, the higher the front.
    pub fn shuffle(&self, mut rng: impl Rng) -> Vec<&T> {
        let mut order: Vec<_> = self
            .items
            .iter()
            .enumerate() //
            .map(|(i, e)| (i, -(rng.gen::<f64>().powf(1.0 / e.weight))))
            .collect();
        // Sort the elements based on the negative random power
        order.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
        // Extract the shuffled items using the sorted order
        order.iter().map(|(i, _)| &self.items[*i].key).collect()
    }
    /// Select n elements according to the weight, the higher the weight, the easier it is to be selected
    pub fn random_select(&self, count: usize, mut rng: impl Rng) -> Vec<&T> {
        let mut out = Vec::with_capacity(count);
        for _ in 0..count {
            if let Some(item) = self.random(&mut rng) {
                out.push(item);
            }
        }
        out
    }
    /// Select n unique elements according to the weight, the higher the weight, the higher the front
    pub fn random_sample(&self, count: usize, mut rng: impl Rng) -> Vec<&T> {
        let mut shuffle = self.shuffle(&mut rng);
        shuffle.truncate(count);
        shuffle
    }
}