8

如标题。我知道它可能会在删除项目之前和之后合并 2 个子列表,但是在删除 LAST 元素时该方法的行为如何?换句话说:它是否会以某种方式复制位于删除索引之前的所有元素?我只是对在一个巨大的列表(比如说 5000 个元素)上使用 RemoveRange 的性能感到好奇,只是为了删除 fe 中的最后两个。

如果它制作了一个副本,有没有办法改变一些设置列表大小的内部变量(并将其余分配的元素视为垃圾)?

我只设法找到一个信息,它是一个 O(n) 复杂度算法,但我不确定这种情况下的“n”是一个列表大小,还是要删除的项目数。

任何提示都会很高兴。

4

2 回答 2

18

它将做的是将项目范围结束后的每个项目删除,并将其在列表中按已删除项目的数量向上移动。就性能影响而言,在移动的项目范围结束后,每个项目都会有一个副本。这意味着它在从末端移除时表现最好(它将是 O(1)),而在从头移除时表现最差(O(n))。

例如,考虑以下列表:

指数 - 价值

0 - 一个
1 - 乙
2 - C
3-D
4 - E
5 - F
6 - 克

如果我们调用RemoveRange(2, 2) Then,我们将删除从索引 2 开始的两个项目,因此我们将删除 C 和 D。

这意味着需要将 E 复制到索引 2,然后需要将 F 复制到索引 3,然后将 G 复制到索引 4。在删除最后一项后,每个项都有一次复制操作。

请注意,由于您可以将整个内存块“向上”移动两个,因此在实践中最终会比单独复制每个项目更有效。计算机内存将整个内存块向上移动某个固定数量的字节比将大量内存的小部分移动到不同的任意位置要容易得多。不过,它将具有相同的渐近复杂性。

于 2013-04-17T16:11:28.200 回答
14

List<T>只是一个数组的包装器,_items在下面的代码中调用。数组中的插槽可能比列表中的项目多,因此_size用于跟踪实际有效的插槽数。当你做RemoveRange(index, count)...

_size -= count;
if (index < _size)
    Array.Copy(_items, index + count, _items, index, _size - index);
Array.Clear(_items, _size, count);

...它将超出范围的项目复制到现在空的空间中,并清除旧项目。

如果您要删除接近大列表开头的范围,则成本与列表的大小成正比,因为必须向下移动很多东西。

如果要删除接近大列表末尾的大范围,则复制成本低,但清除成本高,因此成本将与删除范围的大小成正比。

于 2013-04-17T16:13:10.173 回答