[РЕШЕНО] Различия между двумя списками (TList)

[Brainenjii]

Есть ли у кого ссылка на готовый алгоритм сравнения? Подаёшь на вход 2 списка, получаешь список совпадений, список "недостающих" и "лишних" элементов. Спасибо

[ronin]

а можно полюбопытничать что за задача?

[Brainenjii]

задача простенькая. Есть список (TList), отображение на БД выглядит как таблица, каждое поле которой соответствует элементу этого списка. При изменении этого списка, соответственно, должна меняться структура этой таблицы. И чтобы выяснить, какие поля в БД я должен убрать, а какие - добавить - мне нужно это дело посчитать ^_^
Да и вообще, обычно если одному объекту соответствует несколько записей в БД, я обычно удаляю всё старое и заполняю новым содержимым. С механизмом поиска отличий можно будет ускорить все эти операции ^_^

[ronin]

я решал данный вопрос обычным перебором обоих списков, тут ничего гениального, единственно для ускорения перебора я при сравнении первого списка со вторым просматривал не весь второй список а только диапазон +-n элементов с расчётом на то что изменения затронули этот диапазон, если элемент в этом диапазоне не находился то запускался поиск в верхней части списка (перед диапазоном), и при необходимости в нижней (после диапазона)... второй же список проверялся только на отсутствие элементов в первом полным перебором

и да, после некоторых опытов я решил заменить TList динамическими массивами, скорость меня удовлетворяет, например при сравнении массивов состоящих из примерно 50000 элементов каждый процесс занимает около 10 сек, соответственно скорость зависит от кол-ва изменений (ну и железа конечно ), чем их больше, тем дольше сравнение, в вашем случае я думаю кол-во элементов не такое большое

[minoshi]

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

[Vadim]

Добавить к каждой строке сумму этой строки и сравнивать только суммы. Тогда простым перебором будет очень быстро.

[tema]

Создать для каждого списка стек изменений. Тогда только самое первое сравнение займёт ощутимое время.

[Brainenjii]

Сравнивать нужно было не строки, а целочисленные значения, к счастью.
Сделал по предложению Minoshi, благо и сам к такому склонялся. Хотя вариант со стеком предпочтительнее - проще будет затем реализовать Undo.
Получилось так:

Код: Выделить всё

Procedure BList.Compare(Const aTarget: BList; Out aSame, aOver, aLack: BList);
Var
  i, j: Integer;
  aID, aTargetID: Integer;
Begin
  If aTarget = nil Then Raise Exception.Create('Illegal nil Target');

  Sort;
  aTarget.Sort;

  i := 0;
  j := 0;
  While TRUE Do
    Begin
      If i = Count Then aID := -1
      Else aID := GetAt(i).ID;
      If j = aTarget.Count Then aTargetID := -1
      Else aTargetID := aTarget.GetAt(j).ID;

      If (aID = -1) And (aTargetID = -1) Then Break;

      If aID = aTargetID Then
        Begin
          aSame.Add(GetAt(i));
          Inc(i);
          Inc(j);
        End
      Else
        Begin
          If ((aID < aTargetID) Or (aTargetID = -1)) And Not(aID = -1) Then
            Begin
              aOver.Add(GetAt(i));
              Inc(i)
            End;
          If ((aID > aTargetID) Or (aID = -1)) And Not(aTargetID = -1) Then
            Begin
              aLack.Add(aTarget.GetAt(j));
              Inc(j);
            End;
      End;
    End;
End;


Проверка:

Код: Выделить всё

program project2;

Uses
  sysutils, Classes, BListsUnit, BObjectUnit;

Type

{ BMyClass }

BMyClass = Class(BObjectClass)
  Private
  Public
    Destructor Burn; override;
End;

Type BMyList = Specialize BList<BMyClass>;

{ BMyClass }

Destructor BMyClass.Burn;
Begin

End;

Var
  i: Integer;
  aBuffer: String;
  aMoment: TDateTime;
  aStringList: TStringList;
  aSource, aTarget, aSame, aOver, aLack: BMyList;

Begin
  aSource := BMyList.Build;
  aTarget := BMyList.Build;
  aSame := BMyList.Build;
  aOver := BMyList.Build;
  aLack := BMyList.Build;

  For i := 0 To 100000 Do
    Begin
      aSource.Add(BMyClass.Build(Random(1000000)));
      aTarget.Add(BMyClass.Build(Random(1000000)));
    End;

  aMoment := Now;
  aSource.Compare(aTarget, aSame, aOver, aLack);
  WriteLn(FormatDateTime('hh:mm:ss:zz', Now - aMoment)); <- 00:00:00:243

  // Проверял "вглазную" на малом кол-ве элементов - всё хорошо
  // Надо бы добавить автоматизированный тест
  //aStringList := TStringList.Create;

  //For i := 0 To aSource.Count - 1 Do
  //  aStringList.Add(IntToStr(aSource[i].ID));
  //aStringList.SaveToFile('aSource.txt');
  //aStringList.Clear;
  //
  //For i := 0 To aTarget.Count - 1 Do
  //  aStringList.Add(IntToStr(aTarget[i].ID));
  //aStringList.SaveToFile('aTarget.txt');
  //aStringList.Clear;
  //
  //For i := 0 To aSame.Count - 1 Do
  //  aStringList.Add(IntToStr(aSame[i].ID));
  //aStringList.SaveToFile('aSame.txt');
  //aStringList.Clear;
  //
  //For i := 0 To aOver.Count - 1 Do
  //  aStringList.Add(IntToStr(aOver[i].ID));
  //aStringList.SaveToFile('aOver.txt');
  //aStringList.Clear;
  //For i := 0 To aLack.Count - 1 Do
  //  aStringList.Add(IntToStr(aLack[i].ID));
  //aStringList.SaveToFile('aLack.txt');
  //aStringList.Clear;

  //aStringList.Free;
end.


Из недостатков - нет вариантов обработки дубликатов в списках. Но в моём случае это ситуация, достойная исключения, так что не стал заморачиваться

[wavebvg]

но если не много, то отсортировать оба списка и затем проверить построчно

Как раз если много, тогда лучше отсортировать и идти по двум спискам одновременно сравнивая элементы и заполняя выходные списки... А ещё лучше:
1. Создать копии обоих списков (если исходные списки нельзя портить)
2. Отсортировать списки в одном направлении
3. Идти по двум сортированным спискам и, сделав вывод о состоянии элемента списка, удалять его из основного, вместо перехода к следующему, что обеспечит работу с многократным повторением элементов
4. Окончание цикла - один из списков - пуст
5. Оставшиеся элементы второго списка отнести к категории "есть только в одном из списков"

[Brainenjii]

Интересно.. Но, кажется, выигрыш получу только в читабельности - сложность примерно та же с тем что у меня ^_^