arrays - 配列への複数の挿入を効率的に処理するにはどうすればよいですか?

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 ループではなく Move を使用すると、パフォーマンスがすでにかなり改善されました。これは、配列が大きくなる必要があるときに配列が 2 回コピーされるのを防ぐためです (1 回は既存の配列の SetLength で、もう 1 回は Move で)。 ）。

ただし、最悪の場合、 Insert(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つの位置だけ移動して、平均で1つだけ現在の 1/2 ではなく、/4 のエントリを移動する必要があります。

別のオプションは、スパース配列を実装することです。1990 年代に商用ライブラリでそのような実装を見たのを覚えていますが、それがどれだったかは覚えていません (TurboPower?)。

この手順は、数十のエントリから前述の数百万のエントリまで、さまざまなサイズの配列で機能するソートおよびインデックス コードの中心です。

現在、プログラムは約 2 時間 (最適化前は 5 時間近く) 実行され、配列内のエントリ数が少なくとも 2 倍になることがわかっています。配列が大きくなるほど挿入のパフォーマンスが低下するため、エントリ数が 2 倍になると、実行時間は少なくとも 4 倍になると思います。

パフォーマンスを調整する方法についていくつかの提案をしたいと思います。メモリ消費は現在のところそれほど問題ではありませんが、実行時間は間違いなく問題です。

(これは Delphi 2007 ですが、新しい Delphi バージョンに上記を実行するための最適化されたライブラリが既にある場合を除き、大きな違いはありません。Classes.TList は最適化されていません。)

Edit1: 上記のスパース配列の実装を見つけました: TurboPower SysTools の StColl です。

Edit2: OK、いくつかの背景: 私のプログラムは、現在 240 万のエントリを持つ DBase テーブルを読み取り、これらのエントリからいくつかの新しいテーブルを生成します。新しいテーブルは正規化され、作成後にインデックスが作成されます (パフォーマンス上の理由から、データを挿入する前にインデックスを生成しませんが、最初に試してみました)。配列は、生成されたテーブルの内部ソートを提供するコードの中心部分です。新しいレコードはテーブルに追加されるだけですが、それらの RecNo は並べ替えられた順序で配列に挿入されます。

Answer 1

あなたの手順を見てすぐに、いくつかの欠陥に気づきました。進行状況を確認するために、最初に最悪のシナリオで既存の手順の速度を測定しました（常に0の位置に数字を追加します）。

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

測定: n=500000 47.6 ms

A) シンプルさ

手順から不要な行をいくつか削除しました (OldList はまったく不要です。SetLength はメモリを保持します)。

改善A:

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 ms)

B) すべてが重要

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

• ヒント 1: 関数 Length はすべての挿入で呼び出されます
• ヒント 2: FCount+1 は毎回計算されます
• ヒント 3: const としてのプロシージャ パラメーター (参照による)
• ヒント 4: FCapacity 変数を導入する
• ヒント 5: 長さを 100 だけ増やすと、多くの再割り当てが発生します (250 万の配列で 25.000)。あなたが言うように、メモリは問題ではありません。

改善 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 ms)。

ヒント: Inc by 100000 の代わりに、プログレッシブ アルゴリズムを実装できます。

C) ボトルネック

今の手順を見ると、何も残っておらず、大量のメモリが移動しているだけです。アルゴリズムを変更できない場合は、メモリの移動を改善する必要があります。

実際に fastmove チャレンジがありました (fastcode.sourceforge.net)

必要なファイル (3 つのファイル、ソース コード) だけを含む zip を用意しました。リンク >>> http://www.dakte.org/_stackoverflow/files/delphi-fastcode.zip

• プロジェクトに fastcodeCPUID.pas と fastmove.pas を追加してください!
• 挿入には fastmove.pas を使用します。
• 出来上がり！他に変更点はありません！

私のマシンでは速度がほぼ 50%向上しました (使用している CPU によって異なります)。

元の手順

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

高速移動なしで改善 (-7%)

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

改善、ファストムーブあり (-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 の実装です (必要に応じて if を追加するか、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 からのスピード ゲイン) なし!

結論: FastMove またはアルゴリズムの変更、メモリ移動速度の「物理的」制限に達しました!

私は 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 ルーチンがありますが、サイトから直接ダウンロードしたもの (または上記のリンクからダウンロードしたもの) を含めると、最大の違いがあり、ほぼ 50% (奇妙) になりました。

Answer 2

ネタバレになることはありませんが、解決策はすでに私の質問への編集にあります:

アレイからTurboPower の StCollに切り替えた後、大規模なアレイでパフォーマンスが低下することはなくなり、起動が非常に高速になりました。実行時間は 2 時間から 0.5 時間未満に短縮されました。変更は本当に簡単でした。あの図書館をもっと早く覚えていたらよかったのに。

SourceForge リポジトリから次のファイルが必要でした (ライブラリ全体をダウンロードしたくありませんでした)。

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

実際、相互依存関係がこれ以上なかったことに驚いています。TurboPower の連中は間違いなく自分たちの取引を知っていました。彼らは今日何をしているのか、まだカジノ用のギャンブルマシンをプログラミングしているのだろうか?