4

文字列と整数の間の対応を維持し、文字列値を検索して整数を返す必要があります。次の要件を満たすこの情報を保存するのに最適な構造は何ですか?

  • 速度とメモリ サイズの順に重要です。

  • 車輪を再発明して、独自の並べ替えルーチンを作成したくありません。もちろん、Sort(CompareFunction) への呼び出しは問題ありません。

条件：

  • 整数が連続しているとは限りません。また、0 や 1 のような「開始値」もありません。

  • データ ペアの数は 100 から 100000 まで変化します

  • データは最初にすべて読み込まれ、その後の追加/削除/変更はありません

  • FWIW 文字列は、Outlook (MAPI?) がエントリを識別するために使用する 16 進数のエントリ ID です。例: 00000000FE42AA0A18C71A10E8850B651C2400000300000004000000000000018000000000000001E7FDF4152B0E944BA66DFBF2C6A6416E4F52000487F22

非常に多くのオプション (TStringList (オブジェクトまたは名前と値のペア)、TObjectList、TDictionary など) があるので、最初にアドバイスを求めたほうがよいでしょう...

Delphi TStringList で名前と値のペアをより速く検索するにはどうすればよいですか? を読みました。文字列/文字列ペアの TDictionary を提案し、Delphi 2007 の多次元配列の並べ替えを提案します。これは、文字列/整数の TStringlist オブジェクトを提案しますが、ソートは整数で行われます。

4

2 に答える 2

7

質問に含めた 2 番目のリンクは該当しません。これは、効率的な検索ではなく、並べ替えに関する質問です。質問でソートについて何度も説明していますが、ソートする必要はありません。あなたの要件は、連想配列とも呼ばれる単なる辞書です。もちろん、配列を並べ替えて検索に二分探索を使用することで実装できますが、並べ替えは必須ではありません。効率的な辞書が必要なだけです。

すぐに使用できる、問題に対する最も効率的で便利なデータ構造は ですTDictionary<string, Integer>。これには O(1) のルックアップの複雑さがあるため、大規模なコレクションに適しています。小規模なコレクションの場合、ルックアップの複雑さが O(log n) のバイナリ サーチ ベースのルックアップは競争力があり、実際にディクショナリよりも優れています。

Cosmin Prundは SO に関する優れた回答を書いており、ディクショナリ ルックアップとバイナリ サーチ ベースのルックアップのパフォーマンスを比較しました。一読することをお勧めします。小さなコンテナーの場合、パフォーマンスはおそらくそれほど大きな問題ではないと思います。したがって、二分探索の方が高速かもしれませんが、どちらの方法でもパフォーマンスが優れているため、おそらく問題にはなりません。しかし、大規模なコンテナではパフォーマンスが問題になる可能性があり、辞書は常に強力です。コンテナーが十分に大きい場合、バイナリ検索のパフォーマンスが許容範囲を超える可能性があります。

Embarcadero の実装よりも効率的な辞書の実装を作成できると確信していますが、Embarcadero の実装は完全に安定していると言えます。適切なハッシュ関数を使用しており、明らかな弱点はありません。

メモリの複雑さに関しては、ディクショナリと並べ替えられた配列のどちらを選択するかはほとんどありません。メモリ使用のためにソートされた配列を改善することはできません。

TDictionary<string, Integer>パフォーマンス要件が満たされていない場合にのみ、それ以上のものを検討することをお勧めします。

于 2013-04-22T16:54:36.493 に答える
0

均等に分散された長い文字列を検索しようとしているようです。この種の問題に対する最速のデータ構造の 1 つはTrieです。

ただし、データセットのサイズはかなり小さく、THashedStringList や TDictionary (より便利) などのすぐに使用できる Delphi ソリューションを使用すると、かなり高速になります。

于 2013-04-22T17:22:36.007 に答える