C# 列表的速度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1433307/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Speed of C# lists
提问by George Silva
Are C# lists fast? What are the good and bad sides of using lists to handle objects?
C# 列表速度快吗？使用列表处理对象的好处和坏处是什么？
Extensive use of lists will make software slower? What are the alternatives to lists in C#?
大量使用列表会使软件变慢吗？C# 中列表的替代方法是什么？
How many objects is "too many objects" for lists?
列表中有多少对象是“对象太多”？
采纳答案by Jon Skeet
List<T>uses a backing array to hold items:
List<T>使用后备数组来保存项目：
- Indexer access (i.e. fetch/update) is O(1)
- Remove from tail is O(1)
- Remove from elsewhere requires existing items to be shifted up, so O(n) effectively
- Add to end is O(1) unless it requires resizing, in which case it's O(n). (This doubles the size of the buffer, so the amortized cost is O(1).)
- Add to elsewhere requires existing items to be shifted down, so O(n) effectively
- Finding an item is O(n) unless it's sorted, in which case a binary search gives O(log n)
- 索引器访问（即获取/更新）是 O(1)
- 从尾部移除是 O(1)
- 从其他地方删除需要将现有项目向上移动，因此 O(n) 有效
- 添加到末尾是 O(1) 除非它需要调整大小，在这种情况下它是 O(n)。（这使缓冲区的大小加倍，因此摊销成本为 O(1)。）
- 添加到其他地方需要将现有项目向下移动，因此 O(n) 有效
- 除非已排序，否则查找项目是 O(n)，在这种情况下，二进制搜索给出 O(log n)
It's generally fine to use lists fairly extensively. If you know the final size when you start populating a list, it's a good idea to use the constructor which lets you specify the capacity, to avoid resizing. Beyond that: if you're concerned, break out the profiler...
通常可以相当广泛地使用列表。如果您在开始填充列表时知道最终大小，最好使用构造函数来指定容量，以避免调整大小。除此之外：如果您担心，请打开分析器...
回答by Marc Gravell
Compared to what?
与什么相比？
- If you mean
List<T>, then that is essentially a wrapper around an array; so fast to read/write by index, relativelyfast to append (since it allows extra space at the end, doubling in size when necessary) and remove from the end, but more expensive to do other operations (insert/delete other than the end) - An array is again fast by index, but fixed size (no append/delete)
Dictionary<,>etc offer better access by key
- 如果您的意思是
List<T>，那么这本质上是一个数组的包装器；通过索引读取/写入速度非常快，追加速度相对较快（因为它在末尾允许额外的空间，必要时将大小加倍）并从末尾删除，但执行其他操作（插入/删除除末尾以外的操作）成本更高) - 数组再次通过索引快速，但固定大小（无追加/删除）
Dictionary<,>等提供更好的按键访问
A list isn't intrinsically slow; especially if you know you always need to look at all the data, or can access it by index. But for large lists it may be better (and more convenient) to search via a key. There are various dictionary implementations in .NET, each with different costs re size / performance.
列表本质上并不慢；特别是如果你知道你总是需要查看所有数据，或者可以通过索引访问它。但是对于大型列表，通过键进行搜索可能会更好（也更方便）。.NET 中有各种字典实现，每个实现的大小/性能都有不同的成本。
