0

关于如何从另一个列表中排除一个列表的项目，我有一个相当具体的问题。诸如 except() 之类的常见方法不会这样做，原因如下：

  • 如果列表中的重复项具有“偶数”索引 - 我需要删除 THIS 元素和它之后的 NEXT 元素。
  • 如果列表中的重复项有一个“奇数”索引 - 我需要删除这个元素和一个元素之前**它。
  • 一个列表中可能会出现多次相同的重复项。即一个可能带有“奇数”索引，另一个可能是“偶数”。

我不是在寻求解决方案，因为我自己创建了一个。然而，在多次执行此方法后 - “ANTS 性能分析器”显示该方法经过了整个执行时间的 75%（40 秒中的 30 秒）。问题是：是否有更快的方法来执行相同的操作？我试图优化我当前的代码，但它仍然缺乏性能。这里是：

private void removedoubles(List<int> exclude, List<int> listcopy)
{
    for (int j = 0; j < exclude.Count(); j++)
    {
        for (int i = 0; i < listcopy.Count(); i++)
        {
            if (listcopy[i] == exclude[j])
            {
                if (i % 2 == 0) // even
                {
                    //listcopy.RemoveRange(i, i + 1);
                    listcopy.RemoveAt(i);
                    listcopy.RemoveAt(i);
                    i = i - 1;
                }
                else //odd
                {
                    //listcopy.RemoveRange(i - 1, i);
                    listcopy.RemoveAt(i - 1);
                    listcopy.RemoveAt(i - 1);
                    i = i - 2;
                }
            }
        }
    }
}

在哪里：

  • exclude - 仅包含重复项的列表。此列表最多可能包含 30 个元素。
  • listcopy - 应检查重复的列表。如果发现“排除”中的重复项 -> 执行删除操作。此列表最多可能包含 2000 个元素。

我认为 LINQ 可能会有所帮助，但我不太了解它的语法。

4

4 回答 4

5

更快的方法 ( O(n)) 是执行以下操作：

  1. 遍历exclude列表并将其变为HashSet( O(n))
  2. 在检查中，检查被测试的元素是否在集合中（再次O(n)），因为测试是否存在于 aHashSet中O(1)。

也许你甚至可以改变你的算法，让exclude集合HashSet从一开始就是一个，这样你就可以省略第 1 步并获得更快的速度。

（你目前的方式是O(n^2)。）

编辑：
另一个想法如下：您可能正在创建某个列表的副本并让此方法修改它？（根据参数名称猜测。）然后，您可以将其更改为：将原始数组传递给方法，并让方法分配新数组并返回它（您的方法签名应该比类似的东西private List<int> getWithoutDoubles(HashSet<int> exclude, List<int> original)）。

编辑：
如果您按以下方式重新组织输入数据可能会更快：由于项目总是成对删除（偶数索引+以下奇数索引），您应该提前将它们配对！这样你的列表 if ints 就变成了成对的 int 列表。这样你的方法可能是这样的：

private List<Tuple<int, int>> getWithoutDoubles(
              HashSet<int> exclude, List<Tuple<int, int>> original)
{
    return original.Where(xy => (!exclude.Contains(xy.Item1) &&
                                 !exclude.Contains(xy.Item2)))
           .ToList();
}

（您删除第一个或第二个项目在排除集合中的对）。而不是Tuple，也许您可​​以将项目打包到您的自定义类型中。

于 2012-05-10T09:02:17.340 回答
3

这是获得结果的另一种方法。

var a = new List<int> {1, 2, 3, 4, 5};

var b = new List<int> {1, 2, 3};

var c = (from i in a let found = b.Any(j => j == i) where !found select i).ToList();

c 将包含 4,5

于 2013-04-09T21:37:50.933 回答
2

反转您的循环，使它们从 0 开始.Count - 1并转到 0，因此您不必i在其中一种情况下进行更改，并且Count每个集合仅评估一次。

于 2012-05-10T08:56:37.427 回答
1

您可以将 List 转换为 LinkedList 并尝试一下吗？List.RemoveAt() 比 LinkedList.Remove() 更昂贵。

于 2012-05-10T09:03:23.200 回答