8

编写将比较 n 个列表并返回所有未出现在所有列表中的所有值的方法的最有效方法是什么？

var lists = new List<List<int>> {
                                  new List<int> { 1, 2, 3, 4 },
                                  new List<int> { 2, 3, 4, 5, 8 },
                                  new List<int> { 2, 3, 4, 5, 9, 9 },
                                  new List<int> { 2, 3, 3, 4, 9, 10 }
                                };


public IEnumerable<T> GetNonShared(this IEnumerable<IEnumerable<T>> lists)
{
  //...fast algorithm here
}

以便

列表.GetNonShared();

返回 1、5、8、9、10

我有

public IEnumerable<T> GetNonShared(this IEnumerable<IEnumerable<T>> lists)
{
  return list.SelectMany(item => item)
             .Except(lists.Aggregate((a, b) => a.Intersect(b));
}

但我不确定这是否有效。顺序无所谓。谢谢！

4

4 回答 4

5 
        public static IEnumerable<T> GetNonShared<T>(this IEnumerable<IEnumerable<T>> list)
        {
           return list.SelectMany(x => x.Distinct()).GroupBy(x => x).Where(g => g.Count() < list.Count()).Select(group => group.Key);
        }
于 2011-09-15T19:25:56.077 回答
2

编辑：我想我会这样想...

您想要所有列表的并集，减去所有列表的交集。这实际上就是您的原始文件所做的，尽管获得重复输入，但仍要Except进行“设置”操作。Union在这种情况下，我怀疑您可以更有效地执行此操作，只需构建两个HashSets 并就地完成所有工作：

public IEnumerable<T> GetNonShared(this IEnumerable<IEnumerable<T>> lists)
{        
    using (var iterator = lists.GetEnumerator())
    {
        if (!iterator.MoveNext())
        {
            return new T[0]; // Empty
        }

        HashSet<T> union = new HashSet<T>(iterator.Current.ToList());
        HashSet<T> intersection = new HashSet<T>(union);
        while (iterator.MoveNext())
        {
            // This avoids iterating over it twice; it may not be necessary,
            // it depends on how you use it.
            List<T> list = iterator.Current.Toist();
            union.UnionWith(list);
            intersection = intersection.IntersectWith(list);
        }
        union.ExceptWith(intersection);
        return union;
    }
}

请注意，这现在是急切的，而不是延迟的。

这是一个替代选项：

public IEnumerable<T> GetNonShared(this IEnumerable<IEnumerable<T>> lists)
{
    return list.SelectMany(list => list)
               .GroupBy(x => x)
               .Where(group => group.Count() < lists.Count)
               .Select(group => group.Key);
}

如果一个列表可能不止一次包含同一个项目，那么您需要在其中进行 Distinct 调用：

public IEnumerable<T> GetNonShared(this IEnumerable<IEnumerable<T>> lists)
{
    return list.SelectMany(list => list.Distinct())
               .GroupBy(x => x)
               .Where(group => group.Count() < list.Count)
               .Select(group => group.Key);
}

编辑：现在我已经纠正了这个，我理解你的原始代码......我怀疑我能找到更好的东西......思考......

于 2011-09-15T19:13:37.547 回答
0

我认为您需要创建一个中间步骤，即查找所有列表共有的所有项目。使用集合逻辑很容易做到这一点 - 它只是第一个列表中的项目集与每个后续列表中的项目集相交。不过，我认为这一步在 LINQ 中是不可行的。

class Program
{
    static void Main(string[] args)
    {
        IEnumerable<IEnumerable<int>> lists = new List<IEnumerable<int>> {
                              new List<int> { 1, 2, 3, 4 },
                              new List<int> { 2, 3, 4, 5, 8 },
                              new List<int> { 2, 3, 4, 5, 9, 9 },
                              new List<int> { 2, 3, 3, 4, 9, 10 }
                            };

        Console.WriteLine(string.Join(", ", GetNonShared(lists)
            .Distinct()
            .OrderBy(x => x)
            .Select(x => x.ToString())
            .ToArray()));
        Console.ReadKey();
    }

    public static HashSet<T> GetShared<T>(IEnumerable<IEnumerable<T>> lists)
    {
        HashSet<T> result = null;
        foreach (IEnumerable<T> list in lists)
        {
            result = (result == null)
                         ? new HashSet<T>(list)
                         : new HashSet<T>(result.Intersect(list));
        }
        return result;
    }

    public static IEnumerable<T> GetNonShared<T>(IEnumerable<IEnumerable<T>> lists)
    {
        HashSet<T> shared = GetShared(lists);
        return lists.SelectMany(x => x).Where(x => !shared.Contains(x));
    }
}
于 2011-09-15T19:50:38.087 回答
0 
public static IEnumerable<T> GetNonShared<T>(this IEnumerable<IEnumerable<T>> list)
{
    var lstCnt=list.Count(); //get the total number if items in the list                                
    return list.SelectMany (l => l.Distinct())
        .GroupBy (l => l)
        .Select (l => new{n=l.Key, c=l.Count()})
        .Where (l => l.c<lstCnt)
        .Select (l => l.n)
        .OrderBy (l => l) //can be commented
        ;
}

//使用 HashSet 和 SymmetricExceptWith 用于 .net >= 4.5

于 2015-06-20T12:50:10.477 回答