基准测试

• CPU: AMD Ryzen™ 5 5600G with Radeon™ Graphics x 12
• RAM: 58.8 GiB
• OS: Guix System, 64-bit

用法

use fastset::{set, Set};
use nanorand::WyRand;

   let mut set = set![5, 10, 15, 20, 25, 30]; // Initialize set with elements
   assert!(set.contains(&5)); // Check for element presence

   set.insert(35); // Insert a new element
   assert!(set.contains(&35));

   set.remove(&5); // Remove an element
   assert!(!set.contains(&5));

   if let Some(taken) = set.take(&10) { // Remove and return an element
       assert_eq!(taken, 10);
   }

   let mut rng = WyRand::new();
   if let Some(element) = set.random(&mut rng) { // Get a random element
       set.remove(&element); // Remove the randomly selected element
       assert!(!set.contains(&element));
   }

   println!("Set: {:?}, Length: {}", set, set.len()); // Display the set and its length

Delphic 集合

fastset::Set，在此实现中，满足德尔菲集[1]、[2]的条件。

设Ω为一个离散宇宙。一个集合（S ⊆ Ω）如果能在O(log |Ω|)时间内支持以下操作，则被视为德尔菲家族的成员：

• 成员资格：验证是否存在元素（x ∈ Ω）属于（S）。
• 基数：确定（S）的大小，即（|S|）。
• 抽样：从（S）中抽取一个均匀随机样本。

在src/set.rs中的单元测试使用基本的卡方检验验证了均匀抽样的属性。

use fastset::Set;
use nanorand::WyRand;
use statrs::distribution::{ChiSquared, ContinuousCDF};

fn sampling_is_uniformly_at_random() {
    const SAMPLES: usize = 1_000_000;
    const EDGE_OF_THE_UNIVERSE: usize = 10000;

    let elements = (1..=EDGE_OF_THE_UNIVERSE).collect::<Vec<_>>();
    let set = Set::from(elements.clone());
    let mut rng = WyRand::new_seed(42u64);
    let mut counts = vec![0f64; elements.len()];

(0..SAMPLES).for_each(|_| {
   if let Some(value) = set.random(&mut rng) {
       counts[value - 1] += 1.0;
   }
});

    let e = SAMPLES as f64 / elements.len() as f64;
    let statistic: f64 = counts.iter().map(|&o| { (o - e) * (o - e) / e }).sum();

    let dof = elements.len() - 1;
    let chi = ChiSquared::new(dof as f64).unwrap();
    let acceptable = chi.inverse_cdf(0.99);

    // Null hypothesis: Elements are sampled uniformly at random
    assert!(
        statistic < acceptable,
        "Chi-square statistic {} is greater than what's acceptable ({})",
        statistic,
        acceptable,
    );
}

参考文献

[1]: Chakraborty, Sourav, N. V. Vinodchandran, and Kuldeep S. Meel. "Distinct Elements in Streams: An Algorithm for the (Text) Book." arXiv预印本 arXiv:2301.10191 (2023).

[2]: Meel, Kuldeep S., Sourav Chakraborty, and N. V. Vinodchandran. "Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size." 第41届ACM SIGMOD-SIGACT-SIGAI数据库系统原理研讨会论文集。2022。