Удаление дубликатов из списка с приоритетом

Дан такой набор записей:

string ID1;
string ID2;
string Data1;
string Data2;
// :
string DataN

Первоначально Data1..N равны нулю, и их можно игнорировать для этого вопроса. ID1 и ID2 однозначно идентифицируют запись. Все записи будут иметь ID2; у некоторых также будет ID1. Учитывая ID2, существует (трудоемкий) метод получения соответствующего ID1. Имея ID1, существует способ (затратный по времени) для получения Data1..N для записи. Наша конечная цель — как можно быстрее заполнить Data1..N для всех записей.

Наша ближайшая цель — (как можно быстрее) устранить все дубликаты в списке, сохранив тот, который содержит больше информации.

Например, если Rec1 == {ID1="ABC", ID2="XYZ"} и Rec2 = {ID1=null, ID2="XYZ"}, то это дубликаты, --- НО мы должны специально удалить Rec2 и сохранить Rec1.

Это последнее требование устраняет стандартные способы удаления дубликатов (например, HashSet), поскольку они считают обе стороны «дубликата» взаимозаменяемыми.


list .net c# algorithm distinct
person James Curran    schedule 05.11.2009    source источник

Ответы (4)


arrow_upward
4
arrow_downward

Как насчет того, чтобы разделить исходный список на 3 — один со всеми данными, один с ID1 и один только с ID2.

Затем выполните:

var unique = allData.Concat(id1Data.Except(allData))
                    .Concat(id2Data.Except(id1Data).Except(allData));

определив равенство как раз на основе ID2.

Я подозреваю, что есть более эффективные способы выразить это, но основная идея, насколько я могу судить, верна. Разделение исходного списка на три — это просто вопрос использования GroupBy (и последующего вызова ToList для каждой группы, чтобы избежать повторных запросов).

РЕДАКТИРОВАТЬ: потенциально более приятная идея: разделить данные, как и раньше, затем сделать:

var result = new HashSet<...>(allData);
result.UnionWith(id1Data);
result.UnionWith(id2Data);

Я полагаю, что UnionWith сохраняет существующие элементы, а не перезаписывает их новыми, но равными. С другой стороны, это не указано явно. Было бы хорошо, если бы это было четко определено...

(Опять же, либо заставьте ваш тип реализовать равенство на основе ID2, либо создайте набор хэшей, используя компаратор равенства, который делает это.)

person Jon Skeet    schedule 05.11.2009

arrow_upward
0
arrow_downward

Это может немного пахнуть, но я думаю, что LINQ-отличный все равно будет работать для вас, если вы убедитесь, что два сравниваемых объекта будут одинаковыми. Это сделает следующий компаратор:

private class Comp : IEqualityComparer<Item>
    {
      public bool Equals(Item x, Item y)
      {
        var equalityOfB = x.ID2 == y.ID2;
        if (x.ID1 == y.ID1 && equalityOfB)
          return true;
        if (x.ID1 == null && equalityOfB)
        {
          x.ID1 = y.ID1;
          return true;
        }
        if (y.ID1 == null && equalityOfB)
        {
          y.ID1 = x.ID1;
          return true;
        }
        return false;
      }

      public int GetHashCode(Item obj)
      {
        return obj.ID2.GetHashCode();
      }
    }

Тогда вы могли бы использовать его в списке как таковой...

var l = new[] { 
  new Item { ID1 = "a", ID2 = "b" }, 
  new Item { ID1 = null, ID2 = "b" } };
var l2 = l.Distinct(new Comp()).ToArray();
person flq    schedule 05.11.2009

arrow_upward
0
arrow_downward

У меня была аналогичная проблема пару месяцев назад.

Попробуйте что-то вроде этого...

public static List<T> RemoveDuplicateSections<T>(List<T> sections) where T:INamedObject
        {
            Dictionary<string, int> uniqueStore = new Dictionary<string, int>();
            List<T> finalList = new List<T>();
            int i = 0;
            foreach (T currValue in sections)
            {
                if (!uniqueStore.ContainsKey(currValue.Name))
                {
                    uniqueStore.Add(currValue.Name, 0);
                    finalList.Add(sections[i]);
                }
                i++;
             }
            return finalList;
        }
person sleath    schedule 05.11.2009

arrow_upward
0
arrow_downward 

records.GroupBy(r => r, new RecordByIDsEqualityComparer())
       .Select(g => g.OrderByDescending(r => r, new RecordByFullnessComparer()).First())

или если вы хотите объединить записи, то Aggregate вместо OrderByDescending/First.

person Andrey Shchekin    schedule 05.11.2009