¿Cuál es una forma eficiente de eliminar un gran bloque de elementos desde el comienzo de una tlist en Delphi?

Question

Eliminar (0) de una tlist es costoso porque todos los artículos posteriores deben moverse hacia abajo. Si necesito eliminar una gran cantidad de elementos desde el comienzo de una lista aún más grande ¿Cuál es la forma más rápida?

Answer 1

Eliminar una amplia gama de elementos desde el comienzo de un TList es caro. Aunque el nombre de la clase halagará para engañar, un TList de hecho es una matriz. En TList No hay una instalación para eliminar un rango, cada elemento debe eliminarse individualmente y luego se mueve el resto de la lista. Para una amplia gama que provocará una gran cantidad de reasignaciones y movimientos completos de la lista.

Si tuviera un Delphi más moderno, podría usar la clase de lista genérica TList<T> y aprovechar el DeleteRange método. La documentación incluye esta nota vital:

Esta es una operación O (poste).

En Delphi 2006 puedes escribir algo con características de rendimiento equivalentes como esta:

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

Como Marcelo ya dijo, podría copiar todo el bloque, pero en lugar de hacer ese elemento por elemento, podría mover todo con una llamada para mover (), usando TList.List como argumento.

Tenga en cuenta que TList.List era un PPointerList (^TPointerList; TPointerList = array[0..MaxListSize - 1] of Pointer;) en versiones más antiguas de Delphi y se convirtió en un TPointerList (TPointerList = array of Pointer;) en Delphi XE2, por lo que debe usar la indirección correcta:

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

y

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

Answer 3

Así es como lo haces en XE2, ya que tlist es una variedad de punteros.

La implementación será similar en Delphi 2006, pero no puedo escribir el código ya que no tengo 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;

Mientras todas las cosas que señalan los punteros son la memoria manejada en otro lugar, no hay fuga.

Aquí está la prueba:

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;

La prueba tiene grandes fugas de memoria, pero creamos los objetos solo para mostrar los valores.

Answer 4

Si el pedido es importante, y tiene n elementos para quitar en el frente:

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)

No he pensado muy bien este código, por lo que deberá verificar los errores fuera de uno y similares.

Si el pedido no importa, simplemente puede intercambiar los últimos n elementos con los primeros n elementos, y eliminar los últimos n elementos como se indican anteriormente.

Answer 5

Aquí hay un pensamiento: si sabe que se asignan todos los elementos de su lista, puede no hacer los que desea eliminar y simplemente llamar a tlist.pack (), que descubre dónde están las manchas vacías y mueven todo lo demás de la manera más eficiente posible como sea posible. . Sin embargo, esto requiere un escaneo a través de todos los elementos, por lo que puede no ser lo que desea, pero no utiliza Delete (y, por lo tanto, también evita las llamadas NITOFY). La implementación del paquete no ha cambiado un poco entre D2006 y XE2, por lo que puede depender de su eficiencia.

Tenga en cuenta que para que para los elementos que desea eliminar, podría usar List[aIndex] := nil Pero eso aún impondría una llamada de notificación (), así que List.List[aIndex] := nil Podría ser más rápido para eso.

Answer 6

En primer lugar, use BeginUpdate y Endupdate para evitar actualizar la interfaz de usuario de la TLIST eliminando cada elemento.

Segundo: intente eliminar los elementos en el más inferior de la lista primero. En otra palabra, la eliminación de elementos de abajo hasta arriba la lista requiere menos eficiente en otros elementos.