gpt4 book ai didi

c# - 如何从列表中快速删除项目

转载 作者:IT王子 更新时间:2023-10-29 03:42:32 25 4
gpt4 key购买 nike

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

这严重影响了我的申请。

我写了几个不同的删除方法并在 List<String> 上测试了它们有 500,000 件元素。测试用例如下所示...


概览

我写了一个方法来生成一个字符串列表,其中只包含每个数字的字符串表示形式(“1”、“2”、“3”……)。然后我尝试 remove列表中的每 5 个项目。以下是用于生成列表的方法:

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;
}

测试 1:RemoveAt()

这是我用来测试 RemoveAt() 的测试方法。

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

测试 2:Remove()

这是我用来测试 Remove() 的测试方法。

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]);
}

测试 3:设置为 null,排序,然后 RemoveRange

在这个测试中,我遍历了一次列表并将要删除的项目设置为 null .然后,我对列表进行排序(因此 null 将位于顶部),并删除顶部设置为 null 的所有项目。注意:这对我的列表进行了重新排序,因此我可能必须按正确的顺序将其放回原处。

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...
}

测试 4:创建一个新列表,并将所有“好”值添加到新列表

在这个测试中,我创建了一个新列表,并将我所有的 keep-items 添加到新列表中。然后,我将所有这些项目放入原始列表中。

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);
}

测试5:设置为null然后FindAll()

在这个测试中,我将所有待删除的项目设置为null , 然后使用 FindAll()查找所有不属于 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);
}

测试 6:设置为 null 然后 RemoveAll()

在这个测试中,我将所有待删除的项目设置为null , 然后使用 RemoveAll()删除所有不属于 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()

注释和评论

  • 前两个测试实际上并没有从列表中删除每第 5 个项目,因为列表在每次删除后都会重新排序。事实上,在 500,000 个项目中,只有 83,334 个被删除(应该是 100,000 个)。我对此没有意见 - 显然 Remove()/RemoveAt() 方法无论如何都不是一个好主意。

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

  • 尽管我使用了 List<String>在此示例中,情况并非总是如此。它可能是 List<Anything>

  • 不将项目放在列表的开头不是一个选项。

  • 其他方法 (3 - 6) 都表现得更好,相对而言,但我有点担心 -- 在 3、5 和 6 中,我被迫设置一个值至 null ,然后根据这个哨兵移除所有的元素。我不喜欢这种方法,因为我可以设想一个场景,其中列表中的一项可能是 null而且它会被无意中删除。

我的问题是:从 List<T> 中快速删除许多项目的最佳方法是什么? ?我尝试过的大多数方法在我看来都很丑陋,而且有潜在危险。是List错误的数据结构?

现在,我倾向于创建一个新列表并将好的项目添加到新列表中,但似乎应该有更好的方法。

最佳答案

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

关于c# - 如何从列表中快速删除项目,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6926554/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com