Сравнение двух IEnumerable для обнаружения изменений - PullRequest
Новая
       14

Сравнение двух IEnumerable для обнаружения изменений

5 голосов
/ 23 марта 2012

Для моего первого поста у меня есть вопрос относительно сравнения IEnumerable.У меня есть привязываемая структура, основанная на логике перечисления.Содержимое IEnumerable со временем меняется, и мне приходится вручную запускать события CollectionChanged.

У меня очень наивный алгоритм, который позволяет мне обнаруживать простые изменения между двумя состояниями IEnumerable (простое добавление, простое удаление, множественное добавление, множественное удаление), но он не очень эффективен и не обнаруживает все.

Быстрый пример того, что мне нужно:

Состояние 1 IEnumerable: A * B * C * D * E

State2 из IEnumerable: A * C * B * D * D1

Для этого примера мне потребуется обнаружить

  • Одна операция перемещения: B изменил индекс с 1на 2
  • Одна операция добавления: D1 был вставлен с индексом 4
  • Одна операция удаления: E была удалена

Существует ли алгоритм для эффективного решения этой проблемынасколько это возможно (O (nLog (n)) будет хорошим началом)?

Спасибо!

Ответы [ 2 ]

1 голос
/ 23 марта 2012

Это некомпилированный, непроверенный и, по крайней мере, частично псевдо-код.

При достаточном обнаружении одного движения Предметы могут двигаться только вперед, перемещение назад будет результатом перемещения или удаления другого элемента

например, Состояние 1 IEnumerable: A * B * C * D * E

Состояние 2 IEnumerable: A * D * B * C * D1

Результат как в B, так и вC движется вперед. 

enum1pos = -1;
enum2pos = 0;
  Value2 = enum2.Next()
  enum2pos++;
List<int> SkipList = new SkipList();
while(enum1 has values left)
{
  Value1 = enum1.Next()
  enum1pos++;
  //Skip over moved items.
  while (SkipList.Count > 0 && SkipList[0] == enum2.Position)
  {
    Value2 = enum2.Next()
    enum2pos++;
  }
  if (Value1 == Value2)
    Value2 = enum2.Next()
    enum2pos++;
    continue;

  int temp = enum2pos;
  while(Value1 !=Value and enum2 has more values)
  {
    Value2 = enum2.Next();
    enum2pos++;
  }
  if(Value1 != Value2)
    ItemDeleted(Value1);
  else
  {
    ItemMoved(Value1, enum2pos);
    SkipList.Add(enum2pos);
  }
  //This is expensive for IEnumerable!
  enum2.First();
  loop temp times
    enum2.Next();
  //if 
}
while (enum2 has values left)
{
  while (SkipList.Count > 0 && SkipList[0] == enum2.Position)
  {
    Value2 = enum2.Next()
    enum2pos++;
  }
  if (enum2 has values left)
  Added(Value2, enum2pos)
}

Результат: Сравнить A и A
Далее
Сравнить B и D
Найти B
B Moved -> 2
Добавить 2 в ПропуститьСписок
Сброс Enum2
Сравнение C и D
Поиск C
C Перемещение -> 3
Добавление 3 в список пропуска
Сброс Enum2
Далее
Сравнение D и D
Далее
Пропустить (2)
Пропустить (3)
Сравнить E и D1
Найти E
Удалено (E)
Далее
Добавлен конец Enum1 (D1, 4)

Я думаю, что где-то есть экономия, если enum2pos слишком далеко отстает, чтобы увидеть, был ли он удален, и если он не добавил пропуска для своей исходной позиции в enum1, этопоможет с постоянным сбросом позиции enum2.

1 голос
/ 23 марта 2012

Если вы предпочитаете использовать Linq, вот простое решение, основанное на вашем примере. Извините, но не уверен в производительности. 

var a = new List<string>{"A","B","C","D","E"};
var b = new List<string>{"A","C","B","D","D1"};

var removed = a.Except(b);
var moved = a.Where(x => b[a.IndexOf(x)] != x && !removed.Contains(x));
List<string> newlyInserted = new List<string>();
foreach (var item in removed)
{
    //Newly inserted into the list - D1
    newlyInserted.Add(b[a.IndexOf(item)]);
    //Index of D1 if required
    var indexOfNewlyAddedItem = a.IndexOf(item);
}

или просто 

var newlyAdded = b.Except(a);
...