權重隨機分配器原理與實現

語言: CN / TW / HK

小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動。

本文同時參與 「掘力星計劃」   ,贏取創作大禮包,挑戰創作激勵金

關注公眾號:高效能架構探索。後臺回覆【pdf】,可以免費領取計算機經典書籍

假如有一個數組,需要隨機從該陣列中選擇一個元素輸出。只需生成一個介於 0 和集合長度減 1 之間的隨機數,並將其用作集合中的索引(如果它是陣列)以獲取隨機條目。選擇條目的機會對於集合中的每個條目都是相同的。這稱為均勻分佈或均勻分佈。

但是如果我們不希望每個條目都像其他條目一樣出現呢?假設我們正在建立一個問答遊戲,並且我們希望使用者之前做錯的問題比他或她做對的問題出現得更頻繁?這稱為加權隨機分佈,有時也稱為加權隨機選擇,並且有多種實現方法,例如隨機選擇器。

現實中,很多類似的需求,比如,在nginx中,假如我們需要對server的請求量進行控制,那麼只需要在nginx.conf中做如下配置即可:

http {       upstream cluster {           server a weight=1;           server b weight=2;           server c weight=4;       }       ... }

又比如,在筆者從事的廣告行業中,有個類似的產品需求,每個廣告都配置了權重,在廣告召回之後,需要根據權重的配置,選擇對應的廣告。

那麼,假如需要我們實現一個權重分配器,又該如何實現呢?

目標

假設有幾個數及其權重如下:

weights = {         'A': 2,         'B': 4,         'C': 3,         'D': 1 }

這意味著我們希望 B 出現的次數是 A 的兩倍,我們希望 A 出現的次數是 D 的兩倍。換句話說,如果我們生成十個隨機選擇,我們希望其中兩個是 A,其中四個是 B,等等(這當然不會發生在只有十個隨機選擇的情況下)。

實現

擴充套件式

最簡單的解決方案之一是簡單地擴充套件我們的集合,以便其中的每個條目出現的次數與其權重一樣多。 我們從具有相關權重的基本選擇集開始:

weights = {         'A': 2,         'B': 4,         'C': 3,         'D': 1 }

我們建立一個容器,將每個元素放入與其關聯權重相同的次數。 經過該種操作後,容器中的元素如下:

['A', 'A', 'B', 'B', 'B', 'B', 'C', 'C', 'C', 'D']

我們現在可以通過生成一個介於 0 和列表長度之間的隨機數從列表中進行隨機選擇,並將其用作列表中的索引來獲得我們的加權隨機選擇.

針對部分需求,此實現基本可以滿足,但是如果對於權重特別大的,該方案可能存在問題,比如權重為1000w或者更大,那麼可能會導致記憶體過大,那麼就需要另外一種實現方案。

{'A': 20140, 'C': 29880, 'B': 39986, 'D': 9994}

優點

  • 時間複雜度是O(1),這是最快的方式
  • 它允許相當容易和快速地更新權重。 如果我們想降低一個選擇的權重,我們只需掃描列表並根據需要刪除儘可能多的選擇。 增加權重或新增新選項甚至更簡單,因為我們可以在列表末尾新增任意數量的選項。 它們出現的順序無關緊要,即順序無關性
  • 實現簡單,易於理解

缺點

  • 對於較大的集合,或較大的權重值,這顯然會佔用太多記憶體。 優化它的一種可能方法是找到最大公約數,但這將需要更多的處理時間,並且會使更新我們的權重變得更慢

完整的程式碼實現如下:

struct Item { char val; int weight; }; char select(const std::vector<Item> &items) {   std::vector<char> v;   for (auto elem : items) {     v.insert(v.end(), elem.weight, elem.val);   }      int idx = rand() % v.size();   return v[idx]; }

就地選擇(無序)

除了像上面使用的方法那樣擴充套件集合,我們還可以保持集合的當前形式,並在迴圈中簡單地模擬集合的擴充套件。 為了做到這一點,我們首先必須知道集合的總權重。

int sum = 0; for (auto elem : items) {   sum += elem.weight; }

然後我們選擇一個介於 0 和總權重 - 1 之間的隨機值。 我們通過迴圈集合的元素並保持迄今為止我們看到的總值的分數來模擬我們在之前的方法中看到的擴充套件集合。 當該值大於我們選擇的隨機值時,我們就找到了我們的隨機選擇。

int rd = rand() % sum; int s = 0; for (auto elem : items) {   s += elem.weight;   if (s >= rd) {     break;   } }

優點

更新我們的權重集非常容易和快速。 新增和刪除專案; 降低和繼承權重:都一樣快。 我們所要做的就是關注我們的總權重,並在我們新增或刪除值或更改權重時更新或重新計算它。 此方法使用盡可能少的記憶體。 無需複製其中的元素

缺點

由於迴圈中增加了計算,選擇隨機值的速度稍慢。 我們的初始集合越大,這變得越慢。 選擇的複雜度是 O(n),其中 n 是集合中元素的數量。

完整的程式碼如下:

``` struct Item { char val; int weight; };

char select(const std::vector &items) {   int sum = 0;   for (auto elem : items) {     sum += elem.weight;   }      int rd = rand() % sum; int s = 0; char res; for (auto elem : items) {   s += elem.weight;   if (s >= rd) {     res = elem.val;     break;   } } return res; } ```

就地選擇(有序)

理論上,我們可以通過在開始選擇之前對集合進行排序來加速我們之前的就地演算法。 由於集合已排序,我們可以從末尾開始以相反的順序掃描它。 由於最高的權重將出現在集合的末尾,並且這些權重最有可能被隨機選擇,因此在從我們的集合中選擇隨機數時,我們可以提高速度。 我們在實踐中是否獲得速度提升取決於我們的初始權重集。

首先,我們對集合以權重進行排序。

std::sort(items.begin(), item.end(), [](item a, item b){   return a.weight < b.weight; };

排序之後,其內容如下:

[('D', 1), ('A', 2), ('C', 3), ('B', 4)]

然後進行權重選擇,程式碼如下:

``` int rd = rand() % sum; int s = sum; char res; for (int i = items.size() - 1; i >= 0; --i) {   res = items[i].val;   s -= items[i].weight;   if (s <= rd) {     break;   } }

return res; ```

優點

只要我們的集合至少有一個權重顯著大於其他權重,就可以提高未排序的選擇速度。

缺點

效能不一定有所提升,即由於引入了排序,那麼有可能使得該優化點提升的效能與排序導致的效能下降想抵消

完整程式碼如下:

``` struct Item { char val; int weight; }; char select(const std::vector &items) {   int sum = 0;   for (auto elem : items) {     sum += elem.weight;   }   int rd = rand() % sum; int s = sum; char res; for (int i = items.size() - 1; i >= 0; --i) {   res = items[i].val;   s -= items[i].weight;   if (s <= rd) {     break;   } }

return res; } ```

線段式

將w[i]對映到線段的位置,然後窮舉線段上的位置即可。

此解法與就地未排序型別,我們此處給出完整程式碼即可:

struct Item { char val; int weight; }; char select(const std::vector<Item> &items) {   int sum = 0;   std::vector<int> v;   for (auto elem : items) {     sum += elem.weight;     v.push_back(sum);   }   int rd = rand() % sum;   for (int i = 0; i < v.size(); ++i) {     if (rd <= v[i]) {       res = items[i].val;       break;     }   } return res; }

總結

如您所見,執行隨機加權選擇的方法有很多種。 每個方案都有自己的優點和缺點。 如果目標是快速選擇,且您的元素數量小,權重不是很大,則使用擴充套件方案。 如果需要降低記憶體使用,則不要使用擴充套件。 如果單純為了簡單,則使用擴充套件,就地(未排序) 或者 線段式