從一個集合中選擇N個隨機數

我有一個有序集（std :: set是精確的），它包含具有賦值權重的元素。我想從這個集合中隨機選擇N個元素，而更高權重的元素應該有更大的選擇概率。任何元素都可以選擇多次。從一個集合中選擇N個隨機數

我想盡可能有效地做到這一點 - 我想避免任何複製集（它可能會非常大），並在O（N）時間運行，如果有可能的話。我正在使用C++，並希望堅持僅STL + Boost解決方案。

有沒有人知道在STL/Boost中是否有函數執行這個任務？如果不是，如何實施？

2010-10-04 Karel Petranek

您需要計算（並可能緩存，如果您認爲性能）所有權重的總和。然後，生成N個隨機數，直到該值。最後，重複你的設置，計算你到目前爲止遇到的權重的總和。檢查所有（剩餘的）隨機數。如果數字位於總和的前一個值和下一個值之間，請插入該值中的值並刪除您的隨機數。當你的隨機數字列表爲空或者你已經到達集合的結尾時停止。

來源

2010-10-04 20:53:40

謝謝，這似乎表現確定在我的情況，看起來不錯。 – 2010-10-04 21:27:33

爲獲得最佳性能，請考慮將隨機值放置在有序集合中，並迭代一次，而不是針對源集合的每個值進行迭代。您不必從隨機集合中刪除值，只需增加迭代器即可。 – 2010-10-04 21:34:06

我不知道任何庫，但它聽起來像你有一個加權輪盤賭輪。以下是一些僞代碼的參考，儘管上下文與遺傳算法有關：http://www.cse.unr.edu/~banerjee/selection.htm

至於「儘可能高效」，這取決於數據的某些特性。在加權輪盤賭輪的應用中，當搜索索引時，您可以考慮使用二分法搜索。但是，輪盤的每個插槽的可能性並不相同，因此按照它們的權重來檢查它們可能是有意義的。

來源

2010-10-04 20:51:38

很大程度上取決於您願意花費多少額外的存儲空間來加快選擇。

如果您不願意使用任何額外的存儲空間，@Alex Emelianov的回答幾乎就是我想要發佈的內容。如果你願意使用一些額外的存儲空間（可能還有一個不同於std::set的數據結構），你可以創建一個樹（比如一個集合使用），但是在樹的每個節點上，你還可以存儲（加權）數量的項目在該節點的左側。這將使您可以將生成的數字映射到與對數（而非線性）複雜度相關的正確關聯值。

來源

2010-10-04 20:59:19

即使你的算法可能更快，我用Alex的答案，因爲它似乎不是一個性能瓶頸，它更容易實現:)感謝您的答案。 – 2010-10-04 21:29:49

從一個集合中選擇N個隨機數

回答

相關問題