防止生产者突发事件的算法
我有以下几点：
- 一个产生随机整数的生产者(大约每分钟一个)。例: 154609722148751
- 一个消费者一个一个地消费整数。消费量约为3秒。
有时制片人会变得疯狂，只会很快地产生一种“类”的数字，然后恢复正常。例: 6666666666666666666666666666666666666666666666675444696在1秒内。
我的目标是有尽可能低的不同类型的数字不消费。比如说，在前面的样本中，我有：
- 很多“6”没有被消耗
- 一个'7‘没有被消耗
- 一个'5‘没有被消耗
- 三'4‘未被消耗
- 一个'9‘没有被消耗
如果我使用一个简单的FIFO算法，我将在所有的“6”被消耗之前等待很长一段时间。我更喜欢将其他数字“预先化”，然后消费“6”。
这样的算法是否已经存在？(C#实现优先考虑)
目前，我正在考虑这个算法：
- 为每个数字设置一个队列(Q0、Q1、Q2 .、Q9)
- 顺序地为每个队列排出一个项： 私有int _currentQueueId；私有Queue[] _allQueues；公共T GetNextItemToConsume() {//我们假定至少有一个项要使用，并且不需要锁查找= false；而(！found ){ var nextQueue = _allQueues_currentQueueId++ % 10；if(nextQueue.Count > 0)返回nextQueue.DeQueue()；}}
你有比这个更好的算法吗？(或任何想法)
NB1 :我在消费过程中没有领先优势(也就是说，我不能提高消费速度，也不能增加消费线程的数量。)(事实上，无限的消耗速度可以解决我的问题)
NB2 :确切的时间数据不相关，但我们可以假设消费比生产快十倍
NB3 :我对制片人的“疯狂”行为没有头绪，事实上，这是一种正常(但不那么频繁)的生产行为。
回答 2
Stack Overflow用户
发布于 2013-11-06 07:54:29
这里有一个比我上面的评论更完整的例子：
sealed class Item {
public Item(int group) {
ItemGroup = group;
}
public int ItemGroup { get; private set; }
}
Item TakeNextItem(IList<Item> items) {
const int LowerBurstLimit = 1;
if (items == null)
throw new ArgumentNullException("items");
if (items.Count == 0)
return null;
var item = items.GroupBy(x => x.ItemGroup)
.OrderBy(x => Math.Max(LowerBurstLimit, x.Count()))
.First()
.First();
items.Remove(item);
return item;
}我在这里的想法是根据项目的频率排序，然后从频率最低的项目中提取。这与您使用多个队列的想法相同，但它是动态计算的。如果有多组具有相同的频率，它将采取最古老的项目。(假设GroupBy和OrderBy是稳定的。他们正在实践中，但我不确定文件中是否有这样的规定)
如果要按时间顺序处理项，则增加LowerBurstLimit，除非队列中有超过LowerBurstLimit项的项。
为了测量我刚刚在LinqPad中创建这个快速代码的时间。
(埃里克·利珀特:请忽略这部分：-)
void Main()
{
var rand = new Random();
var items = Enumerable.Range(1, 1000)
.Select(x => { // simulate burst
int group = rand.Next(100);
return new Item(group < 90 ? 1 : (group % 10));
})
.ToList();
var first = TakeNextItem(items); // JIT
var sw = new Stopwatch();
sw.Start();
while (TakeNextItem(items) != null) {
}
sw.Stop();
Console.WriteLine("Elapsed: {0} ms", sw.ElapsedMilliseconds);
}当我用1000件物品运行这段代码时，我的3岁笔记本电脑需要大约80毫秒的时间。即平均每“取”80微升。
GroupBy应该是O( N *M)，OrderBy O(M*LogM)，移除O(N) (N=average队列长度，组的M=number )，因此性能应该与N成线性关系，即一个10000项队列每“取”需要800s(我在测试中得到了~700s的10000个条目)。
Stack Overflow用户
发布于 2013-11-06 09:16:52
正如您所提到的，我将使用这10个队列，并根据特定队列中存在的元素数量，从统计数据中选择要从中脱列的队列。元素数量最多的队列更有可能被选择为去队列。
为了获得更好的perf，您需要跟踪所有队列中元素的总数。对于每个去队列操作，在0和总计数-1之间绘制一个随机的int X，这将告诉您从哪个队列中去队列(通过队列循环从X中减去队列中的元素数，直到小于零，然后选择该队列)。
https://stackoverflow.com/questions/19797241
复制相似问题
腾讯云开发者
