一、线性扫描
最简单常用的算法，获取随机值，直接遍历。
public static int GetRandomIndexLinear(int[] list, int totalWeight)
{
var value = random.Next(0, totalWeight);
for (int i = 0; i < list.Length; i++)
{
value -= list[i];
if (value <= 0)
{
return i;
}
}
return -1;
}
二、预处理
首先对权重进行处理，填充PrepareAdRewardWeight。
public static (float, int)[] PrepareAdRewardWeight;
设置n个空桶，空桶容量为平均权重，按平均权重区分大权重与小权重，依次将小权重填入桶中，剩余部分由大权重的一部分填满，大权重减去填充部分后，如果小于平均值，则后续当做小权重处理。
一轮遍历后，填充好的数据为小权重的占比和大权重的索引。
public static void InitAdRewardWeight(int[] weightList)
{
var total = weightList.Sum();
int length = weightList.Length;
var avg = 1f * total / length;
List<(float, int)> smallAvg = new List<(float, int)>();
List<(float, int)> bigAvg = new List<(float, int)>();
for (int i = 0; i < weightList.Length; i++)
{
(weightList[i] > avg ? bigAvg : smallAvg).Add((weightList[i], i));
}
PrepareAdRewardWeight = new (float, int)[weightList.Length];
for (int i = 0; i < weightList.Length; i++)
{
if (smallAvg.Count > 0)
{
if (bigAvg.Count > 0)
{
PrepareAdRewardWeight[smallAvg[0].Item2] = (smallAvg[0].Item1 / avg, bigAvg[0].Item2);
bigAvg[0] = (bigAvg[0].Item1 - avg + smallAvg[0].Item1, bigAvg[0].Item2);
if (avg - bigAvg[0].Item1 > 0.0000001f)
{
smallAvg.Add(bigAvg[0]);
bigAvg.RemoveAt(0);
}
}
else
{
PrepareAdRewardWeight[smallAvg[0].Item2] = (smallAvg[0].Item1 / avg, smallAvg[0].Item2);
}
smallAvg.RemoveAt(0);
}
else
{
PrepareAdRewardWeight[bigAvg[0].Item2] = (bigAvg[0].Item1 / avg, bigAvg[0].Item2);
bigAvg.RemoveAt(0);
}
}
}
预处理结束后，获取随机值的复杂度为O(1)。
public static int GetRandomIndex()
{
var randomNum = random.NextDouble() * PrepareAdRewardWeight.Length;
int intRan = (int)Math.Floor(randomNum);
var p = PrepareAdRewardWeight[intRan];
if (p.Item1 > randomNum - intRan)
{
return intRan;
}
else
{
return p.Item2;
}
}
三、总结
随机目标的数量越大，第二种方法越高效。
