3

オブジェクトのリストがさまざまな基準を使用して頻繁にフィルタリングされる Delphi アプリケーションの一部を最適化しています。オブジェクトはTObjectList構造に保持され、各フィルターでセット全体のごく一部 (例: 1%) を選択するのが一般的です。オブジェクトの総数は 100k の範囲になる可能性があり、計算中にメイン セットは変更されません。フィルターはいくつかのプロパティにのみ適用されますが、すべての可能な基準を最適化するような方法でリストを並べ替えることができません。

オブジェクト (データ構造) を整理する方法、またはこの問題に対処するために使用できるアルゴリズムについての提案を探しています。ありがとうございました！

フィルタの例:

  ((Object.A between 5 and 15) AND
  (Object.B < 20) AND
  (Object.C(AParam) > 0)) OR
  (Object.IsRoot(...))
4

6 に答える 6

4

フィールドを使用してソートされたリストを使用できます。これにより、検索/フィルタリングが最大限に制限され、バイナリ検索を実行してこの基準のインデックスを取得できます。

上記の例を参照してください: ソートされたリストを生成し、とAのインデックスを検索すると、(はるかに) 小さいリスト (2 つの間のすべてのインデックス) が得られ、他のフィールド ( 、、)を確認する必要があります。 .515BCIsRoot

ソート済みリストの Delphi (2009+) 実装: DeHL.Collections.SortedList

于 2010-02-27T15:07:11.550 に答える
3

tiOPFを使用していないことは知っていますが、このプロジェクトのソースコードから学ぶことはたくさんあります。おそらくフィルター処理されたオブジェクトをループするので、フィルターイテレーターを作成してみませんか？

このユニットは良いスタートですが、完全なソースをダウンロードしてファイルを参照する方が簡単だと思います：http: //tiopf.svn.sourceforge.net/viewvc/tiopf/tiOPF2/Trunk/Core/tiFilteredObjectList.pas？リビジョン=1469＆view = markup

このソリューションは、おそらく多くのRTTIを使用します。フィルター（プロパティ名と値）を使用してリストを作成し、オブジェクトをループするだけです。それはあなたに最大の柔軟性を提供しますが、いくらかの速度を犠牲にします。スピードが必要な場合は、Ulrichbが提供するソリューションの方が優れていると思います。

于 2010-02-27T15:17:32.013 に答える
2

アイデア＃1

プロファイラーでコードを実行します。遅いスポットがないか調べます。

アイデア＃2

オブジェクトをメモリに順番に格納することで、キャッシュ効果を利用できる可能性があります。（リストを最初から最後まで順番に歩いていると仮定しています。）

これを行う 1 つの方法は、オブジェクトのリストの代わりにレコードの配列を使用することです。あなたのケースでそれが可能であれば。Delphi 2006 のレコードにはメソッドを含めることができますが、仮想メソッドを含めることはできません。

もう 1 つのアイデアは、独自のクラス アロケータを作成することです。私はそれを試したことはありませんが、ここに私が見つけた記事があります。TObjectList を使用する代わりに、ポインターを使用してオブジェクトをウォークしてみてください。

于 2010-02-27T16:18:32.467 に答える
1

オブジェクトの量が少ない場合、検索の効率はあまり重要ではありませんが、結果を頻繁にキャッシュすると役立つ場合があります。

オブジェクトの量が多い場合は、インメモリ データベースを使用し、SQL を使用してクエリを実行することを検討します。その後、データベースはインデックスを使用して可能な限り高速に検索できるようになり、その負担を実証済みのツールに任せることができます。個人的には DBISAM または ElevateDB を使用していますが、他の人もインメモリ データベースを使用します。実際のデータベース ツールを使用すると、データが非常に大きくなった場合に、データを簡単にディスクに移動できます。

于 2010-02-27T16:45:35.913 に答える
1

これは、一般的な方法で解決するのが非常に非常に難しい問題です。これを 1 日中実行する 1 種類のソフトウェアがあり、それはSQL クエリ オプティマイザと呼ばれます。最新のすべての SQL エンジンに存在するコードのビットは、必要なもの (クエリ) を調べてから、インデックスを調べます。データの利用可能性、利用可能なインデックスの選択性、および結果セットを得るためにそれらすべてを使用する最適な方法を見つけ出す必要があります。問題が非常に難しいことを証明するために、SQL クエリ オプティマイザは時々失敗し、目に見えて非効率的な計画を作成します。

本格的なクエリ オプティマイザーを実装したくないと思うので、クエリを十分に高速化するためのヒントをいくつか紹介します。

(1) クエリで頻繁に使用されるいくつかのフィールドを選択し、それらにインデックスを設定します。これらのフィールドは、優れた選択性を提供する必要があります。「ブール値」でインデックスを作成しないでください。リスト全体を同じくらい速く (またはより速く) 見たとしても、複雑な二分探索構造をトラバースするのに時間がかかるだけです!

(2) 特定のクエリごとに、1 つの単一インデックスを選択してデータを事前にフィルター処理し、他のすべてのフィルターを 1 つずつ (最適化なしで) 適用します。

あなたの例では：「A」および「B」フィールドにインデックスを作成します。「C」は関数のように見えるため、インデックスを作成できません。「IsRoot」はブール値を返すようですが、インデックスを作成する価値はありません。

データに使用するデータ構造は、データに完全に依存します。パフォーマンスが重要な場合は、いくつか実装してテストを行います。重要でない場合は、お気に入りのリストの並べ替えアルゴリズムだけで完了です!

于 2010-02-28T09:57:48.650 に答える
1

フィルタリングする属性の数が少なく、それらを並べ替えることができる場合、それぞれが別の属性によって並べ替えられている場合は、複数のリストを作成しないでください。リストごとに、オブジェクトごとに参照用に 4 バイトのコストと、リスト自体のわずかなオーバーヘッドがかかります。もちろん、すべてはメモリ要件を満たすことができるかどうかにかかっています。多くのオブジェクトを扱っている場合、2 GB はそれほど多くありません...

于 2010-02-27T19:26:36.380 に答える