权重随机分配器

发表于 3年以前 | 总阅读数：377 次

假如有一个数组，需要随机从该数组中选择一个元素输出。只需生成一个介于 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<Item> &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<Item> &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;
}