bogo_plus_plus/
lib.rs

1use std::cmp::Ordering;
2use std::error::Error;
3use std::fmt::Debug;
4use rand::{Rng, thread_rng};
5use rayon::prelude::*;
6
7fn insert_within<T: Copy>(data: &mut [T], a: usize, b: usize) {
8    if a == b {return};
9    let (pluck_from, insert_at) = if a > b {
10        (a, b)
11    } else {
12        (b, a)
13    };
14
15    let plucked = data[pluck_from];
16    data.copy_within(insert_at..pluck_from, insert_at+1);
17    data[insert_at] = plucked;
18}
19
20fn mutate_one<T: Copy>(data: &mut [T], mutation_chance: f64) {
21    let mut rng = thread_rng();
22    for _ in 0..data.len() {
23        if rng.gen_bool(mutation_chance) {
24            let a = rng.gen_range(0..data.len());
25            let b = rng.gen_range(0..data.len());
26            insert_within(data, a, b);
27        }
28    }
29}
30
31fn mutate<T: Sync + Send + Copy>(population: &mut [Vec<T>], mutation_chance: f64) {
32    population.par_iter_mut()
33        .for_each(|list| {
34            mutate_one(list, mutation_chance);
35        });
36}
37
38fn score_one_from_start<T: Ord>(data: &[T]) -> usize {
39    let mut score = 1;
40    let mut last = &data[0];
41    for current in data.iter().skip(1) {
42        match current.cmp(last) {
43            Ordering::Less => break,
44            Ordering::Equal => score += 1,
45            Ordering::Greater => score += 1,
46        }
47        last = current;
48    }
49    score
50}
51
52fn score_one_everywhere<T: Ord>(data: &[T]) -> usize {
53    data.iter()
54        .skip(1)
55        .fold((1, &data[0]), |(current_score, last), current| {
56            let this_score = match current.cmp(last) {
57                Ordering::Less => 0,
58                Ordering::Equal => 1,
59                Ordering::Greater => 1,
60            };
61            (current_score + this_score, current)
62        })
63        .0
64}
65
66pub fn score_one_default<T: Ord>(data: &[T]) -> f64 {
67    score_one_everywhere(data) as f64 * 0.45 + score_one_from_start(data) as f64 * 0.55
68}
69
70fn conform_to_best<T: Ord + Copy + Sync + Send>(population: &mut [Vec<T>], last_best_score: f64, last_best_i: usize, score_one_fn: fn(&[T]) -> f64) -> (f64, usize) {
71    let mut best_score = 0.0;
72    let mut best_i = 0;
73    let mut best = &population[last_best_i];
74
75    let scores : Vec<_> = population.par_iter()
76        .map(|list| score_one_fn(list))
77        .collect();
78    for ((i, list), score) in population.iter().enumerate().zip(scores) {
79        if score > best_score {
80            best_score = score;
81            best_i = i;
82            best = list;
83        }
84    }
85
86    if last_best_score > best_score {
87        best_score = last_best_score;
88        best_i = last_best_i;
89    }
90
91    let best = best.clone();
92    for list in population {
93        list.copy_from_slice(&best);
94    }
95
96    (best_score, best_i)
97}
98
99/// A Optimizer is used in a Sorting to get the mutation_chance for each epoch
100pub trait Optimizer {
101
102    /// Gets called once before each training session
103    fn start(&mut self, data_length: usize);
104
105
106    /// Gets called before each epoch
107    fn get_mutation_chance(&mut self, last_done_fraction: f64) -> f64;
108
109}
110
111
112/// Audentis is a simple Optimizer that drops the mutation chance off exponentially starting at a certain value
113#[derive(Clone, Debug)]
114pub struct AudentisOptimizer {
115    ten_initial_mutation_chance: f64, // Initial mutation chance for a list of 10 elements
116    exp_rate: f64,
117    initial_mutation_chance: f64
118}
119
120impl Default for AudentisOptimizer {
121    fn default() -> Self {
122        Self {
123            ten_initial_mutation_chance: 0.22,
124            exp_rate: -1.14,
125            initial_mutation_chance: 0.0,
126        }
127    }
128}
129
130impl AudentisOptimizer {
131
132    pub fn new(ten_initial_mutation_chance: f64, decay: f64) -> Self {
133        Self {
134            ten_initial_mutation_chance,
135            exp_rate: -decay,
136            initial_mutation_chance: 0.0,
137        }
138    }
139
140}
141
142impl Optimizer for AudentisOptimizer {
143    fn start(&mut self, data_length: usize) {
144        self.initial_mutation_chance = self.ten_initial_mutation_chance * 10.0 / data_length as f64;
145    }
146
147    fn get_mutation_chance(&mut self, last_done_fraction: f64) -> f64 {
148        self.initial_mutation_chance * (self.exp_rate * last_done_fraction).exp()
149    }
150}
151
152
153/// Aestimabo is a superset of the Audentis Optimizer, that tries to react to more dynamically adapt the mutation chance, when issues arise.
154#[derive(Clone, Debug)]
155pub struct AestimaboOptimizer {
156    audentis: AudentisOptimizer,
157    last_done_fraction: f64,
158    stuck_mutation_change: f64,
159    stuck_decrease_by: f64,
160    omega_factor: f64,
161}
162
163impl AestimaboOptimizer {
164
165    pub fn new(audentis_optimizer: AudentisOptimizer, stuck_decrease_by: f64, omega_factor: f64) -> Self {
166        Self {
167            audentis: audentis_optimizer,
168            last_done_fraction: 0.0,
169            stuck_mutation_change: 0.0,
170            omega_factor,
171            stuck_decrease_by,
172        }
173    }
174
175}
176
177impl Optimizer for AestimaboOptimizer {
178    fn start(&mut self, data_length: usize) {
179        self.audentis.start(data_length);
180        self.last_done_fraction = f64::NAN;
181    }
182
183    fn get_mutation_chance(&mut self, last_done_fraction: f64) -> f64 {
184        if last_done_fraction == self.last_done_fraction {
185            self.stuck_mutation_change -= self.stuck_decrease_by;
186        } else {
187            self.stuck_mutation_change /= self.omega_factor;
188        }
189        self.last_done_fraction = last_done_fraction;
190        let mut mutation_chance = self.audentis.get_mutation_chance(last_done_fraction);
191        mutation_chance += mutation_chance * self.stuck_mutation_change.clamp(-1.0, 1.0) / 1.1;
192        mutation_chance
193    }
194}
195
196
197/// A Config for the `BogoSorting` Sorting
198#[derive(Clone, Debug)]
199pub struct BogoConfig<O: Optimizer, T: Send + Sync + Debug + Copy + Clone + Ord + PartialEq> {
200    pub give_up_count: usize,
201    pub verbose: bool,
202    pub population_size: usize,
203    pub optimizer: O,
204    pub scoring_function: fn(&[T]) -> f64
205}
206
207impl<T: Send + Sync + Debug + Copy + Clone + Ord + PartialEq> Default for BogoConfig<AudentisOptimizer, fn(&[T]) -> f64> {
208    fn default() -> Self {
209        Self {
210            give_up_count: usize::MAX,
211            verbose: true,
212            population_size: 64,
213            optimizer: AudentisOptimizer::default(),
214            scoring_function: score_one_default
215        }
216    }
217}
218
219/// A SortingResultKind defines the Result of a Sorting
220#[derive(Debug)]
221pub enum SortingResultKind<T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq> {
222    /// The Sorting was Successful, contains sorted data
223    SortingWasOkKindResult(Vec<T>),
224    /// The Sorting was Incomplete, contains possibly partially data
225    SortingWasIncompleteKindResult(Vec<T>),
226    /// The Sorting was Erroneous, contains a Error value
227    SortingWasErroneousKindResult(Box<dyn Error>)
228}
229
230impl<T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq> SortingResultKind<T> {
231
232    pub fn unwrap_sorting_result_kind(self) -> Option<Vec<T>> {
233        match self {
234            SortingResultKind::SortingWasOkKindResult(v) => Some(v),
235            SortingResultKind::SortingWasIncompleteKindResult(_) => None,
236            SortingResultKind::SortingWasErroneousKindResult(_) => None,
237        }
238    }
239
240    pub fn unwrap_sorting_result_kind_with_incomplete(self) -> Option<Vec<T>> {
241        match self {
242            SortingResultKind::SortingWasOkKindResult(v) => Some(v),
243            SortingResultKind::SortingWasIncompleteKindResult(v) => Some(v),
244            SortingResultKind::SortingWasErroneousKindResult(_) => None,
245        }
246    }
247
248}
249
250impl<T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq> PartialEq for &SortingResultKind<T> {
251    fn eq(&self, other: &Self) -> bool {
252        match (self, other) {
253            (SortingResultKind::SortingWasOkKindResult(a), SortingResultKind::SortingWasOkKindResult(b)) => a == b,
254            (SortingResultKind::SortingWasIncompleteKindResult(a), SortingResultKind::SortingWasIncompleteKindResult(b)) => a == b,
255            _ => false
256        }
257    }
258}
259
260
261/// A Sorting result that holds a `SortingResultKind`
262pub struct SortingResult<'a, T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq, C: ?Sized> {
263    inner: SortingResultKind<T>,
264    config: &'a mut C
265}
266
267impl<'a, T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq, C: ?Sized> SortingResult<'a, T, C> {
268
269    pub fn get_inner_sorting_result_kind(&self) -> &SortingResultKind<T> {
270        &self.inner
271    }
272
273    pub fn get_inner_config(&'a self) -> &'a C {
274        self.config
275    }
276
277}
278
279impl<'a, T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq, C: ?Sized> From<SortingResult<'a, T, C>> for SortingResultKind<T> {
280    fn from(value: SortingResult<'a, T, C>) -> Self {
281        value.inner
282    }
283}
284
285/// A trait to support Generic Sorting implementations
286pub trait Sorting<'a, 'b, T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq, C: ?Sized> {
287
288    /// Creates a Sorting bound to some data and some Config
289    fn new(data: &'a [T], config: &'b mut C) -> Self where Self: Sized;
290
291    /// Obtain a sorting Result from a Sorting, by sorting the data. \
292    /// This call consumes the Sorting
293    fn sorting_get_sorted_result(self) -> SortingResult<'b, T, C>;
294
295}
296
297/// Bogo++ Sorting
298/// Example usage:
299/// ```
300/// use bogo_plus_plus::{AudentisOptimizer, BogoConfig, BogoSorting, SortingResultKind, score_one_default, Sorting};
301/// let optimizer = AudentisOptimizer::default();
302/// let mut config = BogoConfig {
303///     give_up_count: 1000,
304///     verbose: false,
305///     population_size: 10,
306///     optimizer,
307///     scoring_function: score_one_default
308/// };
309/// // Sort
310/// let data = vec![1, -1, 10, 3, 12, 3, 100];
311/// let sorting = BogoSorting::new(&data, &mut config);
312/// let result = sorting.sorting_get_sorted_result();
313/// let result_kind = result.get_inner_sorting_result_kind();
314/// assert_eq!(result_kind, &SortingResultKind::SortingWasOkKindResult(vec![-1, 1, 3, 3, 10, 12, 100]));
315/// ```
316/// This sorts the list `[1, -1, 10, 3, 12, 3, 100]` using the `BogoSorting` and the Audentis optimizer.
317pub struct BogoSorting<'a, 'b, O: Optimizer, T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq> {
318    population: Vec<Vec<T>>,
319    data: &'a [T],
320    config: &'b mut BogoConfig<O, T>
321}
322
323impl<'a, 'b, O: Optimizer, T: Ord + Copy + Sync + Send + Debug + Clone + PartialEq> Sorting<'a, 'b, T, BogoConfig<O, T>> for BogoSorting<'a, 'b, O, T> {
324
325    fn new(data: &'a [T], config: &'b mut BogoConfig<O, T>) -> Self {
326        Self {
327            population: Vec::with_capacity(0), // We assume that data is empty most of the time
328            data,
329            config,
330        }
331    }
332
333    fn sorting_get_sorted_result(mut self) -> SortingResult<'b, T, BogoConfig<O, T>> {
334        if self.data.is_empty() {
335            return SortingResult {
336                inner: SortingResultKind::SortingWasOkKindResult(vec![]),
337                config: self.config,
338            }
339        }
340
341        self.population = vec![self.data.to_vec(); self.config.population_size];
342
343        let mut last_best_score = 0.0;
344        let mut last_best_i = 0;
345        let mut c = 0;
346
347        self.config.optimizer.start(self.data.len());
348        while last_best_score != (self.data.len() as f64) && c != self.config.give_up_count {
349            let done_fraction = last_best_score / self.data.len() as f64;
350            let mutation_chance = self.config.optimizer.get_mutation_chance(done_fraction);
351            mutate(&mut self.population, mutation_chance);
352            (last_best_score, last_best_i) = conform_to_best(&mut self.population, last_best_score, last_best_i, self.config.scoring_function);
353
354            if self.config.verbose {
355                c += 1;
356                if c % 1000 == 0 || c < 10 {
357                    println!("[{}] {:0.1}/{} {:0.2}% {:0.6}", c, last_best_score, self.data.len(), done_fraction * 100.0, mutation_chance);
358                }
359            }
360        };
361
362        if c == self.config.give_up_count {
363            return SortingResult {
364                inner: SortingResultKind::SortingWasIncompleteKindResult(self.population.pop().unwrap()),
365                config: self.config,
366            };
367        }
368        SortingResult {
369            inner: SortingResultKind::SortingWasOkKindResult(self.population.pop().unwrap()),
370            config: self.config,
371        }
372    }
373
374}
375
376
377#[allow(unused_imports)]
378mod test {
379    use super::*;
380
381    #[test]
382    fn test() {
383        let n = 1000;
384        let mut vec = Vec::with_capacity(n);
385        for i in 0..n {
386            vec.push(i);
387        }
388        // Shuffle
389        for _ in 0..100 {
390            mutate_one(&mut vec, 1.0);
391        }
392        // Config
393        let audentis = AudentisOptimizer::new(0.22, 1.3);
394        let optimizer = AestimaboOptimizer::new(audentis, 0.00001, 2.5);
395        let mut config = BogoConfig {
396            give_up_count: 400000,
397            verbose: true,
398            population_size: 80,
399            optimizer,
400            scoring_function: score_one_default
401        };
402        // Sort
403        let sorting = BogoSorting::new(&vec, &mut config);
404        let result = sorting.sorting_get_sorted_result();
405        let result_kind : SortingResultKind<_> = SortingResultKind::from(result);
406        let ok_result = result_kind.unwrap_sorting_result_kind_with_incomplete();
407        // Evaluate test
408        let mut test_sorted = vec.clone();
409        test_sorted.sort();
410        assert_eq!(ok_result, Some(test_sorted));
411    }
412
413}
bogo_plus_plus/lib.rs

bogo_plus_plus/
lib.rs
