如何有效地處理多個插入數組？

Question

我有一個動態分配的整數數組，我想將整數插入到任意位置。在250萬以上的許多整數。

我的代碼目前看起來是這樣的：

type 
    TIntegerArr = array of Integer; 

var 
    FCount: Integer; 
    FSortedList: TIntegerArr; 

procedure Insert(_Value: Integer; _InsertPos: integer); 
var 
    OldList: TIntegerArr; 
begin 
    OldList := FSortedList; 
    if Length(FSortedList) < FCount + 1 then begin 
    OldList := FSortedList; 
    FSortedList := nil; 
    SetLength(FSortedList, FCount + 100); 
    CopyMemory(@FSortedList[0], @OldList[0], SizeOf(Integer) * _InsertPos); 
    end; 
    MoveMemory(@FSortedList[_InsertPos + 1], @OldList[_InsertPos], SizeOf(Integer) * (FCount - _InsertPos)); 
    FSortedList[_InsertPos] := _Value; 
    Inc(FCount); 
end; 

（真正的代碼是具有FSortedList和FCOUNT作爲字段一個類的方法。）

使用的臨時列表，並使用移動而不是用於移動數據的for循環改進了性能已經相當多，因爲它防止數組在需要增長時被複制兩次（一次在現有陣列上的SetLength中，另一次在Move中）。

但最壞的情況插入（SomeValue，0）仍然會移動所有現有的值。

到目前爲止，我正在考慮在數組的開始處引入一個偏移量，而不是每次在前面插入一個新值都要移動所有現有值，我只能在偏移量達到0。例如：

// simple case: inserting at Position 0: 
if FOffset = 0 then begin 
    // [...] reallocate a new array as above 
    Move(@FSortedList[100], @OldList, SizeOf(Integer) * _InsertPos); 
    FOffset := 100; 
end; 
Dec(FOffset); 
FSortedList[FOffset] := _NewValue; 

（該代碼是未經測試，可能車） 這當然可以擴展到檢查插入點是否是接近的開始或結束，並根據該移動或者第一或最後一個值的位置，因此平均而言，只有1/4的條目必須移動，而不是像現在這樣1/2。

另一種選擇是實現一個稀疏數組。我記得在1990年代的一些商業圖書館看到了這樣的實現，但不記得它是什麼（TurboPower？）。

此過程對於一些排序和索引代碼至關重要，該代碼適用於從幾十個條目到上述數百萬條目的不同大小的數組。

目前該程序運行約2小時（在我的優化之前它接近5個小時），並且我已經知道陣列中的條目數至少會增加一倍。隨着插入性能越差，陣列已經越大，我懷疑如果條目數增加一倍，運行時間至少會增加四倍。

我想就如何調整性能提出一些建議。內存消耗目前不是什麼大問題，但運行時間肯定是。

（這是德爾福2007年，但不應該有太大的差異，除非較新版本的Delphi已經做上述優化的庫Classes.TList不是最優化的。）

EDIT1：剛發現稀疏我上面提到的數組實現：它是TurboPower SysTools的StColl。

編輯2：好吧，一些背景：我的程序讀取一個包含當前240萬個條目的DBase表，並從這些條目生成幾個新表。新表格已經過規範化並在創建之後進行索引（出於性能方面的考慮，我在插入數據之前不會生成索引，請相信我，我先試了一下）。該數組是代碼的核心部分，爲生成的表提供內部排序。新記錄僅附加到表中，但它們的RecNo按排序順序插入到數組中。

Answer 1

不是一個掃興的，但解決方案已經在編輯我的問題：

從數組TurboPower's StColl性能不再與大型陣列降解，是相當快的啓動開關後。運行時間從2小時縮短到不到1/2小時。變化非常簡單。我希望我早點記得那個圖書館。

我需要從SourceForge上的存儲庫（我不想下載整個庫）以下文件：

• StBase.pas
• StColl.pas
• StConst.pas
• StList.pas
• StDefine.inc

其實我小號感到驚訝的是沒有更多的相互依存關係。 TurboPower的人肯定知道他們的交易。我想知道他們今天在做什麼，仍然在爲賭場編程賭博機器？

Answer 2

在看完你的程序後，我注意到一些缺陷。爲了看到進展，我首先在最壞的情況下測量現有程序的速度（在0位置添加總數）。

n:=500000; 
for i:=0 to n-1 
do Insert(i, 0); 

測量：N = 500000 47.6毫秒

A）簡單

我刪除了一些不必要的行從你的程序（OldList是完全不必要的，SetLength保留存儲器）。

改進：

procedure Insert(_Value: Integer; _InsertPos: integer); 
begin 
if Length(FSortedList) < FCount + 1 
    then SetLength(FSortedList, FCount + 100); 
    Move(FSortedList[_InsertPos], FSortedList[_InsertPos+1], SizeOf(Integer) * (FCount - _InsertPos)); 
    FSortedList[_InsertPos] := _Value; 
    Inc(FCount); 
end; 

速度增益6％（44.8毫秒）

B）一切計數

if Length(FSortedList) < FCount + 1 
    then SetLength(FSortedList, FCount + 100); 

• 提示1：功能長度一世這叫上的每個刀片
• 提示2：FCOUNT + 1計算出每時間
• 提示3：程序參數爲const（通過引用）
• 提示4：引入FCapacity可變
• 提示5：增加的長度由只有100個會導致很多重新分配（250萬個陣列中的25000個）。正如你所說，記憶不是問題，那麼爲什麼不預先分配所有或至少大？

改進B：

procedure Insert(const _Value, _InsertPos: integer); 
begin 
if FCount = FCapacity 
    then begin 
    Inc(FCapacity, 100000); 
    SetLength(FSortedList, FCapacity); 
    end; 
Move(FSortedList[_InsertPos], FSortedList[_InsertPos+1], SizeOf(Integer) * (FCount - _InsertPos)); 
FSortedList[_InsertPos] := _Value; 
Inc(FCount); 
end; 

速度增益1％（44.3毫秒）。

提示：而不是由100000公司你可以實現一些漸進算法。

C）瓶頸

如果我們看一下過程現在，沒有什麼留下，只是大量的內存移動。如果我們不能改變算法，我們必須改善記憶移動。

有實際

我準備了一個拉鍊，只有那些你需要的文件（3個文件，源代碼）fastmove挑戰（fastcode.sourceforge.net）。鏈接>>>http://www.dakte.org/_stackoverflow/files/delphi-fastcode.zip

• 將fastcodeCPUID.pas和fastmove.pas添加到您的項目！
• 插入使用fastmove.pas;
• Voila！沒有別的改變！我的機器幾乎50％上

速度增益（取決於你使用的CPU）。

原始程序

n   ms graph 
--------------------------------- 
100000 1.8 * 
200000 7.6 *** 
300000 17.0 ******* 
400000 30.1 ************* 
500000 47.6 ******************** 

改進，而不fastmove（-7％）

n   ms graph 
--------------------------------- 
100000 1.6 * 
200000 6.9 *** 
300000 15.7 ****** 
400000 28.2 *********** 
500000 44.3 ****************** 

改善，fastmove（-46％）

n   ms graph 
--------------------------------- 
100000 0.8 * 
200000 3.8 ** 
300000 9.0 **** 
400000 16.3 ******* 
500000 25.7 *********** 

篇

最新評論：

if FCount = FCapacity 
    then begin 
    if FCapacity<100000 
     then FCapacity:=100000 
     else FCapacity:=FCapacity*2; 
    SetLength(FSortedList, FCapacity); 
    end; 

就像我說的，你可以添加一些進步FCapacity增加。這是一些經典的Grow實現（如果需要，只需添加更多或者將100000更改爲更合適的值）。

d）更新2：數組作爲^在tarray

type 
    PIntegerArr3 = ^TIntegerArr3y; 
    TIntegerArr3y = array[0..1] of Integer; 

var 
FCapacity3, 
FCount3: Integer; 
FSortedList3: PIntegerArr3; 

procedure ResizeArr3(var aCurrentArr: PIntegerArr3; const aNewCapacity: Integer); 
var lNewArr: PIntegerArr3; 

begin 
GetMem(lNewArr, aNewCapacity*SizeOf(Integer)); 

if FCount3>0 // copy data too 
    then begin 
    if aNewCapacity<FCount3 
     then FCount3:=aNewCapacity; // shrink 
    Move(aCurrentArr^[0], lNewArr^[0], FCount3*SizeOf(Integer)); 
    end; 

FreeMem(aCurrentArr, FCapacity3*SizeOf(Integer)); 
FCapacity3:=aNewCapacity; 
aCurrentArr:=lNewArr; 
end; 

procedure FreeArr3; 
begin 
if FCapacity3>0 
    then begin 
    FreeMem(FSortedList3, FCapacity3*SizeOf(Integer)); 
    FSortedList3:=nil; 
    end; 
end; 

procedure Insert3(const _Value, _InsertPos: integer); 
begin 
if FCount3 = FCapacity3 
    then ResizeArr3(FSortedList3, FCapacity3 + 100000); 
Move(FSortedList3^[_InsertPos], FSortedList3^[_InsertPos+1], SizeOf(Integer) * (FCount3 - _InsertPos)); 
FSortedList3^[_InsertPos] := _Value; 
Inc(FCount3); 
end; 

速度增益從步驟C）無！

結合：快速移動或算法更改，達到內存移動速度的「物理」極限！

我正在使用Delphi XE3和System。PAS，線路5307：

(* ***** BEGIN LICENSE BLOCK ***** 
* 
* The assembly function Move is licensed under the CodeGear license terms. 
* 
* The initial developer of the original code is Fastcode 
* 
* Portions created by the initial developer are Copyright (C) 2002-2004 
* the initial developer. All Rights Reserved. 
* 
* Contributor(s): John O'Harrow 
* 
* ***** END LICENSE BLOCK ***** *) 

procedure Move(const Source; var Dest; Count: NativeInt); 

所以實際上在Delphi是媒體鏈接一些Fastcode套路，但包括那些直接從他們的網站下載（或鏈接我上面包括）取得了最大的diferrence，近50％（怪）。