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

Question

Delete (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 путем удаления каждого элемента.

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