9

我正在创建一个在内存中保存大量用户数据负载的应用程序，并且它主要将其全部保存在 List<T> 结构中（以及一些 Dictionary<T,T> 当我需要查找时）。

我想知道...

列表的效率如何？我为每个人获得多少内存开销？（也就是说，除了它们包含的对象之外的内存空间）每次实例化一个新对象时我要支付多少罚款？

有没有更有效的方法？

字典只是哈希表，对吗？还是它们是一种效率较低的数据结构？

我想使用数组，但我有一个典型的问题是总是从它们中添加和删除东西，所以不得不增长/缩小它们会很痛苦。

有什么想法/建议吗？

编辑：我知道我的基本数据结构 101，以及为什么链接列表更适合添加/删除，而哈希表更适合随机访问。

我最关心的是.Net 的特质。例如，每个结构浪费了多少内存。并且浪费时间初始化/杀死它们。

例如，如果实例化/GC 一个 List 需要很多时间，但清除它的时间不多，也许我应该保留一小部分 List 等待我，然后清除它们并将它们发送回池中完成后，而不是简单地取消引用它们。

或者，如果 Hashtables 访问速度更快但浪费大量内存，我可能更喜欢使用 Lists 并遍历它们，用于小项目计数。

而且我真的很想关注内存使用情况，因为我的应用程序非常耗费内存（想想 memcached 之类的）......有谁知道我在哪里可以找到这样的信息？

4

10 回答 10

4

如果你有那么多数据必须保存在内存中，也许你应该考虑使用某种类型的内存数据库，

于 2008-08-28T21:14:49.630 回答
2

列表是下面的数组，因此添加项目的性能损失（除非它位于末尾）将非常昂贵。

否则它们将基本上和数组一样快。

于 2008-08-28T21:08:51.907 回答
2

List 在内部使用数组，Dictionary 使用哈希表。

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

于 2008-08-28T21:14:11.863 回答
2

如果您需要高效地在列表中的随机位置插入或删除，可以使用 LinkedList 数据结构 - MSDN 文章提供了详细信息。显然，作为链表随机访问效率不高。

于 2008-08-28T21:18:20.810 回答
2

由于链表的性质，LinkedList 对象的添加和删除时间会更短。添加元素时，它不必像普通列表那样调整数组的大小。除了这种改进之外，我怀疑 LinkedList 的性能与普通列表大致相同。

在 Wikipedia 上查看：链接列表与数组

于 2008-08-28T21:29:49.017 回答
2

如果您真的想了解 List<> 和 Dictionary<,> 是如何实现的所有细节，请使用非常有用的.NET Reflector。

另请参阅优秀的C5 通用集合库的文档，它很好地实现了 BCL 中缺少的许多集合类型。

于 2008-08-31T02:42:20.267 回答
1

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

关键是使用 FILE_FLAG_NO_BUFFERING 并始终准确地读取/写入一个扇区的数据。

于 2008-08-28T21:39:56.047 回答
1

我认为两个进程的事情可能是矫枉过正的。加上进程间通信可能会有些缓慢（尽管我从未尝试过这样的事情，所以我认为它是一粒盐）。我在一个数据驱动的应用程序上工作，其中每个数据单元都很小，但在任何给定时间我们可能有超过十亿个数据单元。我们使用的方法基本上是：

  • 无论如何，一切都驻留在磁盘上
  • 数据被分成“块”；每个块都知道上次访问的时间
  • 需要时将块从磁盘拖到内存中
  • 低优先级线程监控内存使用情况并删除最近最少使用的东西

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

请记住，.NET 应用程序中的所有内容都必须容纳在 2 GB 内存内，并且由于 GC 的工作方式和应用程序的开销，您实际上可能需要处理的内存要少一些。

要准确监视堆的外观和分配对象，请使用CLR 分析器：http ://www.microsoft.com/downloads/details.aspx?familyid=86ce6052-d7f4-4aeb-9b7a-94635beebdda&displaylang=en

于 2008-08-28T22:18:58.400 回答
0

.Net 列表不使用链表。它是一个数组，默认情况下它从 4 个位置开始，我认为当你添加东西时它的大小会翻倍。因此，性能可能会有所不同，具体取决于您使用它的方式。

如果您使用 VS 2008 运行分析器，然后再深入这个老鼠洞。当我们开始真正研究我们浪费时间的地方时，很快就发现争论链表的细节真的无关紧要。

于 2008-08-28T21:46:07.777 回答
0

在出现一些性能问题并且分析器显示您是这样之前，我不会移动手指。然后，您将有一个明确的问题要解决，并且会容易得多。

于 2009-06-03T05:55:37.680 回答