9

後続のすべての項目を下に移動する必要があるため、TList からの削除 (0) はコストがかかります。さらに大きなリストの先頭から多数のアイテムを削除する必要がある場合、最も速い方法は何ですか?

4

6 に答える 6

9

a の先頭から広範囲の要素を削除すると、負荷TListが高くなります。クラス名は欺くためにお世辞ですが、aTListは実際には配列です。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;
于 2011-12-01T22:39:29.270 に答える
4

Marcelo が既に述べたように、ブロック全体をコピーすることもできますが、アイテムごとにコピーする代わりに、Move() を 1 回呼び出すTList.Listだけで、引数として使用して全体を移動できます。

以前の Delphi バージョンでは( )TList.Listでしたが、Delphi XE2 では( ) になったので、正しい間接指定を使用する必要があります。PPointerList^TPointerList; TPointerList = array[0..MaxListSize - 1] of Pointer;TPointerListTPointerList = array of Pointer;

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

と

TList(aList).List[index]  // for Delphi XE2
于 2011-12-01T22:50:33.920 に答える
2

TList はポインターの配列であるため、XE2 で行う方法は次のとおりです。

実装は 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;

この証明には重大なメモリ リークがありますが、値を表示するためだけにオブジェクトを作成しました。

于 2011-12-02T00:24:22.483 に答える
1

順序が重要で、前に 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)

このコードはよく考えていないので、off-by-one エラーなどをチェックする必要があります。

順序が重要でない場合は、最後の N 個のアイテムを最初の N 個のアイテムと単純に交換し、最後の N 個のアイテムを上記のように削除できます。

于 2011-12-01T22:26:12.550 に答える
1

ここに考えがあります: リスト内のすべてのアイテムが割り当てられていることがわかっている場合は、削除したいアイテムを nil して、TList.Pack() を呼び出すだけで、空のスポットがどこにあるかを把握し、他のすべてをできるだけ効率的に脇に移動できます。 . ただし、これにはすべてのアイテムをスキャンする必要があるため、必要なものではないかもしれませんが、削除を使用しません (したがって、Nitofy 呼び出しを防ぎます)。Pack の実装は、D2006 と XE2 の間で少しも変わっていないので、その効率性に頼ることができます。

削除したいアイテムを nil するには、使用できますList[aIndex] := nilが、それでも Notify() 呼び出しが課されるため、List.List[aIndex] := nilその方が高速である可能性があることに注意してください。

于 2011-12-02T08:23:04.700 に答える
0

まず、BeginUpdate と EndUpdate を使用して、各項目を削除して TList の UI を更新しないようにします。

2 番目: 最初にリストの最下位にある項目を削除しようとします。つまり、リストの下から上にアイテムを削除すると、他のアイテムの効率が低下します。

于 2011-12-01T22:18:14.543 に答える