2

私は Delphi プログラマーです。プログラムでは、「枝」の長さが異なる 2 次元配列を生成する必要があります。それらは非常に大きく、操作には数秒かかります (面倒です)。

例えば：

var a: array of array of Word;
  i: Integer;

begin
   SetLength(a, 5000000);
   for i := 0 to 4999999 do
      SetLength(a[i], Diff_Values);
end;

コマンド SetLength(a, dim1, dim2) を認識していますが、適用できません。dim2 の最小値 (> 0) を設定せず、そこから続行します。これは、dim2 の最小値が 0 であるためです (一部の「ブランチ」は空になる可能性があります)。

それで、それを速くする方法はありますか？5..10% だけでなく、本当に高速です...

ありがとうございました。

4

4 に答える 4

5

大量のデータを処理する場合、多くの作業を行う必要があります。これにより、処理できる時間の理論上の最小値が設定されます。

500 万回の反復ごとに、次のことを行う必要があります。

  • 何とか「枝」の大きさを決める
  • メモリ マネージャーから適切なサイズの新しい配列を割り当てます。
  • 新しい配列で使用されるすべてのメモリをゼロにします (これは SetLength が自動的に行います)。

ステップ 1 は完全に制御可能であり、最適化できる可能性があります。ただし、2 と 3 は、Delphi の最新バージョンを使用している場合とほぼ同じ速さです。(古いバージョンを使用している場合は、FastMM と FastCode をインストールすると、これらの操作を高速化できる場合があります。)

必要に応じて、他に実行できることは、遅延初期化です。一度に 500 万個の配列すべてを割り当てようとする代わりに、SetLength(a, 5000000);最初は単に割り当てます。次に、「分岐」に到達する必要がある場合は、まずその長さ = 0 かどうかを確認します。そうであれば、初期化されていないため、適切な長さに初期化します。これは全体的に時間を節約するわけではなく、実際には全体的に少し長くかかりますが、初期化時間が分散されるため、ユーザーは気づきません。

初期化がすでに可能な限り高速であり、ここで遅延初期化を使用できないような状況になっている場合は、基本的に運が悪いです。これは、大量のデータを処理する代償です。

于 2011-03-29T17:35:41.683 に答える
2

の定数を使用して正確なコードをテストし、基本的なタイミングDiff_Valuesを使用して時間を計りました。GetTickCount()の場合Diff_Valuesは1861466 ミリ秒かかり、の場合Diff_Valuesは187で失敗しOut of Memoryます。Out of Memoryつまり、そうではOut of Address SpaceありませんOut of Memory。

私の意見では、RAM を使い果たし、Windows がページングを開始するほど多くのデータを割り当てているため、遅いのです。私のシステムには、プロセスが必要なだけ割り当てるのに十分な RAM があります。そして、失敗するまでそうします。

可能な解決策

  • 明白なこと: あまり割り当てないでください!
  • すべてのデータを 1 つの連続したメモリ ブロックに割り当てる方法を考え出す: アドレス空間の断片化に役立ちます。「ブランチ」に固定サイズの 2 次元配列が割り当てられる方法と同様ですが、「ブランチ」のサイズが異なる場合は、データに基づいて別の数式を計算する必要があります。
  • 他のデータ構造、おそらくディスクにキャッシュするものを調べます (2Gb アドレス空間の制限にブレーキをかけるため)。
于 2011-03-29T17:54:19.947 に答える
2

メイソンのポイントに加えて、考慮すべきアイデアがいくつかあります。

ブランチが割り当てられた後にブランチの長さが決して変わらず、すべてのブランチにわたって配列に格納されるアイテムの総数に上限がある場合、1 つの巨大なメモリ チャンクを割り当てることで時間を節約できる可能性があります。そして、そのチャンク内の「ブランチ」を自分で分割します。配列はポインターの 1 次元配列になり、その配列の各エントリはそのブランチのデータの開始点を指します。単一のポインター変数を使用して、大きなブロックで使用されているスペースの「最後」を追跡し、新しい「ブランチ」用にスペースを予約する必要がある場合は、現在の「終了」ポインター値を新しいブランチの開始として取得します。分岐し、分岐に必要なスペースの量だけ「終了」ポインターをインクリメントします。ドン'

この手法では、より多くのポインターを使用する必要がありますが、すべてのヒープ割り当てオーバーヘッドを排除するか、少なくとも汎用ヒープ割り当てを、特定の使用パターンに一致する専用の非常にシンプルで非常に高速なサブアロケーターに置き換える可能性があります。実行は速くなるはずですが、書き込みとテストにより多くの時間が必要になります。

この手法は、ヒープの断片化も回避し、すべてのメモリの解放を 1 回の割り当て解除に減らします (現在のモデルでは何百万もの個別の割り当てではなく)。

考慮すべきもう1つのヒント：新しく割り当てられた配列「ブランチ」ごとに常に最初に行うことが、すべてのスロットにデータを割り当てることである場合、メイソンの例のステップ3を削除できます-すべての場合、メモリをゼロにする必要はありませんあなたがやろうとしているのは、すぐに実際のデータをそれに割り当てることです。これにより、メモリの書き込み操作が半分に削減されます。

于 2011-03-29T18:04:27.560 に答える
1

データ構造全体を連続したメモリ ブロックに収めることができると仮定すると、一度に割り当てを行ってから、インデックス作成を引き継ぐことができます。

注: データを 1 つの連続したメモリ ブロックに収めることができない場合でも、複数の大きなブロックを割り当ててそれらをつなぎ合わせることで、この手法を使用できます。

colIndexまず、各行の最初の列のインデックスを含むヘルパー配列 を形成します。の長さを に設定colIndexしRowCount+1ます。colIndex[0] := 0これを設定してから構築しますcolIndex[i+1] := colIndex[i] + ColCount[i]。まで実行される for ループでこれを行いますRowCount。したがって、最後のエントリ にはcolIndex[RowCount]、要素の総数を格納します。

a の長さを に設定しますcolIndex[RowCount]。これには少し時間がかかる場合がありますが、以前に行っていた作業よりも速くなります。

ここで、いくつかのインデクサーを作成する必要があります。それらをクラスまたはレコードに入れます。

ゲッターは次のようになります。

 function GetItem(row, col: Integer): Word;
 begin
   Result := a[colIndex[row]+col];
 end;

セッターは明らかです。これらのアクセス方法をインライン化して、パフォーマンスを向上させることができます。オブジェクトのクライアントに便利なように、それらをインデックス付きプロパティとして公開します。

と の有効性をチェックするコードを追加する必要がrowありcolます。colIndex後者に使用する必要があります。{$IFOPT R+}ネイティブ インデックス作成の範囲チェックを模倣する場合は、このチェックをオプションにすることができます。

もちろん、最初のインスタンス化後に列数のいずれかを変更したい場合、これはまったく問題ありません。

于 2011-03-29T17:45:10.180 に答える