rust_algorithms/
util.rs

1//! Yordamchi vositalar: kichik tasodifiy sonlar generatori va vaqt o'lchagich.
2//!
3//! Loyihada tashqi kutubxonalar ishlatilmagani uchun (`rand` ham yo'q),
4//! demolarda tasodifiy massiv kerak bo'lganda shu yerdagi
5//! [`Rng`] (xorshift64*) ishlatiladi. U kriptografik emas — faqat o'quv maqsadida.
6
7use std::time::{Duration, Instant};
8
9/// Oddiy, tez va deterministik pseudo-random generator (xorshift64*).
10///
11/// **Diqqat:** kriptografiya uchun **yaramaydi**. Faqat demo/benchmark uchun.
12///
13/// # Misol
14/// ```
15/// use rust_algorithms::util::Rng;
16///
17/// let mut rng = Rng::new(42);
18/// let a: Vec<u64> = (0..5).map(|_| rng.next_u64() % 100).collect();
19/// let mut rng2 = Rng::new(42);
20/// let b: Vec<u64> = (0..5).map(|_| rng2.next_u64() % 100).collect();
21/// assert_eq!(a, b); // bir xil urug' (seed) → bir xil ketma-ketlik
22/// ```
23pub struct Rng {
24    state: u64,
25}
26
27impl Rng {
28    /// Yangi generator yaratadi. `seed == 0` bo'lsa, avtomatik almashtiriladi.
29    pub fn new(seed: u64) -> Self {
30        Self {
31            state: if seed == 0 {
32                0x9E37_79B9_7F4A_7C15
33            } else {
34                seed
35            },
36        }
37    }
38
39    /// Navbatdagi 64-bitli tasodifiy son.
40    pub fn next_u64(&mut self) -> u64 {
41        let mut x = self.state;
42        x ^= x >> 12;
43        x ^= x << 25;
44        x ^= x >> 27;
45        self.state = x;
46        x.wrapping_mul(0x2545_F491_4F6C_DD1D)
47    }
48
49    /// `0..n` oralig'idagi tasodifiy `usize` (n > 0 bo'lishi shart).
50    pub fn below(&mut self, n: usize) -> usize {
51        (self.next_u64() % n as u64) as usize
52    }
53
54    /// `lo..=hi` oralig'idagi tasodifiy `i64`.
55    pub fn range(&mut self, lo: i64, hi: i64) -> i64 {
56        debug_assert!(lo <= hi);
57        let span = (hi - lo + 1) as u64;
58        lo + (self.next_u64() % span) as i64
59    }
60
61    /// Slicening elementlarini joyida aralashtiradi (Fisher–Yates, O(n)).
62    ///
63    /// # Misol
64    /// ```
65    /// use rust_algorithms::util::Rng;
66    ///
67    /// let mut v: Vec<i32> = (0..10).collect();
68    /// Rng::new(7).shuffle(&mut v);
69    /// let mut sorted = v.clone();
70    /// sorted.sort();
71    /// assert_eq!(sorted, (0..10).collect::<Vec<_>>()); // elementlar yo'qolmadi
72    /// ```
73    pub fn shuffle<T>(&mut self, slice: &mut [T]) {
74        for i in (1..slice.len()).rev() {
75            let j = self.below(i + 1);
76            slice.swap(i, j);
77        }
78    }
79
80    /// `n` ta tasodifiy `i64` dan iborat vektor.
81    pub fn vec(&mut self, n: usize, lo: i64, hi: i64) -> Vec<i64> {
82        (0..n).map(|_| self.range(lo, hi)).collect()
83    }
84}
85
86/// Berilgan yopilmani (closure) bajarib, ketgan vaqtni qaytaradi.
87///
88/// Demolarda "qaysi algoritm tezroq?" savoliga javob berish uchun.
89///
90/// # Misol
91/// ```
92/// use rust_algorithms::util::measure;
93///
94/// let (sum, elapsed) = measure(|| (1..=1000u64).sum::<u64>());
95/// assert_eq!(sum, 500_500);
96/// assert!(elapsed.as_secs() < 5);
97/// ```
98pub fn measure<T, F: FnOnce() -> T>(f: F) -> (T, Duration) {
99    let start = Instant::now();
100    let out = f();
101    (out, start.elapsed())
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107
108    #[test]
109    fn rng_is_deterministic() {
110        let a: Vec<u64> = (0..100).map(|_| Rng::new(1).next_u64()).collect();
111        assert!(a.windows(2).all(|w| w[0] == w[1]));
112    }
113
114    #[test]
115    fn below_stays_in_range() {
116        let mut rng = Rng::new(123);
117        for _ in 0..1000 {
118            assert!(rng.below(10) < 10);
119        }
120    }
121
122    #[test]
123    fn range_is_inclusive_and_bounded() {
124        let mut rng = Rng::new(9);
125        for _ in 0..1000 {
126            let x = rng.range(-5, 5);
127            assert!((-5..=5).contains(&x));
128        }
129    }
130
131    #[test]
132    fn shuffle_keeps_all_elements() {
133        let mut v: Vec<i32> = (0..50).collect();
134        Rng::new(2024).shuffle(&mut v);
135        v.sort_unstable();
136        assert_eq!(v, (0..50).collect::<Vec<_>>());
137    }
138}
rust_algorithms/util.rs

rust_algorithms/
util.rs
