4

我有以下内容：

  • 一个产生随机整数的生产者（大约每分钟一个）。例如：154609722148751
  • 一位消费者一一消费这些整数。消耗时间约为 3 秒。

制作人有时会发疯，很快就只制作一种“类型”的人物，然后恢复正常。例如：6666666666666666666666666666666666666666666666675444696 在 1 秒内。

我的目标是尽可能降低不消耗的不同类型的数字。说，在上一个示例中，我有：

  • 很多'6'没有消耗
  • 一个“7”未消耗
  • 一个“5”未消耗
  • 三个“4”未消耗
  • 一个“9”未消耗

如果我使用简单的 FIFO 算法，我将等待很长时间才能消耗所有“6”。我宁愿“优先考虑”其他数字，然后使用“6”。

这样的算法是否已经存在？（C# 实现是一个加号）

目前，我正在考虑这个算法：

  • 每个数字都有一个队列（Q0，Q1，Q2 ...，Q9）

  • 为每个队列顺序出列一项：

    private int _currentQueueId;
private Queue<T>[] _allQueues;

public T GetNextItemToConsume<T>()
{
    //We assume that there is at least one item to consume, and no lock needed
    var found = false;
    while(!found)
    {
    var nextQueue = _allQueues[_currentQueueId++ % 10];
    if(nextQueue.Count > 0)
        return nextQueue.DeQueue();
    }
}

你有比这个更好的算法吗？（或任何想法）

NB1：消费过程我没有主导权（也就是说我不能增加消费速度也不能增加消费线程的数量..）（确实无限的消费速度会解决我的问题）

NB2：确切的时间数字不相关，但我们可以假设消费比生产快十倍

NB3：我对制片人的“疯狂”行为没有主导权，实际上这是一种正常（但不那么频繁）的制作行为

4

2 回答 2

0

我将使用您提到的 10 个队列，并根据特定队列中存在的元素数量从统计上选择一个队列。元素数量最多的队列更有可能被选择出队。

为了获得更好的性能，您需要跟踪所有队列中元素的总数。对于每个出队操作，在 0 和总 count-1 之间绘制一个随机 int X，这将告诉您从哪个队列出队（循环通过队列从 X 中减去队列中的元素数，直到您低于零，然后选择该队列）。

于 2013-11-06T09:16:52.823 回答
0

这是一个比我上面的评论更完整的例子：

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 中创建这个快速代码的时间。
（Eric Lippert：请忽略这部分 :-)）

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 毫秒。即平均每次“Take”需要 80µs。

GroupBy 应该是 O(N*M)，OrderBy O(M*LogM) 和 Remove O(N)（N=平均队列长度，M=组数）所以性能应该随着 N 线性扩展。即 10000 个项目队列每次“Take”大约需要 800µs（我在测试中得到了大约 700µs 的 10000 个项目）

于 2013-11-06T07:54:29.127 回答