.Net Dictionary 超出6,000,000个条目的内存不足exception

我使用Dictionary来存储图像中颜色的频率,其中键是颜色(作为int),值是在图像中找到颜色的次数。

当我处理更大/更彩色的图像时,这个字典会变得非常大。 我在大约6,000,000个条目中得到了一个内存不足的例外。 这是在32位模式下运行时的预期容量吗? 如果是这样,我能做些什么吗? 什么可能是一些跟踪这些不会耗尽内存的数据的替代方法?

作为参考,这里的代码循环遍历位图中的像素并将频率保存在Dictionary

 Bitmap b; // = something... Dictionary count = new Dictionary(); System.Drawing.Color color; for (int i = 0; i < b.Width; i++) { for (int j = 0; j < b.Height; j++) { color = b.GetPixel(i, j); int colorString = color.ToArgb(); if (!count.Keys.Contains(color.ToArgb())) { count.Add(colorString, 0); } count[colorString] = count[colorString] + 1; } } 

编辑:如果您想知道哪个图像中有许多不同的颜色: http : //allrgb.com/images/mandelbrot.png

编辑:我还应该提一下,这是在使用.Net 4.0的asp.net Web应用程序中运行的。 因此可能存在额外的内存限制。

编辑:我只是在控制台应用程序中运行相同的代码,没有任何问题。 问题只发生在ASP.Net中。

更新:鉴于OP的示例图像,似乎最大项目数将超过1600万, 显然甚至在实例化字典时分配太多。 我在这里看到三个选项:

  • 将图像大小调整为可管理的大小并从中进行操作。
  • 尝试转换为颜色可能性较少的配色方案。
  • 像其他人建议的那样去寻找固定大小的数组。

上一个答案:问题是您没有为字典分配足够的空间。 在某些时候,当它正在扩展时,你只是为扩展而耗尽内存,但不一定是新词典。

示例:此代码在内存中耗尽近2400万个条目(在我的机器中,以32位模式运行):

 Dictionary count = new Dictionary(); for (int i = 0; ; i++) count.Add(i, i); 

因为在最后一次扩展时,它目前正在为已经存在的条目使用空间,并试图为另外一个分配空间,这太多了。

现在,如果我们最初为4千万个条目分配空间,它运行没有问题:

 Dictionary count = new Dictionary(40000000); 

因此,请尝试指示创建字典时将有多少条目。

来自MSDN :

Dictionary的容量是在resize之前可以添加到Dictionary的元素数量。 当元素添加到Dictionary时,通过重新分配内部数组,容量会根据需要自动增加。 如果可以估计集合的大小,则指定初始容量消除了在向Dictionary添加元素时执行大量resize操作的需要

每个字典条目包含两个4字节整数:总共8个字节。 8字节* 6百万条目只有大约48MB,+ / – 一些空间用于对象开销,对齐等。内存中有足够的空间用于此。 .Net提供每个进程最多2 GB的虚拟地址空间。 48MB左右不应该导致问题。

我希望这里实际发生的事情与字典自动扩展以及垃圾收集器如何处理(或处理) 压缩有关

首先,自动扩展部分。 上次我检查(回到.Net 2.0 * ),.Net中的集合倾向于在内部使用数组。 他们会在集合构造函数中分配一个合理大小的数组(比如10个项目),然后在数组填满时使用双倍算法创建额外的空间。 必须将所有现有项目复制到新arrays,但旧arrays可能会被垃圾收集。 垃圾收集器对此非常可靠,因此这意味着您在集合中最多使用2n – 1项空间。

现在垃圾收集器压缩部分。 在一定大小之后,这些数组最终会出现在一个名为Large Object Heap的内存区域中。 垃圾收集仍然在这里工作(虽然不常见)。 在这里没有真正起作用的是压缩 (想想内存碎片整理)。 旧对象使用的物理内存被释放,返回到操作系统,并可用于其他进程。 但是,进程中的虚拟地址空间…将程序存储器偏移量映射到物理内存地址的表仍将保留(空)空间。

这很重要,因为记住:我们正在处理一个快速增长的对象。 这样的对象可能占用远大于对象本身最终大小的地址空间。 一个对象变得足够快,足够快,突然你得到一个OutOfMemoryException,即使你的应用程序并没有真正使用那么多RAM。

这里的第一个解决方案是在初始集合中为所有数据分配足够的空间。 这允许您跳过所有这些重新分配和复制。 您的数据将存储在一个arrays中,并仅使用您实际要求的空间。 大多数集合(包括Dictionary)都具有构造函数的重载,允许您为其提供希望第一个数组使用的项目数。 这里要小心:您不需要为图像中的每个像素分配项目。 会有很多重复的颜色。 您只需要为图像中的每种颜色分配足够的空间。 如果它只是给您带来问题的大图像,并且您几乎可以处理六百万条记录,那么您可能会发现800万条记录足够多。

我的下一个建议是对像素颜色进行分组 。 人类无法分辨并且不关心任何rgb组件中两种颜色是否相隔一位。 您可能会查看每个像素的单独RGB值并对像素进行标准化 ,以便您只关心R,G或B值的大于等于5的变化。 这将使您从1650万种潜在颜色一直下降到仅约132,000种,并且数据也可能更有用。 这可能看起来像这样:

 var colorCounts = new Dictionary(132651); foreach(Color c in GetImagePixels().Select( c=> Color.FromArgb( (cR/5) * 5, (cG/5) * 5, (cB/5) * 5) ) { colorCounts[c] += 1; } 

* IIRC,在最近或即将发布的.Net版本的某个地方正在解决这两个问题。 一个是允许你强制压缩LOH,另一个是通过使用一组数组用于集合后备存储,而不是试图将所有内容保存在一个大数组中

CLR提供的最大大小限制为2GB

在64位Windows操作系统上运行64位托管应用程序时,可以创建不超过2千兆字节(GB)的对象。

你最好使用一个数组。

您也可以检查此BigArray ,获得2GB数组大小限制

在32位运行时中, Dictionary可以包含的最大项目数为6170万。 有关详细信息,请参阅我的旧文章 。

如果您在32位模式下运行,那么您的整个应用程序以及任何需要的ASP.NET和底层机制都必须适合您的进程可用的内存:通常在32位运行时为2 GB。

顺便说一句,一个非常古怪的方法来解决你的问题(但我不建议,除非你真的伤害了内存),将是以下(假设一个24位图像):

  1. 调用LockBits以获取指向原始图像数据的指针
  2. 通过移动每条扫描线的数据来压缩每扫描线填充,以填充前一行的填充。 最终得到一个3字节值的数组,后跟一堆空的空格(等于填充)。
  3. 对图像数据进行排序。 也就是说,对3字节值进行排序。 你必须写一个自定义排序,但它不会糟糕。
  4. 顺序遍历数组并计算唯一值的数量。
  5. 分配一个二维数组: int[count,2]来保存值及其出现次数。
  6. 再次按顺序遍历数组以计算每个唯一值的出现次数并填充计数数组。

我不诚实地建议使用这种方法。 我想起来的时候笑了一下。

尝试使用数组。 我怀疑它会耗尽内存。 600万个int数组元素并不是什么大问题。