妥当なサイズが 1 ～ 50K の範囲のオブジェクトのコレクションを扱っています (ただし、上限は設定されていません)。各オブジェクトには、いくつかの文字列が含まれています。
これらの文字列のいずれかに部分的、完全、または RegEx と一致し、その後オブジェクトのリストを返すことができる検索関数を実装したいと考えています。
各オブジェクトに含まれる文字列が 1 つだけの場合、単純にそれらを辞書順に並べ替えて、範囲をかなり簡単に引き出すことができますがmap、速度/メモリの問題から、含まれる各文字列に対して - のような構造を実装することには消極的です。
速度とメモリ効率のために、この種の操作に適したデータ構造はありますか? データベースの可能性を感じていますが、私はそれらについてほとんど知らないので、より知識のある誰かが私を正しい方向に向かわせてくれるまで、研究を延期したいと思います!
すべての返信に感謝しますが、この投稿に記載されている手法に従って、ヘッダーのみのSeqAnプロジェクトの拡張サフィックス配列を使用することにしました。
マップのようなコレクションがおそらく最善の策です。キーは文字列になり、値はそれを含むオブジェクトへの参照になります。文字列が stl 文字列としてオブジェクト内に保持されている場合は、代わりにマップのキー部分にデータへの参照を格納できます (または、文字列に shared_ptr を使用し、オブジェクトとマップの両方でそれらを参照します)。
検索、並べ替えは、逆参照されたデータを使用するカスタム検索関数を実装するだけの問題になります。マップのサイズは、2 つの参照にマップのオーバーヘッドを加えたものになります。これは、代替案が大きくないにしても、同じくらい大きくなると考えると、それほど悪くはありません。
部分的、完全、または RegEx は、これらの文字列のいずれかに一致し、続いてオブジェクトのリストを返します
完全一致の場合、std::map<std::string, std::vector<object*> >. キーは正確な文字列であり、vector一致するオブジェクトへのポインターを保持します。これらのポインターの多くは、単一のオブジェクト インスタンスを指す場合があります。
部分的な文字列から完全な文字列へのフロントエンド マップを作成できます。文字列が "dogged" であるとします。悲しいことに、"dogged"、"ogged"、"gged"、"ged"、" のエントリを配置する必要があります。 ed" および "d" (最小一致サイズが必要な場合は、好きな場所で停止します)...次に、lower_bound を使用して検索します。そうすれば、「dog」で検索すると、「dogged」の一致があったことがわかります (代わりに「dogfood」と一致するかどうかは関係ありません。これは単純std::map<string, string>です。位置と文字列がまだ一致する場合 (つまり、dogfood から dogged まで ... で始まるまで)、「完全一致」マップでそれを検索し、結果を集計できます。
正規表現については、良い提案はありません...すべての完全な文字列を力ずくで検索することから始めます。本当に十分でない場合は、ブルート フォース マッチングを実行する前に、定数部分文字列をチェックしてフィルタリングするなど、大まかな最適化を行いますが、これを非常に徹底的かつ迅速に行う方法を想像することはできません。
object*(便利な場合は、お気に入りのスマート ポインターを s に置き換えてください)