TQueue.Capacity属性的用途或功能是什么？

Question

Delphi的通用TQueue类具有一个名为Capacity.的属性，如果TQueue中的项数超过其容量，则仍会向队列中添加其他项。文献资料表示该属性“获取或设置队列容量，即队列的最大大小而不调整大小”。听起来，队列有点像一个固定长度的数组(内存方面的)--直到它满了，这时它变得更像一个动态数组了？这准确吗？

程序员何时需要或需要获得或设置TQueue的容量？

Answer 1

理论

考虑下面的示例，它生成一个随机整数的动态数组：

program DynArrAlloc;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  Windows, System.SysUtils;

const
  N = 100000000;

var
  a: TArray<Integer>;
  i: Integer;
  tc1, tc2: Cardinal;

begin

  tc1 := GetTickCount;

  SetLength(a, 0);
  for i := 1 to N do
  begin
    SetLength(a, Succ(Length(a)));
    a[High(a)] := Random(1000);
  end;

  tc2 := GetTickCount;
  Writeln(tc2 - tc1);
  Readln;

end.

在我的系统上，运行它需要4.5秒。

注意，我--在每次迭代中--重新分配数组，以便它可以再容纳一个项。

最好从一开始就分配一个足够大的数组：

program DynArrAlloc;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  Windows, System.SysUtils;

const
  N = 100000000;

var
  a: TArray<Integer>;
  i: Integer;
  tc1, tc2: Cardinal;

begin

  tc1 := GetTickCount;

  SetLength(a, N);
  for i := 1 to N do
    a[N - 1] := Random(1000);

  tc2 := GetTickCount;
  Writeln(tc2 - tc1);
  Readln;

end.

这一次，程序只需0.6秒。

因此，我们应该尽量避免不必要地重新分配。每次在第一个示例中重新分配时，我都需要请求更多的内存；然后，我需要将数组复制到新位置，最后释放旧内存。显然，这是非常低效的。

不幸的是，在开始时分配一个足够大的数组并不总是可能的。您可能根本不知道最后的元素计数。

然后，一种常见的策略是分步骤分配:当数组满了并且需要多一个时隙时，再分配几个插槽，但要跟踪实际使用的插槽数：

program DynArrAlloc;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  Windows, System.SysUtils;

const
  N = 100000000;

var
  a: TArray<Integer>;
  i: Integer;
  tc1, tc2: Cardinal;
  ActualLength: Integer;

const
  AllocStep = 1024;

begin

  tc1 := GetTickCount;

  SetLength(a, AllocStep);
  ActualLength := 0;
  for i := 1 to N do
  begin
    if ActualLength = Length(a) then
      SetLength(a, Length(a) + AllocStep);
    a[ActualLength] := Random(1000);
    Inc(ActualLength);
  end;

  // Trim the excess:
  SetLength(a, ActualLength);

  tc2 := GetTickCount;
  Writeln(tc2 - tc1);
  Readln;

end.

现在我们需要1.3秒。

在本例中，我按固定大小的块分配.更常见的策略可能是在每次重新分配时将数组加倍(或乘以1.5或其他什么)，或者聪明地组合这些选项。

应用理论

在引擎盖下，TList<T>、TQueue<T>、TStack<T>、TStringList等需要为无限数量的项动态分配空间。为了使这个性能更好，这些类确实分配了不必要的更多内容。Capacity是您可以在当前分配的内存中容纳的元素数，而Count <= Capacity是容器中的实际元素数。

您可以设置Capacity属性，以减少填充容器时对中间分配的需求，并且从一开始就知道元素的最终数量：

var
  L: TList<Integer>;

begin

  L := TList<Integer>.Create;
  try
    while not Something.EOF do
      L.Add(Something.GetNextValue);
  finally
    L.Free;
  end;

可以，并且可能只需要几个重新分配，但是

  L := TList<Integer>.Create;
  try
    L.Capacity := Something.Count;
    while not Something.EOF do
      L.Add(Something.GetNextValue);
  finally
    L.Free;
  end;

将更快，因为将没有中间重新分配。

Answer 2

内部TQueue包含存储元素的动态数组。

当项目计数达到当前容量时，数组将被重新分配(例如，将其大小加倍)，并且您可以添加越来越多的元素。

如果您知道最大项计数的可靠限制，那么设置Capacity是值得的，因此您将避免内存重新分配，从而节省一些时间。