logo标签列表

.NET 2.0 - 泛型列表的效率如何？

.netperformancegenericslistmemory
9
我正在创建一个应用程序，它在内存中保存了大量的用户数据，并且主要使用List<T>结构（以及一些需要查找的Dictionary<T,T>）来保存它们。
我想知道...
List有多高效？ 每个List的内存开销是多少？（即除了它们所包含的对象所需的内存空间之外） 每次实例化一个新的List时，我需要付出多少代价？
有更有效的方法吗？
字典只是哈希表，对吧？或者它们是一种不那么高效的数据结构吗？
我想使用数组，但我遇到了从中添加和删除元素的典型问题，因此必须扩展/缩小它们会很痛苦。
有什么想法/建议吗？
编辑：我知道基本的数据结构101，以及为什么链表更适合添加/删除，哈希表更适合随机访问。
我最关心的是.Net的特点。例如，每种结构浪费了多少内存。以及在初始化/终止它们时浪费的时间。
例如，如果实例化/GC一个List需要很长时间，但清除它不需要花费太多时间，也许我应该保留一些等待我的List池，在完成后将它们清除并发送回池中，而不是简单地取消引用它们。
或者，如果哈希表对于访问更快但浪费了很多内存，我可能更喜欢使用列表并遍历它们，以处理小的项计数。
另外，我真的很想专注于内存使用，因为我的应用程序非常耗费内存（类似于memcached）... 有人知道在哪里可以找到这样的信息吗？
你为什么现在重新提起这个话题？距离你最初发布它已经过去两年了。请注意，通过编辑它，你会使它重新出现在首页。除非你想重新引起人们对你的问题的兴趣，否则就保持原样，包括其中的不足之处。 - Lasse V. Karlsen
10个回答
4
也许你应该考虑使用一些内存数据库类型，如果你的数据量很大需要在内存中保存。
你在考虑什么样的内存数据库呢？数据集吗？我的理解是它们非常慢...或者你是在考虑一些类似于MySQL带有内存表的外部进程数据库吗？（或者是memcached？） - Daniel Magliola
首先，如果您要对答案发表评论，请使用“添加评论”功能。 其次，我怀疑他在考虑类似SQLite（http://www.sqlite.org/）的东西。 - chyne
2
  • Lists 是数组的一种形式，因此添加元素时，除非添加到末尾，否则性能会受到很大影响。
  • 否则它们基本上与数组一样快。
2

List使用数组内部实现，而Dictionary使用哈希表。

它们比旧的非泛型类ArrayList和HashTable更快，因为您不必承担将所有内容转换为/自对象（装箱、拆箱和类型检查）的成本，并且由于MS对它们进行了更好的优化操作。

2
如果您需要在列表中随机插入或删除元素，可以使用链表数据结构 - MSDN文章提供了详细信息。显然，由于链表是一个链接的结构，因此随机访问并不高效。
我总是在列表末尾添加内容。 很多时候，我会从一些最大的列表中间删除内容。除了插入/删除时间之外，链表与常规列表相比如何？（内存，遍历时间等） - Daniel Magliola
2
LinkedList对象由于链表的特性，在添加和删除元素时需要更少的时间。当你添加一个元素时，它不像普通列表那样需要重新调整数组大小。除此之外，我认为LinkedList与普通List的性能表现大致相同。
在维基百科上查看详细信息：链表与数组的比较。
但是.NET的LinkedList会不会将我的每个对象都包装在一个新对象中呢？ 这样会浪费很多内存吗？我真的很担心这个应用程序的内存需求，我希望尽量保持它的低消耗。 - Daniel Magliola
@Daniel：由于它们是链表，所以在随机插入和删除方面效率很高，但在随机访问方面要么缺乏要么效率低（我没有玩过，所以不知道哪个）。如果您需要随机访问，那么我认为List<T>或Dictionary<T, T>将很好，具体取决于您是要按索引还是值访问成员。 - ljs
它确实将对象包装在LinkedListNode对象中，但该对象由4个属性组成，但其中3个仅是对占用非常小的其他对象的引用，第4个是您的实际对象。您始终可以编写自己的链表来减少.NET类型添加的任何开销。我最初建议使用结构体，但在C#中也可能适用。 - Jesse Dearing
2
如果你真的想要了解List<>和Dictionary<,>是如何实现的，可以使用非常有用的.NET Reflector。

同时，可以查看优秀的C5泛型集合库的文档，该库对一些BCL缺失的集合类型有非常好的实现。

1

如果您关心内存使用情况，真正的关键是将数组存储在磁盘上，并在需要时将其部分映射到内存中。

关键是使用FILE_FLAG_NO_BUFFERING，并始终读取/写入恰好一个扇区的数据。

很不幸，我认为我需要把所有东西都放在内存中...至少大部分... 但是你的回答给了我很多有趣的想法。也许我可以把一些我不经常使用的东西保存在磁盘上。有没有关于让Windows自动将其页面到硬盘上的想法？ 例如，我能否将我不经常使用的数据保存在一个单独的进程中，并以某种方式使该其他进程的“内存优先级”低于主要进程？ 这样，当系统内存不足时，它可以首先将那些优先级较低的东西换页出去，保持我的最重要的东西在RAM中？我是在做白日梦吗？ - Daniel Magliola
通过较少地使用不经常使用的数据，可以增加其被分页的可能性。 - Jon Hanna
1

我认为双进程可能有些过度设计，而且进程间通信可能会有一些缓慢（虽然我从未尝试过这样的事情，所以请把我的意见当作一种参考）。我正在开发一个数据驱动的应用程序，每个数据单元都很小，但我们可能在任何时候拥有数十亿个数据单元。我们使用的方法基本上是：

  • 无论什么情况下，所有内容都存储在磁盘上
  • 数据被分块；每个块都知道它上次被访问的时间
  • 当需要时，块从磁盘中拉取到内存中
  • 一个低优先级线程监视内存使用情况并删除最近最少使用的东西

换句话说，这是一个自制的缓存方案。好处是你可以精确地控制哪些数据在内存中，如果你依赖于操作系统的分页方案，你就无法做到这一点。如果一些常用变量与你的数据混合在一页上，那么该页将被反复访问并阻止其进入磁盘。如果你在应用程序中设计了一种适应某些数据请求比其他请求需要更长时间的方式，那么这将非常有效。特别是如果你事先知道哪些块是需要的（我们不知道）。

请记住，.NET应用程序中的所有内容都必须适合2 GB的内存，由于GC的工作方式和您的应用程序的开销，您实际上可能比这少一些。

要监视堆看起来像什么以及谁在分配，请使用CLR分析器：http://www.microsoft.com/downloads/details.aspx?familyid=86ce6052-d7f4-4aeb-9b7a-94635beebdda&displaylang=en

.Net进程在Windows x64中也受到2Gb的限制吗？嗯...哦...我本来指望相反的情况 :-S - Daniel Magliola
我认为x64将允许您寻址4 GB，这一点我没有考虑到。但是，我不会指望在达到那个限制之前完全避免OutOfMemory，因为GC无法将您的对象完美地“打包”到那个空间中（堆碎片化）。 - Nick
回答我的问题：不，它们不是。 - Daniel Magliola
0
除非出现性能问题并且分析器显示了问题所在，否则我不会动手。然后你就会有一个明确的问题需要解决，这样会更容易。
0

.Net中的List并不使用链表，而是使用数组。默认情况下它有4个位置，随着添加的元素增多，其大小会翻倍。因此，List的性能会根据你的使用方式而有所不同。

如果你正在使用VS 2008，请在深入研究之前运行性能分析器。当我们开始实际查看时间损失的位置时，很快就意识到争论链表的细微差别并不重要。
关于性能分析器的想法不错。 我能否在服务器上运行它来对实时进程进行分析，而无需安装整个VS 2008？也许我可以放一个小程序在那里，给我一个日志？是否有类似于性能分析器的工具，可以让我查看我的内存使用情况？（例如，每个类的实例数量或每个类实例中的字节数） - Daniel Magliola
关于工具：请参见https://dev59.com/xXVC5IYBdhLWcg3w9GLM。我个人使用WinDbg + SOS取得了成功。 - Constantin
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接