c# - 为什么队列消耗这么多内存？

问题描述

基本上，在开始编码之前，我在 codewars 网站上做一个代码 kata有点“热身”，并注意到一个问题，我不知道是因为我的代码，还是只是普通的事情。

public static string WhoIsNext(string[] names, long n)
{
    Queue<string> fifo = new Queue<string>(names);

    for(int i = 0; i < n - 1; i++)
    {
        var name = fifo.Dequeue();
        fifo.Enqueue(name);
        fifo.Enqueue(name);
    }
    return fifo.Peek();
}

并且是这样调用的：

// Test 1
string[] names = { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
long n = 1; 
var nth = CodeKata.WhoIsNext(names, n); // n = 1 Should return sheldon.

// test 2
string[] names = { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
long n = 52; 
var nth = CodeKata.WhoIsNext(names, n); // n = 52 Should return Penny.

// test 3
string[] names = { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
long n = 7230702951; 
var nth = CodeKata.WhoIsNext(names, n); // n = 52 Should return Leonard.

在这段代码中，当我将 long n 的值设置为 7230702951（一个非常高的数字......）时，它会引发内存不足异常。数字那么高，还是队列没有针对这些数字进行优化。

我这样说是因为我尝试使用 List 并且列表内存使用量保持在 500 MB 以下（顺便说一句，平台大约是 327MB），并且运行了大约 2/3 分钟，而队列在几秒钟内抛出了异常，然后仅在那段时间就超过 2GB。

有人可以向我解释为什么会发生这种情况，我只是好奇吗？

编辑 1

我忘了添加列表代码：

public static string WhoIsNext(string[] names, long n)
{
    List<string> test = new List<string>(names);
    for(int i = 0; i < n - 1; i++)
    {
        var name = test[0];
        test.RemoveAt(0);

        test.Add(name);
        test.Add(name);
    }

    return test[0];
}

编辑 2

对于那些说代码加倍名称并且无能的人，我已经知道，代码不是有用的，只是一个 kata。（我现在更新了链接！）

我的问题是，为什么 Queue 比具有高计数的 List 要低得多。

标签： c#memoryqueue

解决方案

部分原因是队列代码比代码快得多，因为队列是循环缓冲区，因此针对删除进行了优化。列表不是 -每次删除第一个元素时，列表都会复制数组内容。List

将输入值更改72307000为例如。在我的机器上，队列在不到一秒的时间内完成。几分钟后（按这个速度，几小时），这份名单仍在不断增加。在 4 分钟i内现在是 752408 - 它已经完成了几乎 1% 的工作）。

因此，我不确定队列的内存效率较低。它是如此之快，以至于您很快就会遇到内存问题。该列表几乎肯定有相同的问题（数组大小加倍List的Queue方式非常相似） - 可能需要几天时间才能遇到它。

在某种程度上，即使不运行代码，您也可以预测到这一点。包含 7230702951 个条目的队列（运行 64 位）每个条目至少占用8 个字节。所以 57845623608 字节。大于 50GB。显然，您的机器将难以将其放入 RAM 中（加上 .NET 不会让您拥有那么大的数组）......

此外，您的代码有一个微妙的错误。循环永远不会结束（如果n大于int.MaxValue）。您的循环变量是 aint但参数是 a long。您的遗嘱int溢出（从int.MaxValue到）。因此，对于较大的值（意味着队列将永远增长），循环将永远不会退出。您可能应该将类型更改为。int.MinValuei++nilong

c# - 为什么队列消耗这么多内存？

问题描述

解决方案

推荐阅读