rand-unique

一个无需std的crate，用于以O(1)时间和空间生成唯一的随机数序列。 RandomSequence 是一个非重复的伪随机序列生成器，可以直接索引序列中的第n个数字。

不提供密码学安全性。与no-std兼容。

每个 RandomSequence 的属性

• 唯一：序列将只包含每个数字一次；每个索引都有唯一的输出。
• 均匀分布：序列是伪均匀分布的。尚未出现在序列中的每个数字都有大致相同的概率成为序列中的下一个数字。
• 快速：计算序列中任何随机索引的值是时间和内存复杂度为O(1)的操作。
• 可索引： RandomSequence::n(index) 返回序列中给定位置的输出。
• 整数范围：支持 u8、u16、u32、u64 和 usize。输出可以分别转换为 i8、i16、i32、i64 和 isize。
• 终止和包装： RandomSequence::next() 的迭代器使用将在序列结束时终止。或者，RandomSequence::wrapping_next() 会在耗尽时回到序列的开始。
• 确定性：对于相同的种子，序列是确定性和可重复的。
  • RandomSequenceBuilder可以使用serde进行序列化以存储序列参数。必须启用serde功能。
  • RandomSequenceBuilder::new(seed_base, seed_offset)可用于使用特定种子进行实例化。
  • RandomSequenceBuilder::rand(prng)可用于使用随机种子进行实例化。必须启用rand功能。
  • RandomSequenceBuilder::into_iter()使用构建器定义的参数构建一个RandomSequence。配置相同的两个构建器将生成相同的序列，因此我们可以构建对同一序列的多个迭代器。

特性

此crate与no-std兼容。

• default-features: rand
• rand: 在RandomSequenceBuilder和RandomSequence上启用rand(&mut RngCore)辅助方法以使用随机种子进行初始化，这需要rand依赖项。可以省略，而是手动为RandomSequenceBuilder::seed()方法提供种子以进行实例化。
• serde: 为RandomSequenceBuilder启用serde Serialize和Deserialize支持，这需要serde依赖项。

示例

use std::collections::HashSet;
use rand::rngs::OsRng;
use rand_unique::{RandomSequence, RandomSequenceBuilder};

// Initialise a sequence from a random seed.
let config = RandomSequenceBuilder::<u16>::rand(&mut OsRng);
let mut sequence: RandomSequence<u16> = config.into_iter();

// Iterate over the sequence with next() and prev(), or index directly with n(i).
assert_eq!(sequence.next().unwrap(), sequence.n(0));
assert_eq!(sequence.next().unwrap(), sequence.n(1));
assert_eq!(sequence.next().unwrap(), sequence.n(2));

// Get the current index, if the sequence is not yet exhausted.
assert_eq!(sequence.index(), Some(3));
assert!(!sequence.exhausted());

// Initialise a new RandomSequence iterator over the same sequence.
let sequence_2 = config.into_iter();
assert_eq!(sequence_2.n(0), sequence.n(0));
assert_eq!(sequence_2.index(), Some(0));

// Consume the iterator, and show outputs are unique across the entire type.
// With support for u8, u16, u32, u64, and usize.
let nums: HashSet<u16> = sequence_2.collect();
assert_eq!(nums.len(), u16::MAX as usize + 1);

// Serialise the config to reproduce the same sequence later.
// Requires the "serde" feature to be enabled.
// let config = serde_json::to_string(&sequence.config).unwrap();

输出分布

未来的工作可能包括对输出分布进行更严格的分析。目前，以下图表显示了RandomSequence<u16>的大致均匀分布。

/// `p` is chosen to be the largest number satisfying:
/// - a prime number
/// - that satisfies p = 3 mod 4 (`p % 4 == 3`)
/// - that fits in the datatype chosen, in this example `u64`
const PRIME: u64 = 18446744073709551427;

/// Simplified example of the quadratic residue function, taking input `x` for prime `PRIME`.
fn permute_qpr(x: u64) -> u64 {
    // we choose x to be the largest prime number of the type, and so there are a small handful
    // of numbers in the datatype which are larger than p. We map them directly to themselves.
    if x > PRIME {
        return x;
    }

    // compute the residue, in the real method we're careful to avoid integer overflow, omitted here
    // for clarity.
    let residue = (x * x) % PRIME;

    // the residue is unique for all x <= p/2; and so p-residue is also unique for x > p/2.
    if x <= PRIME / 2 {
        residue
    } else {
        PRIME - residue
    }
}

/// Randomly selected variables to introduce further noise in the output generation.
const OFFSET_NOISE: u64 = 0x46790905682f0161;
const XOR_NOISE: u64 = 0x5bf0363546790905;

/// We can then use this permutation function [permute_qpr] to build our number generator `n(x)`.
fn n(x: u64) -> u64 {
    // function sequence: permute_qpr, wrapping addition, xor, permute_qpr
    // care is taken in the real implementation to use wrapping addition, omitted here for clarity.
    permute_qpr((permute_qpr(x) + OFFSET_NOISE) ^ XOR_NOISE)
}