获取集合与其子组之间的不同项

本文关键字：之间 集合 获取 | 更新日期: 2023-09-27 18:07:30

我被下面的问题卡住了

例如，我有一些项目的集合

    List<int> exampleList = new List<int> { 1, 3, 5, 6, 7, 8, 6, 5, 6, 6 };

和作为第一个

子组的其他项目集合
    List<int> customSelection = new List<int> { 1, 5, 6, 6, 8 };

我想要的是获得它们之间的差异，例如，获得包含项目{ 3, 7, 5, 6, 6 }的集合，或者换句话说，某些IEnumerable<int> resultingCollection将使customSelection.Concat(resultingCollection)等同于exampleList(不看项目顺序)。

我不能使用.Except()扩展方法，因为它会从第一个集合中排除所有项目，这些项目存在于第二个集合中，这不是我要找的。我想到的唯一解决方案是做以下

        // count item occurances in first collection
        var countedItemsInFisrt = exampleList.GroupBy(item => item)
            .ToDictionary(group => group.Key, group => group.Count());
        // count item occurances in second collection
        var countedItemsInSecond = customSelection.GroupBy(item => item)
            .ToDictionary(group => group.Key, group => group.Count());
        List<int> resultingCollection = new List<int>();
        int itemsCountDifference;
        int itemsCountInSecond;
        foreach (var kvp in countedItemsInFisrt)
        {
            // when item count in first collection is grater then in second one we add it to resulting collection
            // "count difference" times
            if (!countedItemsInSecond.TryGetValue(kvp.Key, out itemsCountInSecond))
                itemsCountInSecond = 0;
            itemsCountDifference = kvp.Value - itemsCountInSecond;
            for (int i = 0; i < itemsCountDifference; i++)
                resultingCollection.Add(kvp.Key);
        }
        var stringResult = resultingCollection.Select(items => items.ToString());
        Console.WriteLine(stringResult.Aggregate((a, b) => a + "," + b));

这是一大堆用来执行选择的代码。更让我担心的是性能，因为在实际情况下，两个集合都可能有数千个项目。

有更好的方法吗?也许我错过了一些关于LINQ可以帮助我的情况?

编辑:

目前最好的解决方案是Ulugbek Umirov提出的最后一种算法。它保留了原始集合的顺序，当我们有原始集合的1/2的选择时，它比任何其他算法都快2.5倍，当选择更少时，它甚至更快。非常感谢Ulugbek Umirov!我已经把它变成了一个通用的扩展方法，适用于任何泛型集合:

    public static IEnumerable<T> Subtract<T>(this IEnumerable<T> minuend, IEnumerable<T> subtrahend)
    {
        var diffList = new List<T>(minuend.Count() - subtrahend.Count());
        var diffDict = subtrahend.GroupBy(n => n)
                                 .ToDictionary(g => g.Key, g => g.Count());
        minuend.ForeEach(n =>
        {
            int count = 0;
            if (diffDict.TryGetValue(n, out count))
            {
                if (count == 1)
                    diffDict.Remove(n);
                else
                    diffDict[n] = count - 1;
            }
            else
                diffList.Add(n);
        });
        return diffList;
    }

获取集合与其子组之间的不同项

我不会将第二个列表分组。

List<int> exampleList = new List<int> { 1, 3, 5, 6, 7, 8, 6, 5, 6, 6 };
List<int> customSelection = new List<int> { 1, 5, 6, 6, 8 };
var diffDic = exampleList.GroupBy(n => n)
                         .ToDictionary(g => g.Key, g => g.Count());
customSelection.ForEach(n =>
{
    if (diffDic.ContainsKey(n))
        diffDic[n]--;
});
var diffList = diffDic.Where(p => p.Value > 0)
                      .SelectMany(p => Enumerable.Repeat(p.Key, p.Value))
                      .ToList();

下面这段代码也可以提高性能:

customSelection.ForEach(n =>
{
    int count = 0;
    if (diffDic.TryGetValue(n, out count))
    {
        if (count == 1)
            diffDic.Remove(n);
        else
            diffDic[n] = count - 1;
    }
});

如果您想保留项目的原始顺序，您可以使用以下代码:

List<int> exampleList = new List<int> { 1, 3, 5, 6, 7, 8, 6, 5, 6, 6 };
List<int> customSelection = new List<int> { 1, 5, 6, 6, 8 };
var diffList = new List<int>(exampleList.Count);
var customSelectionDic = customSelection.GroupBy(n => n)
                                        .ToDictionary(g => g.Key, g => g.Count());
exampleList.ForEach(n =>
    {
        int count = 0;
        if (customSelectionDic.TryGetValue(n, out count))
        {
            if (count == 1)
                customSelectionDic.Remove(n);
            else
                customSelectionDic[n] = count - 1;
        }
        else
            diffList.Add(n);
    });
// diffList: { 3, 7, 5, 6, 6 }

这不会是最快的，并且会改变原来的列表，但我认为这是最短的方法:

customSelection.ForEach(x => exampleList.Remove(x));

现在exampleList将包含3,7,5,6,6

简单的解决方案就是从第二个列表的副本中逐个删除第一个列表中的项:

var exampleList = new List<int> { 1, 3, 5, 6, 7, 8, 6, 5, 6, 6 };
var customSelection = new List<int> {1, 5, 6, 6, 8};
var result = new List<int>(exampleList);
foreach (var item in customSelection)
{
    result.Remove(item);
}

然而，这不是很性能，因为每次从列表中删除一个项目时都必须进行内部调整，并且您在op中提到了这是一个问题。首先，测试它，如果性能不够好，那么我会使用List.RemoveAll。它接受一个谓词，这意味着它可以包含局部变量:

    public static void Main()
    {
        var exampleList = new List<int> { 1, 3, 5, 6, 7, 8, 6, 5, 6, 6 };
        var customSelection = new List<int> {1, 5, 6, 6, 8};
        var counts = customSelection.GroupBy(x => x)
                     .ToDictionary(i => i.Key, i => i.Count());
        var removedCounts = new Dictionary<int, int>();
        var result = new List<int>(exampleList);
        result.RemoveAll(x => RemovalCheck(counts, removedCounts, x));
    }
    private static bool RemovalCheck(Dictionary<int, int> counts, Dictionary<int, int> removed, int item)
    {
        if (!counts.ContainsKey(item))
            return false;
        if (!removed.ContainsKey(item))
            removed[item] = 0;
        if (removed[item] >= counts[item])
            return false;
        removed[item]++;
        return true;
    }

(您可以在lambda中完成所有这些，而不是定义单独的方法，但我认为没有任何理由这样做)

相关文章：