c# - 根据受欢迎程度选择项目 : Avoiding a glorified sort

Question

我有一个网站，用户可以在其中发布建议并对建议进行投票。在发件人页面上，我最初列出了 10 个建议，标题每 7 秒获取一个新的随机建议。

我希望投票能够影响建议出现的概率，包括在 10 条建议列表和标题建议中。为此，我有一个小算法来计算受欢迎程度，同时考虑投票、年龄和其他一些因素(需要大量调整)。

无论如何，在运行算法后我有一个建议字典和流行指数，按流行度排序:

{ S = Suggestion1, P = 0.86  }
{ S = Suggestion2, P = 0.643 }
{ S = Suggestion3, P = 0.134 }
{ S = Suggestion4, P = 0.07  }
{ S = Suggestion5, P = 0.0   }
{ . . .}

我不希望这是一个美化的排序，所以我想在选择过程中引入一些随机元素。

简而言之，我希望流行度是建议从列表中被选中的概率。

有了完整的建议/受欢迎程度列表，我该如何根据概率选出 10 个？如何将其应用于循环 header 建议？

Answer 1

恐怕我不知道如何快速做到这一点，但如果你在内存中有集合，你可以这样做:

请注意，您无需对列表进行排序即可使该算法起作用。

1. 首先对所有概率求和(如果概率与流行度相关，只需对流行度数求和，我假设数值越大概率越高)
2. 计算 0 到但不包括该和的范围内的随机数
3. 从列表的一端开始遍历它
4. 对于每个元素，如果您生成的随机数小于流行度，则选择该元素
5. 如果不是，则从随机数中减去该元素的流行度，继续下一个

如果列表是静态的，您可以构建范围并进行一些二进制搜索，但如果列表不断变化，那么我不知道更好的方法。

这是一个示例 LINQPad演示的程序:

void Main()
{
    var list = Enumerable.Range(1, 9)
        .Select(i => new { V = i, P = i })
        .ToArray();
    list.Dump("list");

    var sum =
        (from element in list
         select element.P).Sum();

    Dictionary<int, int> selected = new Dictionary<int, int>();
    foreach (var value in Enumerable.Range(0, sum))
    {
        var temp = value;
        var v = 0;
        foreach (var element in list)
        {
            if (temp < element.P)
            {
                v = element.V;
                break;
            }

            temp -= element.P;
        }
        Debug.Assert(v > 0);
        if (!selected.ContainsKey(v))
            selected[v] = 1;
        else
            selected[v] += 1;
    }

    selected.Dump("how many times was each value selected?");
}

输出:

list [] (9 items)   V  P 1  1  2  2  3  3  4  4  5  5  6  6  7  7  8  8  9  9 45 45  <-- sumhow many times was each value selected? Dictionary<Int32,Int32> (9 items)  Key Value 1    1  2    2  3    3  4    4  5    5  6    6  7    7  8    8  9    9      45 <-- again, sum