6

約200,000行のテキストファイルがあります。各行は、複数のプロパティを持つオブジェクトを表します。オブジェクトのプロパティの1つ（一意のID）のみを検索します。探している一意のIDが現在のオブジェクトの一意のIDと同じである場合は、オブジェクトの残りの値を読み取ります。

現在、オブジェクトを検索するたびに、テキストファイル全体を1行ずつ読み取り、各行にオブジェクトを作成して、それが探しているオブジェクトであるかどうかを確認します。これは、基本的に最も非効率的な方法です。探す。これらすべてのオブジェクトをメモリに読み込んで、後でより効率的に検索できるようにしたいと思います。

問題は、そのような検索を実行するための最も効率的な方法は何ですか？200,000エントリのNSArrayはこれを行うための良い方法ですか（私はそれを疑っています）？NSSetはどうですか？NSSetを使用して、オブジェクトの1つのプロパティのみを検索することは可能ですか？

助けてくれてありがとう！

--Ry

4

3 に答える 3

13

@yngvedhは、NSDictionary（マップ構造で予想されるように）ルックアップ時間がO（1）であるという点で正しいです。NSSetただし、いくつかのテストを行った後、 O（1）ルックアップ時間もあることがわかります。これが私がそれを思い付くために行った基本的なテストです：http： //pastie.org/933070

基本的に、私は1,000,000の文字列を作成し、辞書とセットの両方から100,000のランダムな文字列を取得するのにかかる時間を計ります。これを数回実行すると、セットは実際には高速に見えます...

dict lookup: 0.174897
set lookup: 0.166058
---------------------
dict lookup: 0.171486
set lookup: 0.165325
---------------------
dict lookup: 0.170934
set lookup: 0.164638
---------------------
dict lookup: 0.172619
set lookup: 0.172966

あなたの特定のケースでは、これらのどちらかがあなたが望むものになるかどうかはわかりません。これらのオブジェクトをすべてメモリに保存したいとおっしゃっていますが、本当にすべてが必要ですか、それともいくつかだけ必要ですか？後者の場合は、おそらくファイルを読み取り、オブジェクトIDからファイルへのオフセットマッピングを作成します（つまり、各オブジェクトIDがファイル内のどこにあるかを覚えておいてください）。次に、必要なものを検索し、ファイルオフセットを使用してファイル内の適切な場所にジャンプし、その行を解析して次に進みます。これはの仕事ですNSFileHandle。

于 2010-04-24T16:53:55.657 に答える
5

NSDictionaryを使用して、IDからオブジェクトにマップします。つまり、IDをキーとして使用し、オブジェクトを値として使用します。NSDictionaryは、効率的なキールックアップをサポートする唯一のコレクションクラスです。（またはキールックアップ）

辞書は、他のコレクションクラスとは異なる種類のコレクションです。これは連想コレクション（あなたの場合はIDをオブジェクトにマップします）ですが、他のコレクションは単に複数のオブジェクトのコンテナーです。NSSetは順序付けされていない一意のオブジェクトを保持し、NSArrayは順序付けられたオブジェクトを保持します（重複を保持する場合があります）。

アップデート：

エントリを読み取るときに再割り当てを回避するには、このdictionaryWithCapacity:メソッドを使用します。エントリを読む前に（おおよその）エントリ数がわかっている場合は、それを使用して、十分な大きさの辞書を事前に割り当てることができます。

于 2010-04-24T10:36:02.867 に答える
4

200,000個のオブジェクトは、オブジェクトのサイズとターゲット環境によっては、メモリの制約に遭遇する可能性があるように聞こえます。検討したいもう1つのことは、データをSQLiteデータベースに変換してから、ルックアップする列にインデックスを付けることです。これにより、フルセットをメモリにロードする必要がなくなるため、効率とリソース消費の間で適切な妥協点が得られます。

于 2010-04-24T16:58:01.607 に答える