跳转到内容
标准库Zig 0.17.0官方原文
源码std/Random.zig

第 1 行

此处提供的引擎应使用外部来源初始化。 需要密码学安全性时务必使用 CSPRNG;否则,普通 PRNG 速度更快,且占用的栈空间少得多。

字段

ptr: *anyopaque

对此字段进行任何比较都可能导致非法行为,因为 随机数实现不具有任何关联状态时, 此字段可能被设为 undefined。

fillFn: *const fn (ptr: *anyopaque, buf: []u8) void

std.Random.array

函数

第 76 行

pub fn array(r: Random, comptime E: type, comptime N: usize) [N]E

参数

r: Random
E: type
N: usize

std.Random.Ascon

别名

第 18 行

别名目标 std.Random.Ascon

std.Random.assert

别名

第 9 行

别名目标 std.debug.assert

std.Random.boolean

函数

第 82 行

pub fn boolean(r: Random) bool

参数

r: Random

std.Random.bytes

函数

第 72 行

将随机字节读入指定缓冲区,直到填满。

pub fn bytes(r: Random, buf: []u8) void

参数

r: Random
buf: []u8

std.Random.ChaCha

别名

第 19 行

别名目标 std.Random.ChaCha

std.Random.DefaultCsprng

别名

第 16 行

密码学安全的随机数。

别名目标 std.Random.ChaCha

std.Random.DefaultPrng

别名

第 13 行

快速且无偏的随机数。

别名目标 std.Random.Xoshiro256

std.Random.enumValue

函数

第 91 行

从枚举中返回均匀分布的随机值。

注意,由于用作索引的 usize 表示因目标而异, 此函数不会在所有目标上产生一致结果。 更多说明参见 enumValueWithIndex。

pub inline fn enumValue(r: Random, comptime EnumType: type) EnumType

参数

r: Random
EnumType: type

std.Random.enumValueWithIndex

函数

第 105 行

从枚举中返回均匀分布的随机值。

使用指定的 Index 类型,为所有命名值构成的数组 生成索引,以确定返回值。 这使结果不依赖 usize 的表示。

如果不关心这一点,优先使用 enumValue。

关于此函数运行时间的说明,参见它在多数情况下 使用的 uintLessThan。

pub fn enumValueWithIndex(r: Random, comptime EnumType: type, comptime Index: type) EnumType

参数

r: Random
EnumType: type
Index: type

std.Random.float

函数

第 286 行

返回在 [0, 1) 范围内均匀分布的浮点值。

pub fn float(r: Random, comptime T: type) T

参数

r: Random
T: type

std.Random.floatExp

函数

第 355 行

返回速率参数为 1 的指数分布浮点数。

要使用其他速率参数,请使用:floatExp(...) / desiredRate。

pub fn floatExp(r: Random, comptime T: type) T

参数

r: Random
T: type

std.Random.floatNorm

函数

第 343 行

返回服从均值 0、标准差 1 的正态分布的浮点值。

若需其他参数,使用:floatNorm(...) * desiredStddev + desiredMean。

pub fn floatNorm(r: Random, comptime T: type) T

参数

r: Random
T: type

std.Random.init

函数

第 53 行

pub fn init(pointer: anytype, comptime fillFn: fn (ptr: @TypeOf(pointer), buf: []u8) void) Random

参数

fillFn: fn (ptr: @TypeOf(pointer), buf: []u8) void

std.Random.init.fill

函数

第 59 行

fn fill(ptr: *anyopaque, buf: []u8) void

参数

ptr: *anyopaque
buf: []u8

std.Random.int

函数

第 126 行

返回满足 minInt(T) <= i <= maxInt(T) 的随机整数 i。 i 均匀分布。

pub fn int(r: Random, comptime T: type) T

参数

r: Random
T: type

std.Random.intRangeAtMost

函数

第 269 行

返回均匀分布的随机整数,满足 at_least <= i <= at_most。 关于此函数的运行时间,参见它在大多数情况下使用的 uintLessThan 的说明。

pub fn intRangeAtMost(r: Random, comptime T: type, at_least: T, at_most: T) T

参数

r: Random
T: type
at_least: T
at_most: T

std.Random.intRangeAtMostBiased

函数

第 250 行

intRangeAtMostBiased 的常量时间实现。 此函数的结果可能存在偏差。

pub fn intRangeAtMostBiased(r: Random, comptime T: type, at_least: T, at_most: T) T

参数

r: Random
T: type
at_least: T
at_most: T

std.Random.intRangeLessThan

函数

第 232 行

返回均匀分布的随机整数,满足 at_least <= i < less_than。 有关此函数运行时间的说明,参见 其在大多数情况下使用的 uintLessThan。

pub fn intRangeLessThan(r: Random, comptime T: type, at_least: T, less_than: T) T

参数

r: Random
T: type
at_least: T
less_than: T

std.Random.intRangeLessThanBiased

函数

第 213 行

intRangeLessThan 的常数时间实现。 此函数的结果可能有偏。

pub fn intRangeLessThanBiased(r: Random, comptime T: type, at_least: T, less_than: T) T

参数

r: Random
T: type
at_least: T
less_than: T

std.Random.IoSource

容器

第 37 行

字段

io: std.Io

std.Random.IoSource.fill

函数

第 47 行

fn fill(ptr: *anyopaque, buffer: []u8) void

参数

ptr: *anyopaque
buffer: []u8

std.Random.IoSource.interface

函数

第 40 行

pub fn interface(this: *const @This()) std.Random

参数

this: *const @This()

std.Random.Isaac64

别名

第 21 行

别名目标 std.Random.Isaac64

std.Random.lcg

别名

第 29 行

别名目标 std.Random.lcg

std.Random.limitRangeBiased

函数

第 441 行

将随机整数 0 <= random_int <= maxValue(T) 转换为 0 <= result < less_than 的整数。 此函数会引入轻微偏差。

pub fn limitRangeBiased(comptime T: type, random_int: T, less_than: T) T

参数

T: type
random_int: T
less_than: T

std.Random.math

别名

第 7 行

别名目标 std.math

std.Random.maxInt

别名

第 10 行

别名目标 std.math.maxInt

std.Random.mem

别名

第 8 行

别名目标 std.mem

std.Random.MinArrayIndex

类型函数

第 453 行

返回 Index 和 usize 中较小的一个。

fn MinArrayIndex(comptime Index: type) type

参数

Index: type

std.Random.Pcg

别名

第 22 行

别名目标 std.Random.Pcg

std.Random.Random

别名

第 4 行

别名目标 std.Random

std.Random.RomuTrio

别名

第 26 行

别名目标 std.Random.RomuTrio

std.Random.Sfc64

别名

第 25 行

别名目标 std.Random.Sfc64

std.Random.shuffle

函数

第 369 行

将切片随机打乱。

注意,由于依赖将 usize 表示为索引,此操作在不同目标上 不会产生一致结果。 更多说明请参见 shuffleWithIndex。

pub inline fn shuffle(r: Random, comptime T: type, buf: []T) void

参数

r: Random
T: type
buf: []T

std.Random.shuffleWithIndex

函数

第 385 行

将切片打乱为随机顺序,使用指定类型的索引,以保持跨目标平台的分布性质。 断言索引类型能表示 buf.len。

使用指定的 Index 类型生成切片索引,该类型决定分布性质,使结果不依赖 usize 的表示方式。

若无需这一保证,优先使用 shuffle。

此函数使用 intRangeLessThan,其文档包含关于运行时间的说明。

pub fn shuffleWithIndex(r: Random, comptime T: type, buf: []T, comptime Index: type) void

参数

r: Random
T: type
buf: []T
Index: type

std.Random.SplitMix64

别名

第 27 行

别名目标 std.Random.SplitMix64

std.Random.std

别名

第 6 行

别名目标 std

std.Random.uintAtMost

函数

第 202 行

返回均匀分布的随机无符号整数,满足 0 <= i <= at_most。 有关此函数运行时间的说明,参见 其在大多数情况下使用的 uintLessThan。

pub fn uintAtMost(r: Random, comptime T: type, at_most: T) T

参数

r: Random
T: type
at_most: T

std.Random.uintAtMostBiased

函数

第 190 行

uintAtMost 的常数时间实现。 此函数的结果可能有偏。

pub fn uintAtMostBiased(r: Random, comptime T: type, at_most: T) T

参数

r: Random
T: type
at_most: T

std.Random.uintLessThan

函数

第 159 行

返回均匀分布的随机无符号整数,满足 0 <= i < less_than。 此函数假定底层 fillFn 产生均匀分布的值。在此假设下,函数运行时间呈指数分布。 若 fillFn 由真随机数生成器提供,严格来说,此函数运行时间没有上界。 不过,若 fillFn 由任意均匀分布的伪随机数生成器提供,则保证此函数最终返回。 若需要确定性的运行时间边界,请使用 uintLessThanBiased。

pub fn uintLessThan(r: Random, comptime T: type, less_than: T) T

参数

r: Random
T: type
less_than: T

std.Random.uintLessThanBiased

函数

第 145 行

uintLessThan 的常量时间实现。 此函数的结果可能存在偏差。

pub fn uintLessThanBiased(r: Random, comptime T: type, less_than: T) T

参数

r: Random
T: type
less_than: T

std.Random.weightedIndex

函数

第 407 行

随机选择 proportions 中的一个索引,各索引的 选中概率以对应比重加权。 相对于切片中第一个比重的索引,最后一个比重的索引 可能更容易被返回,反之亦然。

适用于从权重不等的切片中选择项目。 T 必须为可容纳 proportions 总和的数值类型。

pub fn weightedIndex(r: Random, comptime T: type, proportions: []const T) usize

参数

r: Random
T: type
proportions: []const T

std.Random.Xoroshiro128

别名

第 23 行

别名目标 std.Random.Xoroshiro128

std.Random.Xoshiro256

别名

第 24 行

别名目标 std.Random.Xoshiro256

std.Random.ziggurat

别名

第 28 行

别名目标 std.Random.ziggurat

源码

std/Random.zig

//! 此处提供的引擎应使用外部来源初始化。
//! 需要密码学安全性时务必使用 CSPRNG;否则,普通 PRNG
//! 速度更快,且占用的栈空间少得多。
const Random = @This();

const std = @import("std.zig");
const math = std.math;
const mem = std.mem;
const assert = std.debug.assert;
const maxInt = std.math.maxInt;

/// 快速且无偏的随机数。
pub const DefaultPrng = Xoshiro256;

/// 密码学安全的随机数。
pub const DefaultCsprng = ChaCha;

pub const Ascon = @import("Random/Ascon.zig");
pub const ChaCha = @import("Random/ChaCha.zig");

pub const Isaac64 = @import("Random/Isaac64.zig");
pub const Pcg = @import("Random/Pcg.zig");
pub const Xoroshiro128 = @import("Random/Xoroshiro128.zig");
pub const Xoshiro256 = @import("Random/Xoshiro256.zig");
pub const Sfc64 = @import("Random/Sfc64.zig");
pub const RomuTrio = @import("Random/RomuTrio.zig");
pub const SplitMix64 = @import("Random/SplitMix64.zig");
pub const ziggurat = @import("Random/ziggurat.zig");
pub const lcg = @import("Random/lcg.zig");

/// 对此字段进行任何比较都可能导致非法行为,因为
/// 随机数实现不具有任何关联状态时,
/// 此字段可能被设为 `undefined`。
ptr: *anyopaque,
fillFn: *const fn (ptr: *anyopaque, buf: []u8) void,

pub const IoSource = struct {
    io: std.Io,

    pub fn interface(this: *const @This()) std.Random {
        return .{
            .ptr = @constCast(this),
            .fillFn = fill,
        };
    }

    fn fill(ptr: *anyopaque, buffer: []u8) void {
        const this: *const @This() = @ptrCast(@alignCast(ptr));
        this.io.random(buffer);
    }
};

pub fn init(pointer: anytype, comptime fillFn: fn (ptr: @TypeOf(pointer), buf: []u8) void) Random {
    const Ptr = @TypeOf(pointer);
    assert(@typeInfo(Ptr) == .pointer); // 必须是指针
    assert(@typeInfo(Ptr).pointer.size == .one); // 必须是单项指针
    assert(@typeInfo(@typeInfo(Ptr).pointer.child) == .@"struct"); // 必须指向结构体
    const gen = struct {
        fn fill(ptr: *anyopaque, buf: []u8) void {
            const self: Ptr = @ptrCast(@alignCast(ptr));
            fillFn(self, buf);
        }
    };

    return .{
        .ptr = pointer,
        .fillFn = gen.fill,
    };
}

/// 将随机字节读入指定缓冲区,直到填满。
pub fn bytes(r: Random, buf: []u8) void {
    r.fillFn(r.ptr, buf);
}

pub fn array(r: Random, comptime E: type, comptime N: usize) [N]E {
    var result: [N]E = undefined;
    bytes(r, &result);
    return result;
}

pub fn boolean(r: Random) bool {
    return r.int(u1) != 0;
}

/// 从枚举中返回均匀分布的随机值。
///
/// 注意,由于用作索引的 `usize` 表示因目标而异,
/// 此函数不会在所有目标上产生一致结果。
/// 更多说明参见 `enumValueWithIndex`。
pub inline fn enumValue(r: Random, comptime EnumType: type) EnumType {
    return r.enumValueWithIndex(EnumType, usize);
}

/// 从枚举中返回均匀分布的随机值。
///
/// 使用指定的 `Index` 类型,为所有命名值构成的数组
/// 生成索引,以确定返回值。
/// 这使结果不依赖 `usize` 的表示。
///
/// 如果不关心这一点,优先使用 `enumValue`。
///
/// 关于此函数运行时间的说明,参见它在多数情况下
/// 使用的 `uintLessThan`。
pub fn enumValueWithIndex(r: Random, comptime EnumType: type, comptime Index: type) EnumType {
    comptime assert(@typeInfo(EnumType) == .@"enum");

    // 不使用整数到枚举的转换,因为枚举元素的值可能任意。
    // 改为随机选择该类型的一个值。
    const values = comptime std.enums.values(EnumType);
    comptime assert(values.len > 0); // 无法返回任何内容
    comptime assert(maxInt(Index) >= values.len - 1); // 无法访问所有值
    if (values.len == 1) return values[0];

    const index = if (comptime values.len - 1 == maxInt(Index))
        r.int(Index)
    else
        r.uintLessThan(Index, values.len);

    const MinInt = MinArrayIndex(Index);
    return values[@as(MinInt, @intCast(index))];
}

/// 返回满足 `minInt(T) <= i <= maxInt(T)` 的随机整数 `i`。
/// `i` 均匀分布。
pub fn int(r: Random, comptime T: type) T {
    const bits = @typeInfo(T).int.bits;
    const UnsignedT = @Int(.unsigned, bits);
    const ceil_bytes = @divCeil(bits, 8);
    const ByteAlignedT = @Int(.unsigned, ceil_bytes * 8);

    var rand_bytes: [ceil_bytes]u8 = undefined;
    r.bytes(&rand_bytes);

    // 也许使用小端序代替本机字节序可提高可移植性?
    // TODO: 若底层伪随机数生成器不支持跨字节序移植,则字节序可移植性没有意义。
    // TODO: 记录此库的字节序可移植性。
    const byte_aligned_result = mem.readInt(ByteAlignedT, &rand_bytes, .little);
    const unsigned_result: UnsignedT = @truncate(byte_aligned_result);
    return @bitCast(unsigned_result);
}

/// `uintLessThan` 的常量时间实现。
/// 此函数的结果可能存在偏差。
pub fn uintLessThanBiased(r: Random, comptime T: type, less_than: T) T {
    comptime assert(@typeInfo(T).int.signedness == .unsigned);
    assert(0 < less_than);
    return limitRangeBiased(T, r.int(T), less_than);
}

/// 返回均匀分布的随机无符号整数,满足 `0 <= i < less_than`。
/// 此函数假定底层 `fillFn` 产生均匀分布的值。在此假设下,函数运行时间呈指数分布。
/// 若 `fillFn` 由真随机数生成器提供,严格来说,此函数运行时间没有上界。
/// 不过,若 `fillFn` 由任意均匀分布的伪随机数生成器提供,则保证此函数最终返回。
/// 若需要确定性的运行时间边界,请使用 `uintLessThanBiased`。
///
///
///
pub fn uintLessThan(r: Random, comptime T: type, less_than: T) T {
    comptime assert(@typeInfo(T).int.signedness == .unsigned);
    const bits = @typeInfo(T).int.bits;
    assert(0 < less_than);

    // 改编自:
    //   http://www.pcg-random.org/posts/bounded-rands.html
    //   “Lemire 的方法(加上我的一点调整)”
    var x = r.int(T);
    var m = math.mulWide(T, x, less_than);
    var l: T = @truncate(m);
    if (l < less_than) {
        var t = -%less_than;

        if (t >= less_than) {
            t -= less_than;
            if (t >= less_than) {
                t %= less_than;
            }
        }
        while (l < t) {
            x = r.int(T);
            m = math.mulWide(T, x, less_than);
            l = @truncate(m);
        }
    }
    return @intCast(m >> bits);
}

/// `uintAtMost` 的常数时间实现。
/// 此函数的结果可能有偏。
pub fn uintAtMostBiased(r: Random, comptime T: type, at_most: T) T {
    assert(@typeInfo(T).int.signedness == .unsigned);
    if (at_most == maxInt(T)) {
        // 拥有完整范围
        return r.int(T);
    }
    return r.uintLessThanBiased(T, at_most + 1);
}

/// 返回均匀分布的随机无符号整数,满足 `0 <= i <= at_most`。
/// 有关此函数运行时间的说明,参见
/// 其在大多数情况下使用的 `uintLessThan`。
pub fn uintAtMost(r: Random, comptime T: type, at_most: T) T {
    assert(@typeInfo(T).int.signedness == .unsigned);
    if (at_most == maxInt(T)) {
        // 拥有完整范围
        return r.int(T);
    }
    return r.uintLessThan(T, at_most + 1);
}

/// `intRangeLessThan` 的常数时间实现。
/// 此函数的结果可能有偏。
pub fn intRangeLessThanBiased(r: Random, comptime T: type, at_least: T, less_than: T) T {
    assert(at_least < less_than);
    const info = @typeInfo(T).int;
    if (info.signedness == .signed) {
        // 二进制补码使此运算相当直接。
        const UnsignedT = @Int(.unsigned, info.bits);
        const lo: UnsignedT = @bitCast(at_least);
        const hi: UnsignedT = @bitCast(less_than);
        const result = lo +% r.uintLessThanBiased(UnsignedT, hi -% lo);
        return @bitCast(result);
    } else {
        // 有符号实现也可正常工作,但这里可以使用更严格的算术运算符。
        return at_least + r.uintLessThanBiased(T, less_than - at_least);
    }
}

/// 返回均匀分布的随机整数,满足 `at_least <= i < less_than`。
/// 有关此函数运行时间的说明,参见
/// 其在大多数情况下使用的 `uintLessThan`。
pub fn intRangeLessThan(r: Random, comptime T: type, at_least: T, less_than: T) T {
    assert(at_least < less_than);
    const info = @typeInfo(T).int;
    if (info.signedness == .signed) {
        // 二进制补码使此运算相当直接。
        const UnsignedT = @Int(.unsigned, info.bits);
        const lo: UnsignedT = @bitCast(at_least);
        const hi: UnsignedT = @bitCast(less_than);
        const result = lo +% r.uintLessThan(UnsignedT, hi -% lo);
        return @bitCast(result);
    } else {
        // 有符号实现也可正常工作,但这里可以使用更严格的算术运算符。
        return at_least + r.uintLessThan(T, less_than - at_least);
    }
}

/// `intRangeAtMostBiased` 的常量时间实现。
/// 此函数的结果可能存在偏差。
pub fn intRangeAtMostBiased(r: Random, comptime T: type, at_least: T, at_most: T) T {
    assert(at_least <= at_most);
    const info = @typeInfo(T).int;
    if (info.signedness == .signed) {
        // 二进制补码使此运算相当直接。
        const UnsignedT = @Int(.unsigned, info.bits);
        const lo: UnsignedT = @bitCast(at_least);
        const hi: UnsignedT = @bitCast(at_most);
        const result = lo +% r.uintAtMostBiased(UnsignedT, hi -% lo);
        return @bitCast(result);
    } else {
        // 有符号实现也可正常工作,但这里可以使用更严格的算术运算符。
        return at_least + r.uintAtMostBiased(T, at_most - at_least);
    }
}

/// 返回均匀分布的随机整数,满足 `at_least <= i <= at_most`。
/// 关于此函数的运行时间,参见它在大多数情况下使用的
/// `uintLessThan` 的说明。
pub fn intRangeAtMost(r: Random, comptime T: type, at_least: T, at_most: T) T {
    assert(at_least <= at_most);
    const info = @typeInfo(T).int;
    if (info.signedness == .signed) {
        // 二进制补码使此运算相当直接。
        const UnsignedT = @Int(.unsigned, info.bits);
        const lo: UnsignedT = @bitCast(at_least);
        const hi: UnsignedT = @bitCast(at_most);
        const result = lo +% r.uintAtMost(UnsignedT, hi -% lo);
        return @bitCast(result);
    } else {
        // 有符号实现也可正常工作,但这里可以使用更严格的算术运算符。
        return at_least + r.uintAtMost(T, at_most - at_least);
    }
}

/// 返回在 [0, 1) 范围内均匀分布的浮点值。
pub fn float(r: Random, comptime T: type) T {
    // 为尾数生成均匀分布的随机值。
    // 再为指数生成带指数偏置的随机值。
    // 这样可覆盖范围内的每个可能值。
    switch (T) {
        f32 => {
            // 使用 23 个随机位作为尾数,其余随机位用于指数。
            // 若全部 41 位均为零,则继续生成随机位,
            // 直到找到置位的位,或已生成 126 位。
            const rand = r.int(u64);
            var rand_lz = @clz(rand);
            if (rand_lz >= 41) {
                @branchHint(.unlikely);
                rand_lz = 41 + @clz(r.int(u64));
                if (rand_lz == 41 + 64) {
                    @branchHint(.unlikely);
                    // 执行到此处的概率极其微小。
                    rand_lz += @clz(r.int(u32) | 0x7FF);
                }
            }
            const mantissa: u23 = @truncate(rand);
            const exponent = @as(u32, 126 - rand_lz) << 23;
            return @bitCast(exponent | mantissa);
        },
        f64 => {
            // 使用 52 个随机位作为尾数,其余位用于指数。
            // 若全部 12 位均为零,则继续生成随机位,直到
            // 找到置位,或已生成 1022 位。
            const rand = r.int(u64);
            var rand_lz: u64 = @clz(rand);
            if (rand_lz >= 12) {
                rand_lz = 12;
                while (true) {
                    // 此循环执行超过一次的概率极低。
                    const addl_rand_lz = @clz(r.int(u64));
                    rand_lz += addl_rand_lz;
                    if (addl_rand_lz != 64) {
                        @branchHint(.likely);
                        break;
                    }
                    if (rand_lz >= 1022) {
                        rand_lz = 1022;
                        break;
                    }
                }
            }
            const mantissa = rand & 0xFFFFFFFFFFFFF;
            const exponent = (1022 - rand_lz) << 52;
            return @bitCast(exponent | mantissa);
        },
        else => @compileError("unknown floating point type"),
    }
}

/// 返回服从均值 0、标准差 1 的正态分布的浮点值。
///
/// 若需其他参数,使用:floatNorm(...) * desiredStddev + desiredMean。
pub fn floatNorm(r: Random, comptime T: type) T {
    const value = ziggurat.next_f64(r, ziggurat.NormDist);
    switch (T) {
        f32 => return @floatCast(value),
        f64 => return value,
        else => @compileError("unknown floating point type"),
    }
}

/// 返回速率参数为 1 的指数分布浮点数。
///
/// 要使用其他速率参数,请使用:floatExp(...) / desiredRate。
pub fn floatExp(r: Random, comptime T: type) T {
    const value = ziggurat.next_f64(r, ziggurat.ExpDist);
    switch (T) {
        f32 => return @floatCast(value),
        f64 => return value,
        else => @compileError("unknown floating point type"),
    }
}

/// 将切片随机打乱。
///
/// 注意,由于依赖将 `usize` 表示为索引,此操作在不同目标上
/// 不会产生一致结果。
/// 更多说明请参见 `shuffleWithIndex`。
pub inline fn shuffle(r: Random, comptime T: type, buf: []T) void {
    r.shuffleWithIndex(T, buf, usize);
}

/// 将切片打乱为随机顺序,使用指定类型的索引,以保持跨目标平台的分布性质。
/// 断言索引类型能表示 `buf.len`。
///
/// 使用指定的 `Index` 类型生成切片索引,该类型决定分布性质,使结果不依赖 `usize` 的表示方式。
///
/// 若无需这一保证,优先使用 `shuffle`。
///
/// 此函数使用 `intRangeLessThan`,其文档包含关于运行时间的说明。
///
///
///
///
pub fn shuffleWithIndex(r: Random, comptime T: type, buf: []T, comptime Index: type) void {
    const MinInt = MinArrayIndex(Index);
    if (buf.len < 2) {
        return;
    }

    // `i <= j < max <= maxInt(MinInt)`
    const max: MinInt = @intCast(buf.len);
    var i: MinInt = 0;
    while (i < max - 1) : (i += 1) {
        const j: MinInt = @intCast(r.intRangeLessThan(Index, i, max));
        mem.swap(T, &buf[i], &buf[j]);
    }
}

/// 随机选择 `proportions` 中的一个索引,各索引的
/// 选中概率以对应比重加权。
/// 相对于切片中第一个比重的索引,最后一个比重的索引
/// 可能更容易被返回,反之亦然。
///
/// 适用于从权重不等的切片中选择项目。
/// `T` 必须为可容纳 `proportions` 总和的数值类型。
pub fn weightedIndex(r: Random, comptime T: type, proportions: []const T) usize {
    // 此实现先对各权重求和,再在 [0, sum) 内
    // 随机选择一个点。随后遍历各权重并累加,
    // 直至累加值大于该随机点。

    const sum = s: {
        var sum: T = 0;
        for (proportions) |v| sum += v;
        break :s sum;
    };

    const point = switch (@typeInfo(T)) {
        .int => |int_info| switch (int_info.signedness) {
            .signed => r.intRangeLessThan(T, 0, sum),
            .unsigned => r.uintLessThan(T, sum),
        },
        // 注意避免精度误差导致数值略大于 sum
        .float => @min(r.float(T) * sum, sum - std.math.floatEps(T)),
        else => @compileError("weightedIndex does not support proportions of type " ++
            @typeName(T)),
    };

    assert(point < sum);

    var accumulator: T = 0;
    for (proportions, 0..) |p, index| {
        accumulator += p;
        if (point < accumulator) return index;
    } else unreachable;
}

/// 将随机整数 0 <= random_int <= maxValue(T) 转换为 0 <= result < less_than 的整数。
/// 此函数会引入轻微偏差。
///
pub fn limitRangeBiased(comptime T: type, random_int: T, less_than: T) T {
    comptime assert(@typeInfo(T).int.signedness == .unsigned);
    const bits = @typeInfo(T).int.bits;

    // 改编自:
    //   http://www.pcg-random.org/posts/bounded-rands.html
    //   “整数乘法(有偏)”
    const m = math.mulWide(T, random_int, less_than);
    return @intCast(m >> bits);
}

/// 返回 `Index` 和 `usize` 中较小的一个。
fn MinArrayIndex(comptime Index: type) type {
    const index_info = @typeInfo(Index).int;
    assert(index_info.signedness == .unsigned);
    return if (index_info.bits >= @typeInfo(usize).int.bits) usize else Index;
}

test {
    std.testing.refAllDecls(@This());
    _ = @import("Random/test.zig");
}