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

Question

Delphi 的通用 TQueue class 有一个属性称为 Capacity. 如果 TQueue 中的项目数超过其容量，其他项目仍会添加到队列中。 The documentation 表示属性“获取或设置队列容量，即不调整大小的队列的最大大小。”听起来队列有点像固定长度的数组（在内存方面）——直到它满了，此时它变得更像一个动态数组？准确吗？

程序员什么时候想要或需要获取或设置 TQueue 的容量？

Answer 1

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

当项目数达到当前容量时，数组会重新分配（例如，将其大小加倍），您可以添加越来越多的元素。

如果您知道最大项目数的可靠限制，则值得设置 Capacity，这样您将避免内存重新分配，从而节省一些时间。

Answer 2

理论

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

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 等需要为无限数量的项目动态分配 space。为了提高性能，这些类确实分配了超出必要的部分。 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;

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

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

What is the purpose or function of the TQueue.Capacity property?

delphi

generics

queue

理论

应用理论

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

What is the purpose or function of the TQueue.Capacity property?

delphi

generics

queue

理论

应用理论

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