Как мне найти подмножество элементов в двух наборах данных, которые частично отличаются? - PullRequest
Новая
       11

Как мне найти подмножество элементов в двух наборах данных, которые частично отличаются?

2 голосов
/ 03 марта 2009

Я пытаюсь получить подмножество элементов в dataA, которые находятся в dataB, и имеют различные значения свойства c. Свойства a и b можно использовать в качестве индекса, поэтому я попытался отфильтровать только полезные пары, а затем проверить, имеют ли они другое значение c.

Это выражение linq, которое я придумал, и оно работает, но кажется, что должен быть лучший / более быстрый способ найти это подмножество. 

var itemsInBoth = from item in dataA
                  from item2 in dataB
                  where item.a == item2.a && item.b == item2.b
                      select new
                      {
                          first= item,
                          second = item2
                      };
var haveDifferentC = from item in itemsInBoth 
                     where item.first.c != item.second.c
                     select item.first;

Ответы [ 2 ]

3 голосов
/ 03 марта 2009

Основываясь на ответе Дэвида Б., я в конце концов остановился на слегка измененной версии его метода. Хотя различия незначительны, я подумал, что поделюсь этим, прежде всего, чтобы показать версию для тех (как я), которые предпочитают выразительный синтаксис.

Кроме того, вместо группировки я решил использовать анонимную пару ключ / значение для упрощения структуры. 

var dictA = (from item in dataA
             select new
             {
                 key = CreateIndexValue(item.a, item.b),
                 value = item
             }).ToDictionary(kv => kv.key, kv => kv.value);
var dictB = (from item in dataB
             select new
             {
                 key = CreateIndexValue(item.a, item.b),
                 value = item
             }).ToDictionary(kv => kv.key, kv => kv.value);
var filesInBoth = from item in dictA
                  where dictB.ContainsKey(item.Key)
                  select new
                  {
                      itemA = dictA[item.Key],
                      itemB = dictB[item.Key]
                  };
var differentSize = from item in filesInBoth
                    where item.itemA.c!= item.itemB.c
                    select item.itemA;
2 голосов
/ 03 марта 2009

Быстрее? То, что у вас есть, есть O (n ^ 2). Каждый элемент в первом списке будет полностью повторять элементы во втором списке. Вам нужно удалить лишнюю итерацию в этом соединении. Один из способов сделать это - использовать другую структуру для поиска совпадений за O (1).

Вот некоторый непроверенный (непроверенный) код: 

var dictionaryA = dataA
  .GroupBy(item => new {a = item.a, b = item.b})
  .ToDictionary(g => g.Key, g => g.ToList());

var dictionaryB = dataB
  .GroupBy(item => new {a = item.a, b = item.b})
  .ToDictionary(g => g.Key, g => g.ToList());

var results = dictionaryA
  .Where(g1 => dictionaryB.ContainsKey(g1.Key))
  .Select(g1 => new {g1 = g1, g2 = dictionaryB[g1.Key]})
  .SelectMany(pair =>
    pair.g1.SelectMany(item1 =>
      pair.g2
      .Where(item2 => item2.c != item1.c)
      .Select(item2 => new {item1, item2})
    )
  );

Вот упрощенная версия, если пары a, b уникальны в каждом списке. 

var dictionaryA = dataA
  .ToDictionary(item => new {a = item.a, b = item.b}, item => item);

var dictionaryB = dataB
  .ToDictionary(item => new {a = item.a, b = item.b}, item => item);

var results = dictionaryA
  .Where(e1 => dictionaryB.ContainsKey(e1.Key))
  .Select(e1 => new {i1 = e1.Value, i2 = dictionaryB[e1.Key]})
  .Where(pair => pair.i1.c != pair.i2.c);
...