1

私はC++でアドレス帳を実装することを考えていました。モバイルアプリケーション用に開発されているため、名簿はできるだけ少ないメモリを使用する必要があります。また、ユーザーは名前で連絡先をすばやく検索または並べ替えることができます(私が知っているパラドックス)。

少し調べてみると、ほとんどの人が、Trieが私のニーズに合った最良のデータ構造であると示唆していることがわかりました。より正確には、基数木(Patricia Trie)。このデータ構造を使用すると、オートコンプリートの実装にも最適です。

他に実行可能な解決策はありますか、それともこのアイデアを使用してコーディングを開始しても大丈夫ですか?

4

2 に答える 2

1

小さなコレクションの試行には注意してください。それらは適切な漸近的な動作を提供しますが、時間と空間の両方で隠れた定数が大きすぎる可能性があります。

特に、試行はキャッシュのパフォーマンスが低下する傾向があり、小さなコレクションの主な懸念事項となるはずです。

データが比較的小さい [10,000 エントリ未満] であると仮定すると、 はstd::vector優れたキャッシュ パフォーマンスを提供できます。これは、サイズ ファクターよりもはるかに大きな影響を与える可能性があります。そのため、検索時間でさえ、trie または std::set よりも漸近的に長くなります。実際には、優れたキャッシュ動作のおかげで、両方よりも優れている可能性があります。

二分探索vectorを使用してソート済みを維持することもできる場合、対数探索時間と優れたキャッシュ動作の両方から恩恵を受けることができます。

(*)この回答は、アプリがデプロイされるハードウェアにCPU-Cacheがあることを前提としています。

于 2012-04-07T22:18:22.197 に答える
0

試行は、迅速な検索、挿入、および削除を提供するため、このような目的に最適です。

于 2012-04-07T22:11:55.593 に答える