Что такое эффективный способ удаления большого блока предметов с самого начала TLILD в Delphi
-
27-10-2019 - |
Вопрос
Удалить (0) из TLIST стоит дорого, потому что все последующие элементы должны быть перенесены вниз. Если мне нужно удалить большое количество элементов с самого начала еще большего списка, какой самый быстрый способ?
Решение
Удаление большого диапазона элементов с начала 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;
Другие советы
Как уже сказал Марсело, вы можете скопировать весь блок, но вместо того, чтобы делать этот элемент по элементу, вы можете переместить все с одним вызовом, чтобы перемещать (), используя 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
Вот как вы делаете это в 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;
У доказательства есть серьезные утечки памяти, но мы создали объекты только для того, чтобы показать значения.
Если заказ имеет значение, и у вас есть 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 элементы, как указано выше.
Вот мысль: если вы знаете, что все элементы в вашем списке присваиваются, вы могли бы не удалить те, которые хотите удалить, и просто позвонить в tlist.pack (), что выясняет, где находятся пустые места, и отодвигает все остальное в сторону как можно более эффективно Анкет Это требует сканирования по всем элементам, так что это может быть не то, что вы хотите, но он также не использует Delete (и, таким образом, предотвращает Nitofy Calls). Реализация пакета не изменилась между D2006 и XE2, поэтому вы можете зависеть от его эффективности.
Обратите внимание, что ноль удаленных предметов, вы можете использовать List[aIndex] := nil
но это все равно навязало бы вызов notify (), поэтому List.List[aIndex] := nil
может быть быстрее для этого.
Прежде всего, используйте NegnupDate и EndupDate, чтобы предотвратить обновление пользовательского интерфейса TLIST, удаляя каждый элемент.
Второе: попробуйте сначала удалить элементы в самом нижнем в списке. Другими словами, удаление элементов из вниз к списку требуется менее эффективно для других элементов.