C++:使用数组创建函数

Question

写一个函数有:

input: array of pairs (unique id and weight) length of N, K =< N  
output: K random unique ids (from input array)  

注意:在输出中多次出现某些Id的频率被调用的次数应该越多,它的权重就越大.示例:权重为5的id应出现在输出中比id为1的频率多5倍.此外,分配的内存量应在编译时知道,即不应分配额外的内存.

我的问题是:如何解决这个问题？

编辑
感谢大家的回复!
目前我无法理解对的重量如何影响输出对的出现频率,你能给我更清楚,"虚拟"解释它是如何工作的吗？

Answer 1

假设一个足够好的随机数生成器:

• 加权(total_weight)
• 重复K次:
  • 选择0到total_weight(selection)之间的数字
  • 找到第一对,其中从数组的开头到该对的所有权重之和大于或等于 selection
  • 将对的第一部分写入输出

您需要足够的存储空间来存储总重量.

Answer 2

好的,所以给你的输入如下:

(3, 7)
(1, 2)
(2, 5)
(4, 1)
(5, 2)

并且您想要选择一个随机数,以便每个id的权重反映在选择中,即从以下列表中选择一个随机数:

3 3 3 3 3 3 3 1 1 2 2 2 2 2 4 5 5

最初,我创建了一个临时数组,但这也可以在内存中完成,你可以通过将所有权重加起来来计算列表的大小= X,在这个例子中= 17

在[0,X-1]之间选择一个随机数,并通过循环遍历列表来计算应返回哪个id,对权重进行累加.说我有一个随机数8

(3, 7) total = 7 which is < 8
(1, 2) total = 9 which is >= 8 **boom** 1 is your id!

既然你需要K个随机唯一 ID,你可以从传递给你的初始数组创建一个哈希表.找到id后,将其从哈希中删除并继续算法.编辑请注意,您最初只创建一次hashmap!您的算法将在此处理,而不是查看数组.我没有放在顶部以保持答案清楚

只要您的随机计算没有秘密使用任何额外的内存,您将需要存储K个随机选择,其中<= N和原始数组的副本,因此运行时的最大空间要求为O(2*N)

渐近运行时是:

O(n) : create copy of original array into hastable +
(
   O(n) : calculate sum of weights +
   O(1) : calculate random between range +
   O(n) : cumulative totals
) * K random pickings
= O(n*k) overall

这是一个很好的问题 :)

Answer 3

我的简短回答是：绝不。

只是因为问题定义不正确。正如Axn敏锐地注意到的那样：

需求中存在一点矛盾。它规定 K <= N。但是当 K 接近 N 时，频率要求将与唯一性要求相矛盾。最坏的情况，如果 K=N，则所有元素都将被返回（即以相同的频率出现），无论其权重如何。

无论如何，当 K 相对于 N 相当小时，计算出的频率将非常接近理论值。

该任务可以分为两个子任务：

1. 生成具有给定分布的随机数（由权重指定）
2. 生成唯一的随机数

生成具有给定分布的随机数

1. 计算权重之和 ( sumOfWeights)
2. 从范围内生成随机数[1; sumOfWeights]
3. 找到一个数组元素，其中从数组开头开始的权重之和大于或等于生成的随机数

代码

#include <iostream>
#include <cstdlib>
#include <ctime>

// 0 - id, 1 - weight
typedef unsigned Pair[2];

unsigned Random(Pair* i_set, unsigned* i_indexes, unsigned i_size)
{
   unsigned sumOfWeights = 0;
   for (unsigned i = 0; i < i_size; ++i)
   {
      const unsigned index = i_indexes[i];
      sumOfWeights += i_set[index][2];
   }

   const unsigned random = rand() % sumOfWeights + 1;

   sumOfWeights = 0;
   unsigned i = 0;
   for (; i < i_size; ++i)
   {
      const unsigned index = i_indexes[i];
      sumOfWeights += i_set[index][3];
      if (sumOfWeights >= random)
      {
         break;
      }
   }

   return i;
}

生成唯一的随机数

众所周知的Durstenfeld-Fisher-Yates算法可用于生成唯一的随机数。看看这个很棒的解释。

它需要 N 字节的空间，因此如果在编译时定义 N 值，我们就可以在编译时分配必要的空间。

现在，我们必须将这两种算法结合起来。我们只需要使用我们自己的Random()函数而不是标准的rand()唯一数字生成算法。

代码

template<unsigned N, unsigned K>
void Generate(Pair (&i_set)[N], unsigned (&o_res)[K])
{
   unsigned deck[N];
   for (unsigned i = 0; i < N; ++i)
   {
      deck[i] = i;
   }

   unsigned max = N - 1;

   for (unsigned i = 0; i < K; ++i)
   {
      const unsigned index = Random(i_set, deck, max + 1);

      std::swap(deck[max], deck[index]);
      o_res[i] = i_set[deck[max]][0];
      --max;
   }
}

用法

int main()
{
   srand((unsigned)time(0));

   const unsigned c_N = 5;    // N
   const unsigned c_K = 2;    // K
   Pair input[c_N] = {{0, 5}, {1, 3}, {2, 2}, {3, 5}, {4, 4}}; // input array
   unsigned result[c_K] = {};

   const unsigned c_total = 1000000; // number of iterations
   unsigned counts[c_N] = {0};       // frequency counters

   for (unsigned i = 0; i < c_total; ++i)
   {
      Generate<c_N, c_K>(input, result);
      for (unsigned j = 0; j < c_K; ++j)
      {
         ++counts[result[j]];
      }
   }

   unsigned sumOfWeights = 0;
   for (unsigned i = 0; i < c_N; ++i)
   {
      sumOfWeights += input[i][1];
   }

   for (unsigned i = 0; i < c_N; ++i)
   {
      std::cout << (double)counts[i]/c_K/c_total  // empirical frequency
                << " | "
                << (double)input[i][1]/sumOfWeights // expected frequency
                << std::endl;
   }

   return 0;
}

输出

N = 5, K = 2

      Frequencies
Empiricical | Expected
 0.253813   | 0.263158
 0.16584    | 0.157895
 0.113878   | 0.105263
 0.253582   | 0.263158
 0.212888   | 0.210526

实际上忽略权重的极端情况

N = 5, K = 5

      Frequencies
Empiricical | Expected
 0.2        | 0.263158
 0.2        | 0.157895
 0.2        | 0.105263
 0.2        | 0.263158
 0.2        | 0.210526