如何快速删除列表中的项目
我正在寻找一种方法来快速从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。
我觉得HashSet ， LinkedList或Dictionary会对你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
