10

私には選択肢があります。

保存してアクセスする必要がある、既に注文された文字列が多数あります。以下を使用して選択できるようです：

  1. TStringList

  2. 文字列の動的配列、および

  3. 文字列のリンク リスト (単方向リンク)

    アランはコメントで、私も選択肢に追加することを提案しました。

  4. TList<string>

これらのそれぞれが他のものよりも優れているのはどのような状況ですか?

小さなリスト (10 項目未満) に最適なのはどれですか?

大規模なリスト (1000 項目以上) に最適なのはどれですか?

巨大なリスト (1,000,000 アイテム以上) に最適なのはどれですか?

メモリ使用量を最小限に抑えるにはどれが最適ですか?

最後に余分なアイテムを追加するために読み込み時間を最小限に抑えるのに最適なのはどれですか?

最初から最後までリスト全体にアクセスするためのアクセス時間を最小限に抑えるには、どれが最適ですか?

これに基づいて（または他のものに基づいて）、どのデータ構造が望ましいでしょうか?

参考までに、私は Delphi 2009 を使用しています。

コメントでディミトリーは次のように述べています。

タスクとデータ アクセス パターンを説明すると、正確な回答を得ることができます

わかった。大量のデータを含む家系図プログラムがあります。

人ごとに、いくつかのイベントと属性があります。私はそれらを短いテキスト文字列として保存していますが、0 から数百までの範囲で、1 人あたり多数あります。そして、私は何千人もの人々を持っています。それらへのランダムアクセスは必要ありません。各人物に関連付けられた既知の順序で多数の文字列として関連付けられている必要があるだけです。これは、何千もの「小さなリスト」の私の場合です。それらはロードしてメモリを使用するのに時間がかかり、すべてが必要な場合 (たとえば、生成されたレポート全体をエクスポートするなど) にアクセスするのに時間がかかります。

次に、数十万の名前を持つことができる「仮想」ツリービューのセクションのすべての名前など、いくつかの大きなリストがあります。ここでも、インデックスでアクセスできるリストのみが必要です。これらは効率のためにツリービューとは別に保存され、ツリービューは必要な場合にのみそれらを取得します。これは読み込みに時間がかかり、私のプログラムにとってはメモリに関して非常にコストがかかります。しかし、一度にアクセスされるのはごくわずかなので、アクセス時間を気にする必要はありません。

うまくいけば、これで私が達成しようとしていることのアイデアが得られます。

ps Delphi の最適化に関する多くの質問を StackOverflow に投稿しました。私のプログラムは 100,000 人の 25 MB のファイルを読み取り、8 秒でデータ構造、レポート、およびツリービューを作成しますが、そのために 175 MB の RAM を使用します。32 ビット Windows で数百万人のファイルをロードすることを目指しているため、これを削減するために取り組んでいます。

この StackOverflow の質問で、TList を最適化するためのいくつかの優れた提案を見つけました。 より高速な TList 実装はありますか?

4

7 に答える 7

10

多くのコンポーネントが直接使用できるインターフェイスをTStringList提供するため、特別なニーズがない限り、aに勝るものはありません。TStringsではTStringList.Sorted := True、バイナリ検索が使用されます。つまり、検索が非常に高速になります。オブジェクト マッピングも無料で取得できます。各項目をポインターに関連付けることもでき、マーシャリング、ストリーム インターフェイス、カンマ テキスト、区切りテキストなどの既存のメソッドをすべて取得できます。

一方、特別なニーズのために、多くの挿入と削除を行う必要がある場合は、よりリンクされたリストに近いものが良いでしょう. しかしその後、検索が遅くなり、実際には検索を必要としない文字列のまれなコレクションになります。このような状況では、ハッシュが文字列の最初の 2 バイトなどから作成される場合に、ある種のハッシュがよく使用されます (長さ 65536 の配列を事前に割り当て、文字列の最初の 2 バイトが直接ハッシュに変換されます)。その範囲内のインデックス)、次にそのハッシュ位置に、文字列内の残りのバイトで構成される各アイテム キーと共にリンク リストが格納されます (スペースを節約するため --- ハッシュ インデックスには最初の 2 バイトが既に含まれています)。次に、最初のハッシュ ルックアップは O(1) であり、その後の挿入と削除はリンク リスト高速です。

于 2010-04-21T06:42:52.897 に答える
6

  1. TStringList。長所: 機能が拡張されており、動的に拡大、並べ替え、保存、ロード、検索などを行うことができます。短所: インデックスによるアイテムへの大量のアクセスでは、Strings[Index] によりかなりのパフォーマンスが失われます (数パーセント)。配列にアクセスするには、アイテムセルごとにメモリオーバーヘッドが発生します。

  2. 文字列の動的配列。長所: TStrings として動的に拡張する機能と、インデックスによる最速のアクセス、他からの最小限のメモリ使用量を組み合わせます。短所: 標準の「文字列リスト」機能が制限されています。

  3. 文字列のリンク リスト (単独でリンク)。長所: リストの最後に項目を追加する直線的な速度。短所: インデックスと検索によるアクセスが最も遅い、制限された標準の「文字列リスト」機能、「次の項目」ポインターのメモリ オーバーヘッド、各項目のメモリ割り当ての速度オーバーヘッド。

  4. TList< 文字列 >. 上記のように。

  5. TStringBuilder. TStringBuilder を複数の文字列のストレージとして使用する方法がわかりません。

実際には、もっと多くのアプローチがあります。

  • 動的配列の連結リスト
  • ハッシュ テーブル
  • データベース
  • 二分木
  • 等

最適なアプローチはタスクによって異なります。

小さなリスト (10 項目未満) に最適なのはどれですか?

誰でも、合計アイテム数変数を持つ静的配列でさえあるかもしれません。

大規模なリスト (1000 項目以上) に最適なのはどれですか? 巨大なリスト (1,000,000 アイテム以上) に最適なのはどれですか?

大きなリストの場合は、次を選択します: - 動的配列、インデックスによるアクセスまたは特定のアイテムの検索が必要な場合 - ハッシュ テーブル、キーで検索する必要がある場合 - 動的配列のリンク リスト (多くのアイテムが必要な場合)追加し、インデックスによるアクセスなし

メモリ使用量を最小限に抑えるにはどれが最適ですか?

動的配列はより少ないメモリを消費します。しかし、問題はオーバーヘッドについてではなく、このオーバーヘッドが適切になるアイテムの数についてです。そして、この数のアイテムを適切に処理する方法。

最後に余分なアイテムを追加するために読み込み時間を最小限に抑えるのに最適なのはどれですか?

動的配列は動的に拡大する可能性がありますが、非常に多数のアイテムでは、メモリ マネージャーが連続したメモリ領域を見つけられない場合があります。リンクされたリストは、少なくともセルのメモリが存在するまで機能しますが、各アイテムのメモリ割り当てのコストがかかります。混合アプローチ - 動的配列のリンクされたリストが機能するはずです。

最初から最後までリスト全体にアクセスするためのアクセス時間を最小限に抑えるには、どれが最適ですか?

動的配列。

これに基づいて（または他のものに基づいて）、どのデータ構造が望ましいでしょうか?

どのタスクの ?

于 2010-04-21T06:54:58.720 に答える
2

あなたが述べた目標が、何百万人もの人が含まれる系図ファイルをロードできるようにプログラムを改善することである場合、質問の4つのデータ構造のどちらかを決定しても実際にはそこに到達しません。

計算してください。現在、約100000人が含まれる25 MBのファイルをロードしているため、アプリケーションは175MBのメモリを消費します。数百万人が含まれるファイルをロードしたい場合は、プログラムに大幅な変更を加えることなく、メモリの必要量を増やす必要があると見積もることができますn * 10。現在のようにすべてをメモリに保持しながら、32ビットプロセスでこれを行う方法はありません。

基本的に2つのオプションがあります。

  1. すべてを一度にメモリに保持するのではなく、データベース、または必要なときにデータをロードするファイルベースのソリューションを使用します。これについてはすでに他の質問があったことを覚えていますが、おそらく反対することにしたので、そのままにしておきます。

  2. すべてをメモリに保存しますが、可能な限りスペース効率の高い方法で保存します。64ビットのDelphiがない限り、各人のデータ量に応じて、数百万人が許可されます。これを64ビット用に再コンパイルすると、その制限もなくなります。

2番目のオプションを選択する場合は、メモリ消費をはるかに積極的に最小化する必要があります。

  • 文字列インターニングを使用します。同じデータを含むが異なる文字列に含まれるプログラムにロードされたすべてのデータ要素は、基本的に無駄なメモリです。あなたのプログラムはエディタではなくビューアであると理解しているので、インターンされた文字列のプールに文字列を追加するだけでおそらく逃げることができます。何百万もの文字列で文字列インターンを行うことはまだ困難です。SmartInspectブログの「文字列プールを使用したメモリ消費の最適化」ブログ投稿は、いくつかの良いアイデアを提供する可能性があります。これらの人は定期的に巨大なデータファイルを処理し、あなたが直面しているのと同じ制約でそれを機能させる必要がありました。
    これはまた、この答えをあなたの質問に結び付けるはずです-文字列インターンを使用する場合、データ構造に文字列のリストを保持する必要はありませんが、文字列プールインデックスのリストを保持する必要があります。
    名前用に1つなど、複数の文字列プールを使用することも有益な場合がありますが、都市や国などの場所には別の文字列プールを使用します。これにより、プールへの挿入が高速化されます。

  • メモリ内の表現が最小になる文字列エンコーディングを使用します。すべてをネイティブのWindowsUnicode文字列として格納すると、UTF-8エンコーディングで3バイト以上を必要とする文字を主に含む文字列を定期的に処理しない限り、UTF-8に文字列を格納するよりもはるかに多くのスペースを消費する可能性があります。
    文字セットの変換が必要なため、プログラムは文字列を表示するためにより多くのCPUサイクルを必要としますが、その量のデータでは、メモリアクセスがボトルネックになり、データサイズを小さくするとメモリアクセスの負荷を減らすことができるため、トレードオフに値します。

于 2010-04-22T07:20:59.713 に答える
1

あなたの説明から、それがあなたのデザインに適合するかどうかは完全にはわかりませんが、パフォーマンスを大幅に低下させることなくメモリ使用量を改善できる方法の 1 つは、trieを使用することです。

二分探索木と比較した利点

二分探索木 (BST) に対する試行の主な利点は次のとおりです。

  • キーを検索する方が高速です。長さ m のキーを検索すると、最悪の場合 O(m) の時間がかかります。BST はキーの O(log(n)) 比較を実行します。ここで、n はツリー内の要素の数です。ルックアップはツリーの深さに依存するためです。これは、ツリーのバランスが取れている場合、キーの数が対数になるためです。したがって、最悪の場合、BST には O(m log n) の時間がかかります。また、最悪の場合、log(n)はmに近づきます。また、文字を使用した配列インデックスなど、ルックアップ中に使用しようとする単純な操作は、実際のマシンでは高速です。

  • キーが明示的に格納されず、共通の初期サブシーケンスを持つキー間でノードが共有されるため、試行に多数の短い文字列が含まれている場合、必要なスペースが少なくなる可能性があります。

  • 試行は、最長の接頭辞の一致を容易にし、すべての一意の文字の可能な限り長い接頭辞を共有するキーを見つけるのに役立ちます。
于 2010-04-22T14:13:15.680 に答える
1

1 つの質問: どのようにクエリを実行しますか? リスト内の ID または位置に対して文字列またはクエリを一致させますか?

小さな # 文字列に最適:

プログラムを理解しやすくするものは何でも。プログラムの可読性は非常に重要であり、速度のためにアプリケーションの実際のホットスポットでのみ犠牲にする必要があります。

メモリ (それが最大の制約である場合) と読み込み時間に最適:

すべての文字列を 1 つのメモリ バッファー (またはメモリ マップ ファイル) に保持し、文字列 (またはオフセット) へのポインターのみを保持します。文字列が必要なときはいつでも、2 つのポインタを使用して文字列を切り取り、それを Delphi 文字列として返すことができます。このようにして、文字列構造自体 (refcount、length int、codepage int、および各文字列割り当てのメモリ マネージャー構造) のオーバーヘッドを回避します。

これは、文字列が静的で変更されない場合にのみ正常に機能します。

TList、TList<>、文字列の配列、および上記のソリューションには、文字列ごとに 1 つのポインターの「リスト」オーバーヘッドがあります。連結リストには、少なくとも 2 つのポインター (単一連結リスト) または 3 つのポインター (二重連結リスト) のオーバーヘッドがあります。リンク リスト ソリューションには高速なランダム アクセスはありませんが、他のオプションが O(lgN) (サイズ変更の係数を使用) または固定サイズ変更を使用して O(N) を持つ場合、O(1) のサイズ変更が可能です。

私がすること：

項目数が 1000 未満で、パフォーマンスがそれほど重要でない場合: TStringList または dyn 配列を最も簡単に使用できます。それ以外の場合は静的: 上記のトリックを使用します。これにより、O(lgN) クエリ時間、最小使用メモリ、および非常に高速なロード時間が得られます (ただ飲み込むか、メモリ マップ ファイルを使用するだけです)。

コードで動的に変更する必要がある大量のデータ 1M + 文字列を使用すると、質問で言及されているすべての構造が失敗します。そのとき、作成する必要があるクエリの種類に応じて、残高バイナリ ツリーまたはハッシュ テーブルを使用します。

于 2010-04-21T06:46:41.350 に答える
1

TStringList(string, TObject) レコードへのポインタの配列を格納します。

TListポインターの配列を格納します。

TStringBuilder文字列のコレクションを格納できません。これは .NET の StringBuilder に似ており、(多数の) 文字列を連結するためにのみ使用する必要があります。

動的配列のサイズ変更は遅いため、オプションとは考えないでください。

すべてのシナリオでDelphi のジェネリックを使用TList<string>します。文字列の配列を格納します (文字列ポインタではありません)。(アン) ボックス化がないため、すべてのケースでより高速にアクセスできるはずです。

順次アクセスのみが必要な場合は、わずかに優れたリンク リスト ソリューションを見つけたり、実装したりできる場合があります。Delphi アルゴリズムとデータ構造を参照してください。

Delphi はそのTListとを促進しTList<>ます。内部配列の実装は高度に最適化されており、使用時にパフォーマンスやメモリの問題を経験したことはありません。TList と TStringList の効率性を参照してください

于 2010-04-21T06:33:00.607 に答える
1

可能な代替:

私は最近、文字列インデックスを使用して大量のデータを格納するための TSynBigTableString クラスを持つSynBigTable ( http://blog.synopse.info/post/2010/03/16/Synopse-Big-Table ) を発見しました。

非常にシンプルな単一レイヤーの Bigtable 実装であり、主にディスク ストレージを使用するため、数十万件のレコードを保存するときに予想よりもはるかに少ないメモリを消費します。

単純な：

aId := UTF8String(Format('%s.%s', [名前、姓]));

bigtable.Add(データ、aId)

と

bigtable.Get(aId, データ)

1 つの問題として、インデックスは一意である必要があり、更新のコストが少し高くなります (最初に削除してから再挿入する必要があります)。

于 2010-06-11T07:57:27.603 に答える