javascript - 无需蛮力即可生成随机且唯一的 4 位代码

Question

我正在构建一个应用程序，我需要在我的一个功能中生成随机且唯一的 4 位代码。显然，从 0000 到 9999 的范围是有限的，但是每天都会删除整个列表，并且每天我需要的代码数量不会超过可用的代码数量，这意味着每天都有可能拥有唯一的代码。实际上，我每天可能只需要几百个代码。

我现在编码的方式是简单的蛮力方式，即生成一个随机的 4 位数字，检查该数字是否存在于数组中，如果存在，则生成另一个数字，如果不存在' t，返回生成的数字。

由于它是 4 位数字，因此运行时并不算太疯狂，而且我每天主要生成几百个代码，因此不会出现我生成 9999 个代码并且我不断随机生成数字的情况找到最后一个。

如果可以使问题变得更容易，也可以在其中包含字母而不是数字。

除了我的蛮力方法，还有什么更有效的方法？

谢谢!

Answer 1

由于您的值数量有限，可以轻松放入内存，我知道的最简单方法是创建一个可能值的列表并随机选择一个，然后将其从列表中删除，这样就不会再次选择。这永远不会与以前使用的号码发生冲突:

function initValues(numValues) {
    const values = new Array(numValues);
    // fill the array with each value
    for (let i = 0; i < values.length; i++) {
        values[i] = i;
    }
    return values;
}

function getValue(array) {
    if (!array.length) {
        throw new Error("array is empty, no more random values");
    }
    const i = Math.floor(Math.random() * array.length);
    const returnVal = array[i];
    array.splice(i, 1);
    return returnVal;
}

// sample code to use it
const rands = initValues(10000);
console.log(getValue(rands));
console.log(getValue(rands));
console.log(getValue(rands));
console.log(getValue(rands));

这通过执行以下操作来工作:

1. 生成一个包含所有可能值的数组。
2. 当您需要一个值时，从具有随机索引的数组中选择一个。
3. 选择值后，将其从数组中移除。
4. 返回选定的值。
5. 项目从不重复，因为它们在使用时会从数组中移除。
6. 使用的值不会发生冲突，因为您始终只是从剩余的未使用值中选择一个随机值。
7. 这依赖于这样一个事实，即整数数组在 Javascript 中得到了很好的优化，因此对 10,000 个元素的数组执行 .splice() 仍然非常快(因为它可能只是 memmove说明)。

仅供引用，这可以通过使用类型化数组来提高内存效率，因为您的数字可以用 16 位值表示(而不是 double 的默认 64 位)。但是，您必须实现自己的 .splice() 版本并自己跟踪长度，因为类型化数组没有内置这些​​功能。

对于像这种内存使用成为问题的更大问题，我使用了 BitArray 来跟踪以前的值使用情况。

---

这是相同功能的类实现:

class Randoms {
    constructor(numValues) {
        this.values = new Array(numValues);
        for (let i = 0; i < this.values.length; i++) {
            this.values[i] = i;
        }
    }
    getRandomValue() {
        if (!this.values.length) {
            throw new Error("no more random values");
        }
        const i = Math.floor(Math.random() * this.values.length);
        const returnVal = this.values[i];
        this.values.splice(i, 1);
        return returnVal;
    }
}

const rands = new Randoms(10000);
console.log(rands.getRandomValue());
console.log(rands.getRandomValue());
console.log(rands.getRandomValue());
console.log(rands.getRandomValue());