scala - 如何找到适合 32 位整数的 n 的最大倍数
问题描述
我正在阅读Scala 中的函数式编程,但无法理解一段代码。我已经检查了这本书的勘误表,并且有问题的段落没有印刷错误。(实际上,它确实有错印,但错印并不影响我有疑问的代码。)
有问题的代码计算一个小于某个上限的伪随机非负整数。执行此操作的函数称为nonNegativeLessThan
。
trait RNG {
def nextInt: (Int, RNG) // Should generate a random `Int`.
}
case class Simple(seed: Long) extends RNG {
def nextInt: (Int, RNG) = {
val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL // `&` is bitwise AND. We use the current seed to generate a new seed.
val nextRNG = Simple(newSeed) // The next state, which is an `RNG` instance created from the new seed.
val n = (newSeed >>> 16).toInt // `>>>` is right binary shift with zero fill. The value `n` is our new pseudo-random integer.
(n, nextRNG) // The return value is a tuple containing both a pseudo-random integer and the next `RNG` state.
}
}
type Rand[+A] = RNG => (A, RNG)
def nonNegativeInt(rng: RNG): (Int, RNG) = {
val (i, r) = rng.nextInt
(if (i < 0) -(i + 1) else i, r)
}
def nonNegativeLessThan(n: Int): Rand[Int] = { rng =>
val (i, rng2) = nonNegativeInt(rng)
val mod = i % n
if (i + (n-1) - mod >= 0) (mod, rng2)
else nonNegativeLessThan(n)(rng2)
}
我无法理解以下代码nonNegativeLessThan
,如下所示:if (i + (n-1) - mod >= 0) (mod, rng2)
等。
这本书解释说,整个 if-else 表达式是必要的,因为简单地采用结果的 mod 的简单实现nonNegativeInt
会稍微偏向较低的值,因为 Int.MaxValue 不能保证是 n 的倍数。因此,此代码旨在检查生成的输出nonNegativeInt
是否大于适合 32 位值的 n 的最大倍数。如果生成的数字大于适合 32 位值的 n 的最大倍数,则函数将重新计算伪随机数。
详细地说,天真的实现如下所示:
def naiveNonNegativeLessThan(n: Int): Rand[Int] = map(nonNegativeInt){_ % n}
其中 map 定义如下
def map[A,B](s: Rand[A])(f: A => B): Rand[B] = {
rng =>
val (a, rng2) = s(rng)
(f(a), rng2)
}
重复一遍,这种幼稚的实现是不可取的,因为当 Int.MaxValue 不是 n 的完美倍数时,它会略微偏向较低的值。
所以,重申一下这个问题:下面的代码做了什么,它如何帮助我们确定一个数字是否小于适合 32 位整数的 n 的最大倍数?我在里面谈论这段代码nonNegativeLessThan
:
if (i + (n-1) - mod >= 0) (mod, rng2)
else nonNegativeLessThan(n)(rng2)
解决方案
事实上,如果在 Rust 中尝试相同的示例,编译器会对此发出警告(只是对正在执行多少静态检查的有趣比较)。当然,jwvh 的铅笔和纸方法绝对是正确的方法。
我们首先定义了一些类型别名,以使代码匹配更接近 Scala 代码(请原谅我的 Rust,如果它不是很地道的话)。
pub type RNGType = Box<dyn RNG>;
pub type Rand<A> = Box<dyn Fn(RNGType) -> (A, RNGType)>;
pub fn non_negative_less_than_(n: u32) -> Rand<u32> {
let t = move |rng: RNGType| {
let (i, rng2) = non_negative_int(rng);
let rem = i % n;
if i + (n - 1) - rem >= 0 {
(rem, rng2)
} else {
non_negative_less_than(n)(rng2)
}
};
Box::new(t)
}
编译器警告if nn + (n - 1) - rem >= 0
是:
warning: comparison is useless due to type limits
推荐阅读
- javascript - 改变对象 JavaScript 的结构
- java - 如何使用 java 在现有 json 文件中添加属性
- django - RESTful API:有外键发送到不同版本的 API 好不好?
- javascript - 使用 reactjs 将 script 标签附加到 head 标签
- python - python:从mysql表中选择
- r - 将文件夹移动到不同的文件夹
- angular - ng-select:在角度 6 中选择不适用于 ng-option
- deep-learning - 全连接层在深度学习中的作用是什么?
- javascript - 为什么我们不能在 Array.map() 中使用扩展运算符,还有什么可以替代展平数组?
- ruby-on-rails - 基于会话 id 的片段缓存