固定任意长度数组的低内存伪随机洗牌

Question

上下文：我正在为基于微控制器的嵌入式系统编写 external SRAM tester。没有安全性，不涉及密码学。为了可重复访问 "as-non-consecutive-as-possible" 内存位置，我正在寻找

的实现

y = shuffle(x)，获取并返回一个介于 0 和固定 N = 2^16 - 1

之间的整数

它本身可能不会使用大量 RAM，例如一个天真的混洗地址数组会。从好的方面来说，它可以很慢。没有对非连续的严格定义——它是关于上下颠簸地址线，寻找印刷电路板的焊接和其他故障。建议？

到目前为止我找到了 Knuth shuffle a.k.a. Fisher-Yates shuffle。

晚编辑：我想我正在寻求最大化汉明距离。 “Anti-Grey code”?

Answer 1

我建议实施 Xorshift 或类似的东西。它们速度快，需要的内存少，可以构造成具有较长的周期，并且满足许多随机性测试。

另一种方法是将 0..(n-1) 范围内的每个数字唯一地映射到该范围内的另一个数字。正如我在 this answer.

中描述的那样，使用模乘逆可以很容易地做到这一点

Answer 2

我同意 Jim Mischel 的观点，xorshift 是快速非加密 PRNG 的一个很好的候选者。需要仔细选择系数以实现完整循环，其中包括除 0 以外的所有值。

由于您在问题中将问题连接到 16 位，这里有一个用 Ruby 编写的 16 位实现，但很容易移植到您喜欢的任何其他地方：

# << is shift left, >> is shift right, ^ is bitwise XOR, & is bitwise AND

MASK_16 = (1 << 16) - 1

def xorshift(x)
  x ^= x << 7 & MASK_16
  x ^= x >> 9
  x ^= x << 8 & MASK_16
  return x
end

counter = 0
x = 1
y = 1

# Floyd's "Tortoise and Hare" cycle-finding algorithm shows
# the generator to be full cycle for 16 bits, excluding zero.
loop do
  counter += 1
  x = xorshift(x)
  y = xorshift(xorshift(y))
  break if x == y
end
puts counter   # => 65535

固定任意长度数组的低内存伪随机洗牌

low-memory pseudo-random shuffle for fixed arbitrary length array

algorithm

random

shuffle

hamming-distance

gray-code