背景
X上闲逛发现这样一个post
简单翻译一下,就是说如果针对无序数组(顺序不重要),要删除其中某个元素,比起费劲的移动很多元素,可以把要删除的元素和最后一个元素交换,然后减小数组的长度即可。
然后我看有回复说,他给dotnet提了PR有这样的一个优化
github PR地址:https://github.com/dotnet/runtime/pull/106581/commits/28f434c3f3415181901a803985d05b19b0d18107
方便观看,我直接截图贴在这里:
分析
上图我们可以看到这个优化就是文章开头提到的方法,将list.RemoveAt(targetIndex)
优化,
先与最后一个元素交换list[targetIndex] = list[^1]
然后list.RemoveAt(lastIndex)
那么二者到底有何差异?
那就得看RemoveAt的源码了
RemoveAt源码
此处方便查看,我直接贴出来:
public void RemoveAt(int index) {
if ((uint)index >= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}
Contract.EndContractBlock();
_size--;
if (index < _size) {
Array.Copy(_items, index + 1, _items, index, _size - index);
}
_items[_size] = default(T);
_version++;
}
看源码,流程是这样的
因为是移除某个index元素,list的size必然会少一个,所以首先size--
正常我们指定某个index,那么将会进行Array.Copy
操作,我们可以看到这个方法有5个参数,参数意义见:
public static void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
{
}
我们可以看到sourceArray 和 destinationArray其实都是当前数组_items
Copy之后,最后一个元素必然空着了,所以会把最后一个元素置为泛型目标的默认值 _items[_size] = default(T);
示意如下,现在小学生都能理解
代码如此,回到刚才的问题,list.RemoveAt(lastIndex)
的时候,由于size--
,所以不会进入if代码块,所以也不会发生Array.Copy
操作。