sql - 在恒定时间内保留没有重复项的随机项目

Question

我有一个数组，我在其中取出随机项

[a, b, c, d ,...]

function getRandomItem(){
   // return random item from array
}

我也有一个像这样的 SQL 表:

category_id
random_item

然后我想将该项目添加到表中。对于每个 category_id，我想要多行随机项目，例如:

• 每个类别中没有重复的项目(项目a不能与category_id 1重复，但项目a可以在category_id 1和category_id 2中)<
• 项目的数量将小于数组的长度。 (这不是一个总是如此的要求)。

---

下面是一些虚构的代码:

function persist(){
    var a = giveRandomItem();
    // $1 = a
    return execute("INSERT INTO mytable (random_item) values ($1) ON CONFLICT DO NOTHING RETURNING *", a)
}

 // usage
 var persisted;
 while(persisted === undefined){
    persisted = persist();
 }

问题在于它不是常数时间。有一个概率，我连续打了5次DB，因为item已经被持久化了。

对于每个类别，我预计最多 5k 个项目，我的数组长度为 400 000。所以概率很低。

我想找到一种仍然是恒定时间的方法，或者至少有一个可以尝试多个值的 sql 命令，以进一步降低概率。

---

用例

我能想到的一个简单的用例是这个(没用但简单):

用户会看到一个可以选择类别的界面。然后他们可以按下一个按钮，向其中添加一个随机项目。有多个用户，每个用户单独行动。因此，用户 1 可以将一个随机项目添加到类别 1，而用户 2 同时将一个随机项目添加到类别 2

编辑

我最终做了这样的事情:

在应用层:

shuffle(array);

function getRandomItem(seed, inc){
   let index = (seed + inc) % array.length;
   return array[index]
}

// usage:

let seed = item.category_id
let inc = category.item_count

这样我就没有重复，因为我说项目的数量低于数组的长度。此外，这些项目看起来是随机的，因为类别的 id 用作增量开始的种子。然而，这只是起点，因此并不是真正随机的，但适用于我的用例。

Answer 1

为保证您不会遇到冲突(违反唯一约束)，您应该改变您的方法。与其一次生成一个随机项，不如一次生成所有 5K 个项(然后批量插入)。批量插入也会大大加快速度。

如何从 400,000 个项目的数组中生成 5,000 个随机项目？

一种方法是shuffle the array并获取前 5K 个元素。然后是下一个 5K 元素，依此类推。这也将保证单独的批处理没有重复元素(直到所有 400K 都用完并且您再次从数组的开头开始)。

如果您希望元素有机会在批处理之间重复，则在批处理之间重新洗牌数组。

---

在评论中讨论后，您似乎需要一个生成 Cyclic permutations 的算法.对于数据库中的每个类别存储，该算法的起始种子/内部状态知道如何以看起来随机的方式继续选择 400K 数组的元素，但在选择该类别的所有 400K 元素之前不要重复。