【Rust日报】2021-03-30 用 Bevy 实现节奏大师

用 Bevy 实现节奏大师

@ChaoBots 张老师最近决定用 Bevy 复刻 bevy_rhythm并且将其更新至 Bevy 最新的 API，感兴趣的小伙伴可以前往B站学习 第一集,第二集

​​https://github.com/guimcaballero/bevy_rhythm​​

​​https://www.bilibili.com/video/BV1LX4y1G7wr​​

​​https://www.bilibili.com/video/BV1tb4y1Q71a​​

蓄水池抽样算法改进 - 面向抽奖场景保证等概率性

小编周末回顾了一下以前做的一个蓄水池抽样算法的研究，发现还有一个不足之处在于蓄水池在填充完成之前顺序是故定的；而现实中的蓄水池在填充的时候水流的流向是可以打乱的；于是仿照后蓄水池抽样算法的后续流程，添加了在填充蓄水池时进行 shuffling 的逻辑：

fn sample(&mut self, it: Self::Item) -> (bool, Option<Self::Item>) {
let lucky_cap = self.lucky.capacity();

self.total += 1;

// 概率渐小的随机替换
let r = random::<usize>() % self.total + 1;
let mut replaced = None;
if r <= lucky_cap {
replaced = self.lucky[r - 1].take();
self.lucky[r - 1] = Some(it);
}

if self.total <= lucky_cap && r < self.total {
self.lucky[self.total - 1] = replaced.take();
}

(r <= lucky_cap, replaced)
}

如果到最后还是不够人数填充，用 None 来填充进一步打乱顺序：

let mut final_lucky = self.lucky.into_iter().collect::<Vec<Option<P>>>();
let mut i = self.total;
while i < lucky_cap {
i += 1;

// 概率渐小的随机替换
let r = random::<usize>() % i + 1;
if r <= lucky_cap {
final_lucky[i - 1] = final_lucky[r - 1].take();
}
}

更完整的思路与代码 demo 实现请转至原文。

​​https://huangjj27.github.io/reservoir.html​​