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
}

となることによって

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

編集：私はそれをこのように考えると思います...

すべてのリストの共通部分を除いて、すべてのリストの和集合が必要です。これは事実上、オリジナルが行うことであり、重複した入力を取得しているにもかかわらず、の「集合」操作を実行するために残されています。この場合、2つを構築し、すべての作業をインプレースで実行するだけで、これをより効率的に実行できると思います。ExceptUnionHashSet

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とSymmetricExceptWithfor .net>=4.5を使用します

于 2015-06-20T12:50:10.477 に答える