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 回答