当我事先不知道我将要拥有多少物品时,我应该如何为物品清单分配空间？

Question

在另一个问题中,David Heffernan发表了一篇关于他"所有时间最不喜欢的Delphi结构"的评论:

SetLength(FItems, Length(FItems)+1);

他不喜欢的构造在Pebongo项目中被大量使用,例如在这段摘录中:

procedure TBSONDocument.ReadStream( F: TStream ); 
var 
  len : integer; 
  elmtype : byte; 
  elmname : string; 
begin 
  Clear; 
  f.Read( len, sizeof( len ) ); 
  f.Read( elmtype, sizeof( byte ) ); 

  while elmtype <> BSON_EOF do // Loop
  begin 
    elmname := _ReadString( f ); 
    SetLength( FItems, length( FItems ) + 1 ); // This, spotted by TOndrej
    case elmtype of 
      BSON_ARRAY: FItems[high( FItems )] := TBSONArrayItem.Create; 
      BSON_BINARY: FItems[high( FItems )] := TBSONBinaryItem.Create; 
      ...
    end; 
    f.Read( elmtype, sizeof( byte ) ); 
  end; 
end; 

有哪些替代方案？

Answer 1

它SetLength()本身并不是坏的,而是增加了循环中的长度.坏代码示例:

SetLength( Result.FItems, 0 ); 

for i := 0 to high( FItems ) do 
begin 
  SetLength(Result.FItems, Length(Result.Fitems)+1);
  Result.FItems[i] := FItems[i].Clone; 
end; 

在这种情况下,数组被重新排列并在每次迭代时重新分配内存.您发布的示例未显示错误的使用情况SetLength()

Answer 2

我所说的是一次增加动态数组1个元素:

SetLength(FItems, Length(FItems)+1);

在循环中,对于大型数组,这可能导致内存地址碎片.发生这种情况时,即使总可用地址空间很大,您也会发现自己无法分配大量连续的内存块.如果受到32位地址空间的限制,这可能是一个非常现实的问题.此外,性能也可能是一个问题.

有多种方法可以避免这个问题:

• 预分配数组.有时这涉及迭代两次,一次计数项目,一次填充数组.这可以非常有效.事实上,这正是TBSONDocument.Clone你的问题所做的.
• 使用TList或TList<T>容器.虽然这些使用动态数组作为其底层存储,但它们实现了基于容量的分配方法.当它们满了时,它们会分配大量额外的物品,以备将来添加.这再次非常有效.
• 另一个用作最后手段的选择是远离连续分配的内存.以块为单位分配内存,并使用类或记录的索引属性在索引与存储所在的实际块和位置之间进行映射.这在避免地址空间碎片方面特别有效.