一运杭、線性掃描
最簡單常用的算法夫啊，獲取隨機值，直接遍歷辆憔。
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;
}
二涮母、預(yù)處理
首先對權(quán)重進行處理，填充PrepareAdRewardWeight躁愿。
public static (float, int)[] PrepareAdRewardWeight;
設(shè)置n個空桶，空桶容量為平均權(quán)重沪蓬，按平均權(quán)重區(qū)分大權(quán)重與小權(quán)重彤钟，依次將小權(quán)重填入桶中，剩余部分由大權(quán)重的一部分填滿跷叉，大權(quán)重減去填充部分后逸雹，如果小于平均值，則后續(xù)當做小權(quán)重處理云挟。
一輪遍歷后梆砸，填充好的數(shù)據(jù)為小權(quán)重的占比和大權(quá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);
}
}
}
預(yù)處理結(jié)束后园欣，獲取隨機值的復(fù)雜度為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;
}
}
三、總結(jié)
隨機目標的數(shù)量越大沸枯，第二種方法越高效日矫。
