根据受欢迎程度选择项目:避免美化排序

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？如何将相同的内容应用于循环标头建议？

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  <-- sum

how 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