Какой эффективный способ удаления большого блока элементов с начала TList в Delphi

Question

Удаление (0) из TList стоит дорого, потому что все последующие элементы должны быть перемещены вниз. Если мне нужно удалить большое количество элементов из начала еще большего списка, какой самый быстрый способ?

Answer 1

Удаление большого диапазона элементов с начала TList стоит дорого.Хотя имя класса льстит, чтобы обмануть, TList на самом деле массивВ TList нет возможности удалить диапазон - каждый элемент должен быть удален индивидуально, а затем остальная часть списка перемещается вниз.Для большого диапазона, который спровоцирует очень много перераспределений и перемещений полного списка.

Если у вас более современный Delphi, вы можете использовать универсальный класс списка TList<T> и воспользоваться самим собой.метода DeleteRange.Документация включает в себя это важное примечание:

Это операция O (ACount).

В Delphi 2006 вы можете написать что-то с эквивалентными характеристиками производительности, например так:

procedure DeleteRange(List: TList; AIndex, ACount: Integer);
var
  i: Integer;
  NewCount: Integer;
begin
  NewCount := List.Count-ACount;
  Assert(AIndex>=0);
  Assert(ACount>=0);
  Assert(NewCount>=0);
  for i := AIndex to NewCount-1 do
    List[i] := List[i+ACount]
  List.Count := NewCount;
end;

Answer 2

Как уже сказал Марсело, вы можете скопировать весь блок, но вместо того, чтобы делать этот элемент за элементом, вы можете переместить все одним вызовом Move (), используя TList.List в качестве аргумента.

Обратите внимание, что TList.List было PPointerList (^TPointerList; TPointerList = array[0..MaxListSize - 1] of Pointer;) в более старых версиях Delphi и стало TPointerList (TPointerList = array of Pointer;) в Delphi XE2, поэтому вы должны использовать правильное перенаправление:

TList(aList).List^[index] // for older Delphi's

и

TList(aList).List[index]  // for Delphi XE2

Answer 3

Вот как вы это делаете в XE2, поскольку TList - это массив указателей.

Реализация будет похожа на Delphi 2006, но я не могу написать код, так как у меня нет 2006.

// I have 1000000 items, and I want to delete the first 5000
// Copy the pointer array items up the array
CopyMemory(@myList.List[0],
  @myList.List[5000],
  SizeOf(Pointer) * (myList.Count - 5000));
// Reset the count. Delphi cooperates as long as we're shrinking
myList.Count := myList.Count - 5000;
// You now have tons of unused memory at the end, it's fine
// but if you want to clean house
myList.Capacity := myList.Count;

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

Вот доказательство:

type
  TMyObject = class
    index: Integer;
  end;

procedure TForm1.Button1Click(Sender: TObject);
var
  myList: TList;
  i: Integer;
  myObject: TMyObject;
begin
  // Create a list with 1000000 entries
  myList := TList.Create;
  for i := 1 to 1000000 do
  begin
    myObject := TMyObject.Create;
    myObject.index := i;
    myList.Add(myObject);
  end;
  // Delete the first 5000
  CopyMemory(@myList.List[0],
    @myList.List[5000],
    SizeOf(Pointer) * (myList.Count - 5000));
  myList.Count := myList.Count - 5000;
  myList.Capacity := myList.Count;
  // Show the new count
  ShowMessage(IntToStr(myList.Count));
  // Shows that my array now has objects 5001 and up
  for i := 0 to 5 do
  begin
    myObject := TMyObject(myList.Items[i]);
    ShowMessage(IntToStr(myObject.index));
  end;
end;

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

Answer 4

Вот мысль: если вы знаете, что все элементы в вашем Списке назначены, вы можете обнулить те, которые хотите удалить, и просто вызвать TList.Pack (), который определяет, где находятся пустые места, и отодвигает все остальное в сторону, как эффективно, насколько это возможно. Это требует сканирования всех элементов, поэтому, возможно, это не то, что вам нужно, но он не использует Delete (и, таким образом, предотвращает вызовы Nitofy). Внедрение Pack не сильно изменилось между D2006 и XE2, поэтому вы можете зависеть от его эффективности.

Обратите внимание, что для обнуления элементов, которые вы хотите удалить, вы можете использовать List[aIndex] := nil, но это все равно будет вызывать вызов Notify (), поэтому List.List[aIndex] := nil может быть быстрее для этого.

Answer 5

Если порядок имеет значение, и у вас есть N предметов, которые нужно удалить спереди:

for I := 0 to List.Count - N - 1 do
    list[I] := list[I + N];
for I := list.Count - 1 downto list.Count - N do
    list.Delete(I)

Я не очень хорошо продумал этот код, поэтому вам нужно будет проверять наличие отдельных ошибок и т. П.

Если порядок не имеет значения, вы можете просто обменять последние N элементов на первые N элементов и удалить последние N элементов, как указано выше.

Answer 6

Прежде всего, используйте BeginUpdate и EndUpdate, чтобы предотвратить обновление пользовательского интерфейса TList путем удаления каждого элемента.

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