ph_temp/phast/seed_chooser/
k.rs

1use bitm::ceiling_div;
2
3use crate::phast::{conf::Conf, cyclic::{GenericUsedValue, UsedValueMultiSetU8}};
4use super::SeedChooser;
5
6/// [`SeedChooser`] to build `k`-perfect functions.
7/// `k` is given as a parameter of this chooser.
8/// 
9/// Should be used with [`Perfect`].
10/// 
11/// It chooses best seed with quite strong hasher, without shift component,
12/// which should lead to quite small size, but long construction time.
13#[derive(Clone, Copy)]
14pub struct SeedOnlyK(pub u8);
15
16#[inline(always)]
17fn best_seed_k<SC: SeedChooser>(k: u8, seed_chooser: SC, best_value: &mut usize, best_seed: &mut u16, used_values: &mut UsedValueMultiSetU8, keys: &[u64], conf: &Conf, seeds_num: u16) {
18    //assert!(keys.len() <= SMALL_BUCKET_LIMIT);  // seems to speeds up a bit
19    //let mut values_used_by_seed = arrayvec::ArrayVec::<_, SMALL_BUCKET_LIMIT>::new(); // Vec::with_capacity(keys.len());
20    let mut values_used_by_seed = Vec::with_capacity(keys.len());
21    for seed in SC::FIRST_SEED..seeds_num {    // seed=0 is special = no seed,
22        values_used_by_seed.clear();
23        for key in keys.iter().copied() {
24            let value = seed_chooser.f(key, seed, conf);
25            if used_values[value] == k { break; }
26            used_values.add(value);
27            values_used_by_seed.push(value);
28        }
29        if values_used_by_seed.len() == keys.len() {
30            let seed_value = values_used_by_seed.iter().sum();
31            if seed_value < *best_value {
32                *best_value = seed_value;
33                *best_seed = seed;
34            }
35        }
36        for v in &values_used_by_seed {
37            used_values[*v] -= 1;
38        }
39    }
40}
41
42impl SeedChooser for SeedOnlyK {
43    type UsedValues = UsedValueMultiSetU8;
44
45    /// Returns maximum number of keys mapped to each output value; `k` of `k`-perfect function.
46    #[inline(always)] fn k(self) -> u8 { self.0 }
47
48    /// Returns output range of minimal (perfect or k-perfect) function for given number of keys.
49    #[inline(always)] fn minimal_output_range(self, num_of_keys: usize) -> usize { ceiling_div(num_of_keys, self.k() as usize) }
50
51    #[inline(always)] fn f(self, primary_code: u64, seed: u16, conf: &Conf) -> usize {
52        conf.f(primary_code, seed)
53    }
54
55    #[inline(always)]
56    fn best_seed(self, used_values: &mut Self::UsedValues, keys: &[u64], conf: &Conf, bits_per_seed: u8) -> u16 {
57        let mut best_seed = 0;
58        let mut best_value = usize::MAX;
59        best_seed_k(self.0, self, &mut best_value, &mut best_seed, used_values, keys, conf, 1<<bits_per_seed);
60        if best_seed != 0 { // can assign seed to the bucket
61            for key in keys {               
62                used_values.add(conf.f(*key, best_seed));
63            }
64        };
65        best_seed
66    }
67}
ph_temp/phast/seed_chooser/k.rs

ph_temp/phast/seed_chooser/
k.rs
