将整数转换为随机但确定性可重复的选择

Question

如何将无符号整数（代表用户 ID）转换为随机但实际上是确定性可重复的选择？必须以相等的概率选择该选项（与输入整数的分布无关）。例如，如果我有 3 个选择，即 [0, 1, 2]，用户 ID 123 可能总是被随机分配到选项 2，而用户 ID 234 可能总是被分配到选项 1。

需要跨语言和跨平台的算法重现性。除非有更好的方法，否则我倾向于使用哈希函数和模数。这是我拥有的：

>>> num_choices = 3
>>> id_num = 123
>>> int(hashlib.sha256(str(id_num).encode()).hexdigest(), 16) % num_choices
2

我使用的是最新的稳定版 Python 3. 请注意，此问题与的相关问题类似但不完全相同。

Answer 1

使用散列和取模

import hashlib

def id_to_choice(id_num, num_choices):
    id_bytes = id_num.to_bytes((id_num.bit_length() + 7) // 8, 'big')
    id_hash = hashlib.sha512(id_bytes)
    id_hash_int = int.from_bytes(id_hash.digest(), 'big')  # Uses explicit byteorder for system-agnostic reproducibility
    choice = id_hash_int % num_choices  # Use with small num_choices only
    return choice

>>> id_to_choice(123, 3)
0
>>> id_to_choice(456, 3)
1

备注：

内置 hash 不能使用方法，因为它可以保留输入的分布，例如hash(123)。或者，当 Python 重新启动时，它可以 return 不同的值，例如hash('123').
为了将 int 转换为字节，bytes(id_num) 可以工作，但效率非常低，因为它 return 是一个空字节数组，因此不能使用它。使用 int.to_bytes 更好。使用 str(id_num).encode() 可以，但会浪费几个字节。
诚然，使用模数并不能提供完全一致的概率，[1][2] 但这对这个应用程序来说应该不会有太大偏差，因为 id_hash_int 预计会非常大并且num_choices 被认为是小的。

使用随机

random module can be used with id_num as its seed, while addressing concerns surrounding both thread safety 和连续性。以这种方式使用 randrange 与散列种子和取模相当并且更简单。

使用这种方法，不仅跨语言的可再现性是一个问题，Python 多个未来版本的可再现性也可能是一个问题。因此不推荐。

import random

def id_to_choice(id_num, num_choices):
    localrandom = random.Random(id_num)
    choice = localrandom.randrange(num_choices)
    return choice

>>> id_to_choice(123, 3)
0
>>> id_to_choice(456, 3)
2

Answer 2

最简单的方法是对user_id取模选项数：

choice = user_id % number_of_options

非常简单快捷。但是，如果您知道 user_id，您可能会猜到一个算法。

此外，伪随机序列可以从 random 中获得，并使用用户常量（例如 user_id）播种：

>>> import random
>>> def generate_random_value(user_id):
...     random.seed(user_id)
...     return random.randint(1, 10000)
...
>>> [generate_random_value(x) for x in range(20)]
[6312, 2202, 927, 3899, 3868, 4186, 9402, 5306, 3715, 7586, 9362, 7412, 7776, 4244, 1751, 3424, 5924, 8553, 2970, 709]
>>> [generate_random_value(x) for x in range(20)]
[6312, 2202, 927, 3899, 3868, 4186, 9402, 5306, 3715, 7586, 9362, 7412, 7776, 4244, 1751, 3424, 5924, 8553, 2970, 709]
>>>

Answer 3

另一种方法是加密用户 ID。如果您保持加密密钥相同，则每个输入数字将加密为不同的输出数字，最大为您使用的密码的块大小。 DES 使用 64 位块，涵盖 ID 000000 到 18446744073709551615。这将为用户 ID 提供随机出现的替换，保证不会为两个不同的用户 ID 提供相同的 'random' 数字，因为加密是一对一的块值的一种排列。

Answer 4

抱歉我没有 Python 实现，但我在 Java 中有非常清晰、可读且不言而喻的实现，应该很容易将其转换为 Python努力。以下产生长的可预测均匀分布的序列，覆盖除零以外的所有范围

XorShift ( http://www.arklyffe.com/main/2010/08/29/xorshift-pseudorandom-number-generator )

public int nextQuickInt(int number) {
    number ^= number << 11;
    number ^= number >>> 7;
    number ^= number << 16;
    return number;
}

public short nextQuickShort(short number) {
    number ^= number << 11;
    number ^= number >>> 5;
    number ^= number << 3;
    return number;
}

public long nextQuickLong(long number) {
    number ^= number << 21;
    number ^= number >>> 35;
    number ^= number << 4;
    return number;
}

或XorShift128Plus（使用前需要将state0和state1重新设置为非零值，http://xoroshiro.di.unimi.it/xorshift128plus.c）

public class XorShift128Plus {

private long state0, state1; // One of these shouldn't be zero

public long nextLong() {
    long state1 = this.state0;
    long state0 = this.state0 = this.state1;
    state1 ^= state1 << 23;
    return (this.state1 = state1 ^ state0 ^ (state1 >> 18) ^ (state0 >> 5)) + state0;
}

public void reseed(...) {
    this.state0 = ...;
    this.state1 = ...;
}

}

或XorOshiro128Plus (http://xoroshiro.di.unimi.it/)

public class XorOshiro128Plus {

private long state0, state1; // One of these shouldn't be zero

public long nextLong() {
    long state0 = this.state0;
    long state1 = this.state1;
    long result = state0 + state1;
    state1 ^= state0;
    this.state0 = Long.rotateLeft(state0, 55) ^ state1 ^ (state1 << 14);
    this.state1 = Long.rotateLeft(state1, 36);
    return result;
}

public void reseed() {

}

}

或SplitMix64 (http://xoroshiro.di.unimi.it/splitmix64.c)

public class SplitMix64 {

private long state;

public long nextLong() {
    long result = (state += 0x9E3779B97F4A7C15L);
    result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9L;
    result = (result ^ (result >> 27)) * 0x94D049BB133111EBL;
    return result ^ (result >> 31);
}

public void reseed() {
    this.state = ...;
}
}

或XorShift1024Mult (http://xoroshiro.di.unimi.it/xorshift1024star.c) or Pcg64_32 (http://www.pcg-random.org/, http://www.pcg-random.org/download.html)

将整数转换为随机但确定性可重复的选择

Convert integer to a random but deterministically repeatable choice

python

random

hashlib

使用散列和取模

使用随机