堅持不重複隨機物品在固定時間

我一個一個array中，我拿出random項目堅持不重複隨機物品在固定時間

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

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

我也有一個SQL表所示：

category_id 
random_item

然後我想要將該項目添加到表格中。對於每一個category_id，我想如隨機項的多行：

有每個類別中沒有重複的項目（項目一個不能與CATEGORY_ID 1兩次身影，但是項可以在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次。

對於每個類別，我期望最大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用作增量開始的種子。但是，這只是出發點，因此它不是真正的隨機，但這適用於我的用例。

來源

2017-04-18 Ced

爲了保證您不會遇到衝突（唯一違反約束），您應該改變您的方法。不要一次生成一個隨機項目，而應該一次生成所有5K項目（然後將其批量插入）。大量插入也會大大加快速度。

如何從400K項目的數組中生成5K個隨機項目？

一種方法是shuffle the array並採取第一個5K元素。然後是下一個5K元素，依此類推。這也可以保證單獨的批次不具有重複元素（直到所有的400K都耗盡並且您從數組的開始再次開始）。

如果您希望元素有機會在批次之間重複，請在批次之間重新排列數組。

在評論中討論後，它看起來像你需要一個算法，產生Cyclic permutations。對於數據庫中的每個類別商店，這個算法的起始種子/內部狀態知道如何繼續選取400K數組的元素，使得它們看起來是隨機的，但是不要重複，直到所有類別的所有400K元素都被選中。

來源

2017-04-18 10:34:11

我相信這是行不通的。我在我的問題中添加了一個用例來更好地反映問題。你的回答將不起作用，因爲它假定我可以一次生成所有內容。我不能，項目是通過用戶輸入生成的。如果這使得sens。 – Ced

如果你堅持一個接一個地插入元素，那麼你應該改變你的'getRandomItem（）'函數的實現，以便它返回非重複元素。一種方法是再次洗牌400K數組，每次調用'getRandomItem（）'它會返回數組中的下一項。所以，主要想法是控制隨機生成。當您需要隨機項目時，按隨機順序預先生成400K陣列，然後依次從中讀取。它會保證沒有衝突，直到你遍歷所有400K元素。 –

它已經這樣做了。問題是類別的數量是未知的。用戶1可以發佈類別1中的項目。然後，隨機數組中的索引增加。一段時間過去了，而其他用戶發佈了其他類別（並且隨機數組中的索引增加了）。然後過了一段時間後，另一個用戶將一個項目發佈到第1類。問題是在此期間有其他類別發佈了40萬個項目，我們又回到了第1個項目。您是否看到這個問題？該索引不保證位於該類別不重複的地方。 – Ced

堅持不重複隨機物品在固定時間

回答

相關問題