编辑:本问题底部发布了不同技术的基准测试结果。
我有一个非常大的 List<int>
,里面装满了整数。我想从这个 List<int>
中删除所有出现的“3”。使用哪种技术可以最有效地完成此操作?通常我会使用.Remove(3)
方法,直到它返回false
,但我担心每次调用.Remove(3)
内部都会不必要地遍历整个List<int>
。
编辑:在评论中建议尝试以下代码:
TheList = TheList.Where(x => x != 3).ToList();
但是我需要在不实例化新列表的情况下删除元素。
var TheList = new List<int> { 5, 7, 8, 2, 8, 3, 1, 0, 6, 3, 9, 3, 5, 2, 7, 9, 3, 5, 5, 1, 0, 4, 5, 3, 5, 8, 2, 3 };
//technique 1
//this technique has the shortest amount of code,
//but I fear that every time the Remove() method is called,
//the entire list is internally looped over again starting at index 0
while (TheList.Remove(3)) { }
//technique 2
//this technique is an attempt to keep the keep the list from
//being looped over every time an element is removed
for (var i = 0; i < TheList.Count; i++)
{
if (TheList[i] == 3)
{
TheList.RemoveAt(i);
i--;
}
}
有没有更好的方法?
基准测试
我测试了三种技术来从包含100,000个元素的数组中删除10,138个元素:上面展示的两种和Serg在回答中推荐的一种。以下是结果:
- 'while'循环:179.6808毫秒
- 'for'循环:65.5099毫秒
- 'RemoveAll'谓词:0.5982毫秒
基准测试代码:
var RNG = new Random();
//inclusive min and max random number
Func<int, int, int> RandomInt = delegate (int min, int max) { return RNG.Next(min - 1, max) + 1; };
var TheList = new List<int>();
var ThreeCount = 0;
for (var i = 0; i < 100000; i++)
{
var TheInteger = RandomInt(0, 9);
if (TheInteger == 3) { ThreeCount++; }
TheList.Add(TheInteger);
}
var Technique1List = TheList.ToList();
var Technique2List = TheList.ToList();
var Technique3List = TheList.ToList();
<div style="background-color:aquamarine;color:#000000;">Time to remove @ThreeCount items</div>
//technique 1
var Technique1Stopwatch = Stopwatch.StartNew();
while (Technique1List.Remove(3)) { }
var Technique1Time = Technique1Stopwatch.Elapsed.TotalMilliseconds;
<div style="background-color:#ffffff;color:#000000;">Technique 1: @(Technique1Time)ms ('while' loop)</div>
//technique 2
var Technique2Stopwatch = Stopwatch.StartNew();
for (var i = 0; i < Technique2List.Count; i++)
{
if (Technique2List[i] == 3)
{
Technique2List.RemoveAt(i);
i--;
}
}
var Technique2Time = Technique2Stopwatch.Elapsed.TotalMilliseconds;
<div style="background-color:#ffffff;color:#000000;">Technique 2: @(Technique2Time)ms ('for' loop)</div>
//technique 3
var Technique3Stopwatch = Stopwatch.StartNew();
var RemovedCount = Technique3List.RemoveAll(x => x == 3);
var Technique3Time = Technique3Stopwatch.Elapsed.TotalMilliseconds;
<div style="background-color:#ffffff;color:#000000;">Technique 3: @(Technique3Time)ms ('RemoveAll' predicate)</div>
list = list.Where(x=>x!=3).ToList();
- Shiljo PaulsonList<T>
中删除项目涉及复制列表的其余部分。 - Jon SkeetRemoveAll()
的复杂度是O(N)
,这已经是List<T>
的最低要求了,但您仍然可以通过删除所有不必要的类型检查、使方法非泛型并远离Func<T>
委托向原始类型检查转变来稍微提高性能。 - Fabjan