IList<T>从对象中删除多个项目的最有效方法是什么。假设我有一个IEnumerable<T>要删除的所有项目，其出现顺序与原始列表中的出现顺序相同。
我想到的唯一方法是：
IList<T> items;
IEnumerable<T> itemsToDelete;
...
foreach (var x in itemsToDelete)
{
items.Remove(x);
}
但我想它效率不高，因为每次Remove调用方法时它都必须从一开始就遍历列表。
问问题
17752 次
3 回答
9
随着要删除的项目数量越来越多，您可能会发现遍历列表并根据“要删除的项目”的哈希集检查每个项目更有效。像这样的扩展方法可能会有所帮助：
static void RemoveAll<T>(this IList<T> iList, IEnumerable<T> itemsToRemove)
{
var set = new HashSet<T>(itemsToRemove);
var list = iList as List<T>;
if (list == null)
{
int i = 0;
while (i < iList.Count)
{
if (set.Contains(iList[i])) iList.RemoveAt(i);
else i++;
}
}
else
{
list.RemoveAll(set.Contains);
}
}
我使用下面的这个小程序进行了基准测试。IList<T>（请注意，如果实际上是 a ，它使用优化的路径List<T>。）
在我的机器上（并使用我的测试数据），这种扩展方法需要1.5 秒才能执行，而您问题中的代码需要17 秒。但是，我没有测试过不同大小的数据。我敢肯定，只删除几个项目RemoveAll2会更快。
static class Program
{
static void RemoveAll<T>(this IList<T> iList, IEnumerable<T> itemsToRemove)
{
var set = new HashSet<T>(itemsToRemove);
var list = iList as List<T>;
if (list == null)
{
int i = 0;
while (i < iList.Count)
{
if (set.Contains(iList[i])) iList.RemoveAt(i);
else i++;
}
}
else
{
list.RemoveAll(set.Contains);
}
}
static void RemoveAll2<T>(this IList<T> list, IEnumerable<T> itemsToRemove)
{
foreach (var item in itemsToRemove)
list.Remove(item);
}
static void Main(string[] args)
{
var list = Enumerable.Range(0, 10000).ToList();
var toRemove = new[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
list.RemoveAll(toRemove); // JIT
//list.RemoveAll2(toRemove); // JIT
var sw = Stopwatch.StartNew();
for (int i = 0; i < 10000; i++)
{
list.RemoveAll(toRemove);
//list.RemoveAll2(toRemove);
}
sw.Stop();
Console.WriteLine("Elapsed: {0} ms", sw.ElapsedMilliseconds);
Console.ReadKey();
}
}
更新（@KarmaEDV 和 Mark Sowul 的评论如下）：如果您需要使用自定义相等比较器，则扩展方法可能具有采用此类比较器的重载：
public static void RemoveAll<T>(this IList<T> iList, IEnumerable<T> itemsToRemove, IEqualityComparer<T> comparer = null)
{
var set = new HashSet<T>(itemsToRemove, comparer ?? EqualityComparer<T>.Default);
if (iList is List<T> list)
{
list.RemoveAll(set.Contains);
}
else
{
int i = iList.Count - 1;
while (i > -1)
{
if (set.Contains(iList[i])) iList.RemoveAt(i);
else i--;
}
}
}
于 2013-08-03T02:17:16.973 回答
7
如果IList<T>引用碰巧引用了 的实例List<T>，则转换为该类型并使用RemoveAll比任何其他不依赖其实现细节的方法都容易产生更好的性能。
否则，虽然最佳方法将取决于要删除的项目的相对比例和 的性质，但IList<T>我建议您最好的选择可能是将 复制IList<T>到新的List<T>，清除它，然后有选择地重新添加项目。即使列表中的项目不利于有效的散列，但事实上，列表中的项目与列表中的项目的IEnumerable<T>顺序相同，这IList<T>将使其无关紧要。首先从IEnumerable<T>. 然后将数组中的项复制到列表中，直到找到该项。然后从 中读取下一项IEnumerable<T>并将数组中的项复制到列表中，直到找到该项，等等。一旦IEnumerable<T>用完，将数组的余额复制到List<T>.
这种方法在许多IList<T>. 但是，它有一个主要缺点：它删除和重新添加每个项目的事实可能会对诸如可观察列表之类的事物产生不必要的副作用。如果一个列表可能是可观察的，则可能必须使用慢得多的 N^2 算法来确保正确性。[顺便说一句，IList<T>有一种Remove(T)方法但缺乏更有用的RemoveAll(Func<T,bool>)方法让我很恼火。与and在Remove(T)很大程度上是多余的，而如果不允许删除和重新添加项目，则允许在不存在 O(N^2) 的情况下执行 O(N) 的许多操作。IndexOfRemoveAtRemoveAll
于 2013-08-02T23:44:57.650 回答
1
也许这有帮助。可以包括其他相同类型的想法。
IList<T> items;
IEnumerable<T> itemsToDelete;
...
{
if(items.Equals(itemsToDelete)) //Equal lists?
{
items.Clear();
return true;
}
if( (double) items.Count/itemsToDelete.Count < 1){
/* It is faster to iterate the small list first. */
foreach (var x in items)
{
if(itemsToDelete.Contains(x)){/**/}
}
}
else{
foreach (var x in itemsToDelete)
{
items.Remove(x);
}
}
}
于 2013-08-02T23:55:18.390 回答