Эффективный алгоритм поиска дополнений и удалений из 2 коллекций

Question

Здравствуйте, я хотел бы реализовать эффективный алгоритм для обработки следующего случая:

Предположим, у нас есть 2 списка со следующими элементами:

Источник: [a, b, c,d, e] Новое: [d, e, f, g]

Теперь я должен обновить источник новой информацией.Алгоритм должен быть в состоянии обнаружить, что «f» и «g» являются новыми записями, что «a», «b» и «c» были удалены, а «d» и «e» не были изменены.

Используемые операции - это операции пересечения множества между Источником и Новым, и наоборот.Я ищу эффективный алгоритм для реализации в C # для произвольных несортированных перечислений.

Заранее спасибо,

Answer 1

var added = New.Except(Source);
var removed = Source.Except(New);
var notModified = Source.Intersect(New);

Если вы хотите использовать подход, в котором вы «показываете свою работу», я бы предложил поместить их каждый в HashSets, поскольку это позволяет провести быструю проверку Contains по сравнению с другими перечислениями.

Edit:

Хорошо, если мы идем на общую скорость за счет эффективности выражения, то со следующими допущениями:

1. У нас есть достаточно хеш-тип элемента (если нет, но он может быть абсолютно отсортирован, тогда SortedList может превзойти хеш-набор).
2. Мы не можем предсказать, будет ли Source или New больше (в этом примере есть небольшое преимущество, если я сделаю это наоборот, как у меня, но я предполагаю, что это случайно в данных и что мы должны ожидать каждого с равной вероятностью.

Тогда я бы предложил:

HashSet<T> removed = Source as HashSet<T> ?? new HashSet<T>(Source);
LinkedList<T> added = new LinkedList<T>();
LinkedList<T> notModified = new LinkedList<T>();
foreach(T item in New)
    if(removed.Remove(item))
        notModified.AddLast(item);
    else
        added.AddLast(item);

При настройке removed я проверяю, является ли это уже хэш-набором, чтобы избежать расточительного построения нового (я предполагаю, что ввод вводится как IEnumerable<T>). Конечно, это разрушительное действие, поэтому мы все равно можем его избежать.

Обратите внимание, что я изменяю хэш-набор при перечислении через него. Это разрешено hashset, но вне гарантий, предоставляемых перечислителями, поэтому зависит от реализации. Тем не менее, с нынешними рамками вкл. это более эффективно, чем тестировать и добавлять в другую удаленную коллекцию.

Я выбрал связанные списки для двух других коллекций, так как они, как правило, хорошо подходят с точки зрения стоимости вставки (не только O (1), но и быстрого O (1) по сравнению с использованием другого набора).

Теперь, если вы хотите пойти еще дальше, возможно, для реализации хэш-набора доступны микрооптимизации, если вы выберете свой собственный.

Answer 2

Я не проверял это на производительность, но мое внутреннее чувство заключается в том, что вы должны сначала отсортировать два списка.Затем вы можете пройти по списку ключей каждый удаленный, добавленный или неизмененный элемент по мере продвижения.

1- Sort the Old and New list
2- Set up a pointer for each list lets call them p1 and p2
3- Step the pointers using the following algorithm
  a) If Old[p1] = New[p2] the items are unchanged, increment p1 and p2
  b) If Old[p1] < New[p2] then Old[p1] has been removed, increment p1
  c) If Old[p1] > new[p2] then New[p2] is a new element, increment p2
  d) If p1 > Old.ItemCount then break out of loop, rest of New contains new items
  e) If p2 > New.ItemCount then break out of loop, rest of Old items have been removed
  f) If p1 < Old.ItemCount and p2 < Old.ItemCount Goto step **a**

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

Вот быстрое и грязное демо, я включил сортировку для демонстрационных целей, конечно, в этом случае данные уже отсортированы.

static void Main(string[] args)
{
  string[] oldList = { "a", "b", "c", "d", "e" };
  string[] newList = { "d", "e", "f", "g" };      

  Array.Sort(oldList);
  Array.Sort(newList);

  int p1 = 0;
  int p2 = 0;

  while (p1 < oldList.Length && p2 < newList.Length)
  {
    if (string.Compare(oldList[p1], newList[p2]) == 0)
    {
      Console.WriteLine("Unchanged:\t{0}", oldList[p1]);
      p1++;
      p2++;
    }
    else if (string.Compare(oldList[p1], newList[p2]) < 0)
    {
      Console.WriteLine("Removed:\t{0}", oldList[p1]);
      p1++;
    }
    else if (string.Compare(oldList[p1], newList[p2]) > 0)
    {
      Console.WriteLine("Added:\t\t{0}", newList[p2]);
      p2++;
    }        
  }

  while (p1 < oldList.Length)
  {
    Console.WriteLine("Removed:\t{0}", oldList[p1]);
    p1++;
  }

  while (p2 < newList.Length)
  {
    Console.WriteLine("Added :\t\t{0}", newList[p2]);
    p2++;
  }

  Console.ReadKey();
}

Выход из вышеперечисленного

Removed:        a
Removed:        b
Removed:        c
Unchanged:      d
Unchanged:      e
Added :         f
Added :         g

Answer 3

Назовите наборы X и Y. Если набор X поддерживает быстрый поиск, и у вас есть удобные средства «пометить» и «пометить» элементы в нем, вы можете начать с тегирования всех элементов в X, а затем запросить Xдля каждого элемента в Y. Если элемент не найден, элемент является «новым» в Y. Если элемент найден, он является общим для обоих наборов, и вы должны разметить его в X. Повторите для всех элементов в Y. Когдавсе готово, любые элементы в X, которые все еще помечены, были "удалены" из Y.

Этот подход требует только одного из наборов для поддержки удобных запросов и тегов.Требуется запросить один набор для всех записей в другой, а затем извлечь из него все элементы, которые не генерировали хиты.Нет необходимости сортировать любой набор.

Answer 4

Вы можете использовать операции набора , доступные в Linq.

string[] list1 = { "a","b","c","d","e"};
string[] list2 = { "d", "e", "f", "g" };

string[] newElements = list2.Except(list1).ToArray();
string[] commonElements = list2.Intersect(list1).ToArray();
string[] removedElements = list1.Except(list2).ToArray(); 

Примечание. Приведенный выше код предполагает, что каждый из списков отличается, т.е.не содержать один и тот же элемент более одного раза.Например, для списков [a, b, c, c] и [a, b, c] код не обнаружит удаленный элемент.

Answer 5

Я думаю, что вы ищете операции над множествами, т.е. объединение и т. Д. Посмотрите на эту статью: http://srtsolutions.com/public/item/251070