如何快速删除列表中的项目

我正在寻找一种方法来快速从C# List<T>删除项目。 该文档指出, List.Remove()List.RemoveAt()操作都是O(n)

  • List.Remove
  • List.RemoveAt

这严重影响了我的应用程序。

我写了几个不同的删除方法,并在一个List<String>上testing了它们全部500,000个项目。 testing用例如下所示…


概观

我写了一个方法,可以生成一个简单的包含每个数字(“1”,“2”,“3”,…)的string表示的string列表。 然后我试图remove列表remove每一个第五项。 以下是用于生成列表的方法:

 private List<String> GetList(int size) { List<String> myList = new List<String>(); for (int i = 0; i < size; i++) myList.Add(i.ToString()); return myList; } 

testing1:RemoveAt()

这是我用来testingRemoveAt()方法的testing。

 private void RemoveTest1(ref List<String> list) { for (int i = 0; i < list.Count; i++) if (i % 5 == 0) list.RemoveAt(i); } 

testing2:删除()

这是我用来testingRemove()方法的testing。

 private void RemoveTest2(ref List<String> list) { List<int> itemsToRemove = new List<int>(); for (int i = 0; i < list.Count; i++) if (i % 5 == 0) list.Remove(list[i]); } 

testing3:设置为空,sorting,然后RemoveRange

在这个testing中,我一次遍历列表,并将要删除的项目设置为null 。 然后,我对列表进行sorting(所以null将位于顶部),并删除顶部设置为null的所有项目。 注意:这个重新sorting我的列表,所以我可能不得不把它放回正确的顺序。

 private void RemoveTest3(ref List<String> list) { int numToRemove = 0; for (int i = 0; i < list.Count; i++) { if (i % 5 == 0) { list[i] = null; numToRemove++; } } list.Sort(); list.RemoveRange(0, numToRemove); // Now they're out of order... } 

testing4:创build一个新列表,并将所有“好”值添加到新列表中

在这个testing中,我创build了一个新列表,并将所有保留项添加到新列表中。 然后,我将所有这些项目放入原始列表中。

 private void RemoveTest4(ref List<String> list) { List<String> newList = new List<String>(); for (int i = 0; i < list.Count; i++) { if (i % 5 == 0) continue; else newList.Add(list[i]); } list.RemoveRange(0, list.Count); list.AddRange(newList); } 

testing5:设置为null,然后FindAll()

在这个testing中,我将所有要删除的项目设置为null ,然后使用FindAll()function查找所有不为null的项目

 private void RemoveTest5(ref List<String> list) { for (int i = 0; i < list.Count; i++) if (i % 5 == 0) list[i] = null; list = list.FindAll(x => x != null); } 

testing6:设置为null,然后RemoveAll()

在此testing中,我将所有要删除的项目设置为null ,然后使用RemoveAll()function删除所有不为null的项目

 private void RemoveTest6(ref List<String> list) { for (int i = 0; i < list.Count; i++) if (i % 5 == 0) list[i] = null; list.RemoveAll(x => x == null); } 

客户应用程序和输出

 int numItems = 500000; Stopwatch watch = new Stopwatch(); // List 1... watch.Start(); List<String> list1 = GetList(numItems); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); RemoveTest1(ref list1); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine(); // List 2... watch.Start(); List<String> list2 = GetList(numItems); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); RemoveTest2(ref list2); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine(); // List 3... watch.Reset(); watch.Start(); List<String> list3 = GetList(numItems); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); RemoveTest3(ref list3); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine(); // List 4... watch.Reset(); watch.Start(); List<String> list4 = GetList(numItems); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); RemoveTest4(ref list4); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine(); // List 5... watch.Reset(); watch.Start(); List<String> list5 = GetList(numItems); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); RemoveTest5(ref list5); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine(); // List 6... watch.Reset(); watch.Start(); List<String> list6 = GetList(numItems); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); RemoveTest6(ref list6); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine(); 

结果

 00:00:00.1433089 // Create list 00:00:32.8031420 // RemoveAt() 00:00:32.9612512 // Forgot to reset stopwatch :( 00:04:40.3633045 // Remove() 00:00:00.2405003 // Create list 00:00:01.1054731 // Null, Sort(), RemoveRange() 00:00:00.1796988 // Create list 00:00:00.0166984 // Add good values to new list 00:00:00.2115022 // Create list 00:00:00.0194616 // FindAll() 00:00:00.3064646 // Create list 00:00:00.0167236 // RemoveAll() 

注释和评论

  • 前两个testing实际上并没有从列表中移除每个第五项,因为每次移除后都会重新排列列表。 事实上,在五十万件中,只有八万八千三百三十四件(应该是十万件)。 我没关系 – 显然Remove()/ RemoveAt()方法不是一个好主意。

  • 虽然我试图从列表中删除第五项,但实际上不会有这样的模式。 要删除的条目将是随机的。

  • 尽pipe在这个例子中我使用了一个List<String> ,但并不总是如此。 它可能是一个List<Anything>

  • 不要将这些项目放入列表中,这不是一个选项。

  • 其他的方法(3-6)都performance得比较好,但是我有点担心 – 在3,5,6中,我被迫设置了一个null ,然后根据这个哨兵去掉所有的项目。 我不喜欢这种方法,因为我可以设想一个场景,其中列表中的项目之一可能是null ,它会被无意中删除。

我的问题是:什么是从List<T>快速删除多个项目的最佳方法? 我尝试过的大多数方法对我来说都非常难看,而且很危险。 List是错误的数据结构?

现在,我倾向于创造一个新的名单,并把好的项目添加到新的名单,但似乎应该有一个更好的方法。

列表是不是一个有效的数据结构,当涉及到删除。 您最好使用双链表(LinkedList),因为删除只需要在相邻条目中进行引用更新。

如果你很高兴创build一个新的列表,你不需要通过设置项目为null。 例如:

 // This overload of Where provides the index as well as the value. Unless // you need the index, use the simpler overload which just provides the value. List<string> newList = oldList.Where((value, index) => index % 5 != 0) .ToList(); 

但是,您可能需要查看其他数据结构,例如LinkedList<T>HashSet<T> 。 这真的取决于你的数据结构需要哪些function。

我觉得HashSetLinkedListDictionary会对你LinkedList

如果顺序不重要,那么就有一个简单的O(1)List.Remove方法。

 public static class ListExt { // O(1) public static void RemoveBySwap<T>(this List<T> list, int index) { list[index] = list[list.Count - 1]; list.RemoveAt(list.Count - 1); } // O(n) public static void RemoveBySwap<T>(this List<T> list, T item) { int index = list.IndexOf(item); RemoveBySwap(list, index); } // O(n) public static void RemoveBySwap<T>(this List<T> list, Predicate<T> predicate) { int index = list.FindIndex(predicate); RemoveBySwap(list, index); } } 

这个解决scheme对于内存遍历是很友好的,所以即使你需要先find索引,它也会非常快。

笔记:

  • 查找项目的索引必须是O(n),因为列表必须是未sorting的。
  • 链接列表的遍历速度很慢,特别是对于长寿命的大型集合。

您始终可以从列表的末尾删除项目。 在最后一个元素上执行清单清除是O(1),因为它所做的全部是递减计数。 所涉及的下一个元素没有转移。 (这就是清单一般是O(n)的原因)

 for (int i = list.Count - 1; i >= 0; --i) list.RemoveAt(i); 

好吧尝试像这样使用RemoveAll

 static void Main(string[] args) { Stopwatch watch = new Stopwatch(); watch.Start(); List<Int32> test = GetList(500000); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); test.RemoveAll( t=> t % 5 == 0); List<String> test2 = test.ConvertAll(delegate(int i) { return i.ToString(); }); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine((500000 - test.Count).ToString()); Console.ReadLine(); } static private List<Int32> GetList(int size) { List<Int32> test = new List<Int32>(); for (int i = 0; i < 500000; i++) test.Add(i); return test; } 

这只会循环两次,并删除正十万个项目

我的这个代码的输出:

 00:00:00.0099495 00:00:00.1945987 1000000 

更新为尝试一个HashSet

 static void Main(string[] args) { Stopwatch watch = new Stopwatch(); do { // Test with list watch.Reset(); watch.Start(); List<Int32> test = GetList(500000); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); List<String> myList = RemoveTest(test); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine((500000 - test.Count).ToString()); Console.WriteLine(); // Test with HashSet watch.Reset(); watch.Start(); HashSet<String> test2 = GetStringList(500000); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); watch.Reset(); watch.Start(); HashSet<String> myList2 = RemoveTest(test2); watch.Stop(); Console.WriteLine(watch.Elapsed.ToString()); Console.WriteLine((500000 - test.Count).ToString()); Console.WriteLine(); } while (Console.ReadKey().Key != ConsoleKey.Escape); } static private List<Int32> GetList(int size) { List<Int32> test = new List<Int32>(); for (int i = 0; i < 500000; i++) test.Add(i); return test; } static private HashSet<String> GetStringList(int size) { HashSet<String> test = new HashSet<String>(); for (int i = 0; i < 500000; i++) test.Add(i.ToString()); return test; } static private List<String> RemoveTest(List<Int32> list) { list.RemoveAll(t => t % 5 == 0); return list.ConvertAll(delegate(int i) { return i.ToString(); }); } static private HashSet<String> RemoveTest(HashSet<String> list) { list.RemoveWhere(t => Convert.ToInt32(t) % 5 == 0); return list; } 

这给了我:

 00:00:00.0131586 00:00:00.1454723 100000 00:00:00.3459420 00:00:00.2122574 100000 

我发现在处理大型列表时,这通常会更快。 删除和查找字典中的正确项目的速度删除,多于弥补创build字典。 尽pipe如此,原始列表必须具有独特的价值,而且我认为一旦完成,订单就不会被保证。

 List<long> hundredThousandItemsInOrignalList; List<long> fiftyThousandItemsToRemove; // populate lists... Dictionary<long, long> originalItems = hundredThousandItemsInOrignalList.ToDictionary(i => i); foreach (long i in fiftyThousandItemsToRemove) { originalItems.Remove(i); } List<long> newList = originalItems.Select(i => i.Key).ToList(); 

或者你可以这样做:

 List<int> listA; List<int> listB; 

 List<int> resultingList = listA.Except(listB); 

其他答案(和问题本身)提供了使用内置的.NET Framework类来处理这个“slug”(缓慢的bug)的各种方法。

但是,如果您愿意切换到第三方库,则只需更改数据结构即可获得更好的性能,除列表types外,您的代码保持不变。

Loyc核心库包括两种工作方式与List<T>相同的方式,但可以更快地移除项目:

  • DList<T>是一个简单的数据结构,当从随机位置移除项目时,您可以使用List<T>两倍的速度
  • AList<T>是一个复杂的数据结构,当你的列表非常长(但是当列表很短时可能会比较慢)的时候,给你一个比List<T>大的加速。

直到n获得真正的大,列表比LinkedLists更快。 原因是因为所谓的caching未命中使用LinkedList比List更频繁地发生。 内存查找相当昂贵。 由于列表以数组的forms实现,因此CPU可以一次加载一堆数据,因为它知道所需的数据是彼此相邻存储的。 然而,一个链表不会给CPU提示下一步需要哪些数据,这会强制CPU执行更多的内存查找操作。 顺便一提。 术语记忆我的意思是RAM。

有关详细信息,请参阅: https : //jackmott.github.io/programming/2016/08/20/when-bigo-foolsya.html