C#列表的速度

Question

C#列表速度快吗？使用列表处理对象有哪些好处和坏处？

大量使用列表会使软件变慢吗？C#中列表的替代品有哪些？

列表中有多少个对象是"太多对象"？

Answer 1

List<T> 使用支持数组来保存项目:

• 索引器访问(即获取/更新)是O(1)
• 从尾部移除是O(1)
• 从其他地方删除需要将现有项目向上移动,因此O(n)有效
• 添加到结尾是O(1),除非它需要调整大小,在这种情况下它是O(n).(这是缓冲区大小的两倍,因此摊销成本为O(1).)
• 添加到其他地方需要将现有项目向下移动,因此O(n)有效
• 找到一个项目是O(n),除非它被排序,在这种情况下二进制搜索给出O(log n)

相当广泛地使用列表通常很好.如果在开始填充列表时知道最终大小,最好使用构造函数来指定容量,以避免调整大小.除此之外:如果你担心,打破探查器......

Answer 2

相比什么？

• 如果你的意思是List<T>,那么它本质上是一个数组的包装器; 如此快速地通过索引进行读/写,相对快速地追加(因为它允许最后的额外空间,必要时大小加倍)并从最后删除,但是执行其他操作更加昂贵(插入/删除除了结束之外) )
• 一个数组再次按索引快速,但是固定大小(没有追加/删除)
• Dictionary<,> 等提供更好的密钥访问

列表本质上不是很慢; 特别是如果你知道你总是需要查看所有数据,或者可以通过索引访问它.但对于大型列表,通过密钥搜索可能更好(也更方便)..NET中有各种字典实现,每种字典都具有不同的成本大小/性能.