List.Insert 导致的 CPU 爆高

我们经常会利用 List 作为数据存储容器。但在某些特别场景下，List.Insert 方法可能会引发严重的性能问题，例如 CPU 占用率飙升。
示例步伐

以下是一个简单的控制台步伐，模拟在 List 的开头不停插入数据：

1. internal class Program
2. {
3.     static void Main(string[] args)
4. {
5.     List<string> numbers = new List<string>();
6.     string orderNumber = "order12345678912456";
7.     Console.WriteLine($"从数据库读取到数据，逐条放入list");
8.     Stopwatch sw = Stopwatch.StartNew();
9.     for (int i = 0; i < 100000; i++)
10.     {
11.         numbers.Insert(0, orderNumber); // 每次插入到列表开头
12.         //numbers.Add(orderNumber);
13.         if (i % 1000 == 0)
14.         {
15.             Console.WriteLine($"已插入 {i} 次");
16.         }
17.     }
18.     //numbers.Reverse();
19.     sw.Stop();
20.     Console.WriteLine($"插入完成，耗时：{sw.ElapsedMilliseconds} ms，按任意键退出...");
21.     Console.ReadLine();
22. }
23. }

复制代码

运行上述代码后，当插入数据量逐渐增大时，CPU 的占用率会显著提升，执行完以后CPU恢复正常。原因安在？我们从源码和数据结构的角度进行分析。
List.Insert 的底层实现

以下是 List.Insert 方法的核心实现（通过ILSpy检察）：

1. public void Insert(int index, T item)
2. {
3.     if ((uint)index > (uint)_size)
4.     {
5.         ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
6.     }
7.     if (_size == _items.Length)
8.     {
9.         Grow(_size + 1);
10.     }
11.     if (index < _size)
12.     {
13.         Array.Copy(_items, index, _items, index + 1, _size - index);
14.     }
15.     _items[index] = item;
16.     _size++;
17.     _version++;
18. }

复制代码

关键点：
1.Array.Copy：当插入位置在列表中间或开头时，需要将插入点之后的全部元素向后移动一位，以腾出空间存放新元素。
2.时间复杂度：
•单次插入操作的时间复杂度为 (O(n))，其中 (n) 是列表的当前长度。
•当在循环中多次调用 Insert，团体复杂度会累积。
插入过程的图解

以下用一张图示意 numbers.Insert(0, i) 的操作过程：
1.初始状态：
[1, 2, 3, 4, 5] (原始数组)`` ^ Insert(0, 10)
2.插入后：
[10, 1, 2, 3, 4, 5] (新状态)
起首会进行扩容检查，假如_size已到达_items.Length，会调用EnsureCapacity扩容。在插入过程中，  Array.Copy 从索引 0 开始，将每个元素向右移动一位，终极完成插入。
复杂度分析

对于长度为 (n) 的 List，在头部插入元素的时间复杂度为 (O(n))。在一个循环中执行 (m) 次插入操作，累积复杂度为：
[ O(1) + O(2) + O(3) + \ldots + O(m) = O\left(\frac{m^2}{2}\right) ]
示例盘算

假设 List 的长度为 100,000，每次在头部插入数据：
•第 1 次插入移动 0 个元素•第 2 次插入移动 1 个元素•第 3 次插入移动 2 个元素•...•第 100,000 次插入移动 99,999 个元素
总移动次数为：
[ T = 0 + 1 + 2 + \ldots + (100,000 - 1) = \frac{(100,000) \times (100,000 - 1)}{2} = 4,999,950,000 ]
移动了 49.9 亿次元素，这就是导致 CPU 爆高的根本原因。
解决方案

需要注意的是，LinkedList 的遍历效率不如 List，因此适用场景有限。
1. 利用 List.Add + Reverse 优化

可以先用 List.Add 插入，再调用 Reverse 方法。List.Add 方法，复杂度为 (O(1))。

1. var numbers = new List<int>();
2. for (int i = 0; i < 100000; i++)
3. {
4.     numbers.Add(orderNumber);
5. }
6. numbers.Reverse();

复制代码

2. 利用 LinkedList

对于频仍在头部插入的场景，可以选择 LinkedList，插入操作复杂度为 (O(1))。

1. var linkedNumbers = new LinkedList<int>();
2. for (int i = 0; i < 100000; i++)
3. {
4.     linkedNumbers.AddFirst(i);
5. }

复制代码

总结

List 存放的数据可能有肯定量时候，要考虑的List.Insert性能问题。了解常见集合范例及其操作背后的数据结构原理，选择合适的数据结构。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。