从对象中移除多个项，最有效的方法是什么？假设我有一个包含我想要删除的所有项的IEnumerable<T>，以与原始列表中出现的顺序相同。
我所知道的唯一方法是：
IList<T> items;
IEnumerable<T> itemsToDelete;
...
foreach (var x in itemsToDelete)
{
items.Remove(x);
}
但我猜这不是很有效，因为每次调用Remove方法时都必须重新遍历列表。
从 IList<T> 中删除多个项的最有效方法
13
- Guillermo Gutiérrez
7
2你对代码进行了性能分析吗？你需要多少性能提升？ - I4V
1正如John Skeet所说：给个踩的人，能否评论一下？ - Guillermo Gutiérrez
2计算机通常可以非常快地完成“许多次”操作。您确定这里真的存在性能问题吗？ - Abe Miessler
两者都可能没有被排序，但它们的出现顺序相同。我不能创建一个新的List，因为我不知道IList<T>实例是否实际上是List<T>，而且可能使用它的底层库有IList<T>的自定义实现，而不是List<T>。并且，我没有进行基准测试。这可能不是一个重大的性能问题，但正如某位老师曾经告诉我：“这只是为了我的灵魂”。 - Guillermo Gutiérrez
但正如某位老师曾经对我说过的：“这只是为了我的灵魂而做的。” 是的，还有一位更明智的老师说过：“过早优化是万恶之源”（引自Donald Knuth）。 - ta.speot.is
显示剩余2条评论
4个回答
13
当需要移除的项目数量变大时，您可能会发现遍历列表并将每个项目与“要删除的项目”的哈希集合进行检查更加高效。像这样的扩展方法可能会有所帮助：
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> 实际上是一个 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.RemoveAll(set.Contains);
}
else
{
int i = iList.Count - 1;
while (i > -1)
{
if (set.Contains(iList[i])) iList.RemoveAt(i);
else i--;
}
}
}
- Eren Ersönmez
6
1我建议按相反的顺序遍历列表。如果您从列表中删除第一个项目，则必须移动所有剩余项目。从后往前删除更有效率。 - Mark Sowul
这个解决方案很棒，但如果List覆盖了Contains方法，优化的List-Path就不能可靠地工作。 - KarmaEDV
@ErenErsönmez 我不确定你所说的“不调用Contains”的意思。是的，抱歉，不是覆盖，而是重载。如果您需要自定义比较器，则IEnumerable<T>.Contains(item, customComparer)是一种重载。如果您使用它，您需要稍微调整建议的解决方案。 - KarmaEDV
如果我理解正确的话，是的，如果您需要使用自定义比较器，则需要进行轻微修改。我在答案中发布了这样的变体。 - Eren Ersönmez
小改进：从列表后面运行，这样在删除多个元素时可以节省最多的复制操作。 - Felix K.
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>) 方法。 Remove(T) 在很大程度上与 IndexOf 和 RemoveAt 重复，而 RemoveAll 将允许 O(N) 的实现许多在其缺席时是 O(N^2) 的操作，如果不允许删除和重新添加项的话。]- supercat
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);
}
}
}
- celerno
2
你可能想尝试比较
items.Count < itemsToDelete.Count() 而不是使用 double。这样还可以避免编译器错误。 - ta.speot.is我没有解释：除法是为了得到一个接近百分比的值，你可以把1替换成0.9来得到90%。 - celerno
0
如果
IList<T>接口有一个可用的扩展方法RemoveAll，那么这个问题将更容易解决。因此，这里提供一个：/// <summary>
/// Removes all the elements that match the conditions defined by the
/// specified predicate.
/// </summary>
public static int RemoveAll<T>(this IList<T> list, Func<T, int, bool> predicate)
{
ArgumentNullException.ThrowIfNull(list);
ArgumentNullException.ThrowIfNull(predicate);
int i = 0, j = 0;
try
{
for (; i < list.Count; i++)
{
if (predicate(list[i], i)) continue;
if (j < i) list[j] = list[i];
j++;
}
}
finally
{
if (j < i)
{
for (; i < list.Count; i++, j++)
list[j] = list[i];
while (list.Count > j)
list.RemoveAt(list.Count - 1);
}
}
return i - j;
}
这是一个修改过的自定义List<T>.RemoveAll实现版本，可以在此答案中找到。由于IList<T>接口中缺少RemoveRange方法，因此通过重复删除最后一个元素来清除IList<T>中右侧剩余的插槽。在大多数IList<T>实现中，这应该是一个非常快速的操作。
现在，可以像这样高效地解决从IList<T>中删除多个项的原始问题：
IList<T> items;
IEnumerable<T> itemsToDelete;
//...
HashSet<T> itemsToDeleteSet = new(itemsToDelete);
items.RemoveAll((x, _) => itemsToDeleteSet.Contains(x));
在线演示。
- Theodor Zoulias
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接