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

Question

我有一个 array，我在其中取出 random 项

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

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

我也有一个 SQL table 像这样:

category_id
random_item

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

每个类别中没有重复的项目（项目a不能用category_id1计算两次，但项目a可以在category_id1和category_id2中计算）
项数将小于数组的长度。（这不是一个总是如此的要求）。

下面是一些虚构的代码：

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

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

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

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

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

用例

我能想到的一个简单的用例是这个（没用但简单）：

用户会看到一个可以select类别的界面。然后他们可以按下一个按钮，向其中添加一个随机项目。有多个用户，每个用户单独行动。因此，用户 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的算法。对于数据库中的每个类别存储，此算法的起始 seed/internal 状态知道如何以看起来随机的方式继续挑选 400K 数组的元素，但在该类别的所有 400K 元素都完成之前不要重复已选。

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

persist random items with no duplicates in constant time

sql

postgresql

rdbms