私は、より珍しいデータ構造の使用を必要とするかもしれない問題に遭遇しましたが、わかりません。URIホスト名を格納するコンテナ
基本的には、URIホスト名をコンテナに格納し、そのコンテナにホスト名が存在するかどうかを問い合わせることができます。ただし、コンテナに特定のホスト名の上位レベルのドメインが含まれている場合は、下位レベルのドメインを検索するとクエリにはtrue
が返されます。つまり、コンテナにexample.com
が含まれている場合は、www.example.com
を検索できるようにしたいので、true
を返します。または、コンテナにfoo.example.com
が含まれている場合は、bar.foo.example.com
を参照できるようにしたいので、trueを返します。
私はこの問題について考えてきましたが、これを行うには簡単な方法はありません。明白な解決策は、ハッシュテーブルやツリー(C++でstd::unordered_set
またはstd::set
)のような通常の連想コンテナを使用することです。検索時には、ドメイン名の各セグメントを繰り返し処理し、コンテナにクエリを送信して各セグメントが含まれているかどうかを確認する必要があります。したがって、www.example.com
を検索する必要がある場合は、com
の1つ、example.com
の1つ、www.example.com
の1つの3つのクエリを実行する必要があります。私が肯定を得るとすぐに、私はtrue
を返すか、そうでなければfalseを返します。
この解決方法は問題ありませんが、おそらくこれで解決します。ただし、ホスト名の長さに応じてN個のクエリを作成する必要があるため、正しいとは限りません。ホスト名は通常、、つまり個のセグメントを持っていないので、私は実際にパフォーマンスについて心配していません。しかし、私はです。は、他の人がすでに考えていた問題のように思えるので、私はここでよりスマートにすべきだと心配しました。
Patrica Trieや他のタイプのプレフィックス対応コンテナのような、よりエキゾチックなデータ構造を使用すると考えました。私はこの構造を実装する素敵なライブラリを持っているので、それを使うのは問題ではありません。しかし、問題を考えた後、私はパトリシア・トライが助けてくれるとは思わない。試行は、キーが接頭辞で、値が完全長の文字列である場合に設計されています。私の場合、のキーは、しばしばコンテナ内のどの値よりも長くなります。言い換えれば、私の鍵はwww.example.com
であり、コンテナにexample.com
があれば、example.com
を見つけることができます。しかし、Patricia Triesは逆の仕事をしています。
ここでは、定期的な連想型コンテナが最適な方法ですか?それとも、他に何か提案がありますか?
私はそれが動作するかどうかは分かりません。 Patricia Triesは接頭辞を探すために設計されています。したがって、トライに 'com.example.www'が含まれていて、' com.example'を検索したいのであればうまく動作します。しかし、実際には、私は*反対*をしたいです。トライに 'com.example'が含まれていれば、' com.example.www'というキーを使用してそれを見つけることができます。これは 'com.example'の接頭辞ではありません。 – Channel72
@ Channel72:あなた自身の検索機能を使っているなら、 'com.example'が最終的なもの(正しい単語ならば)であり、' com.example 'の接頭辞であると判断できるはずです。 www'。 – Hasturkun
@ Channel72:実際には、検索が 'com.example'で終わると、' com.example.www'はそのサフィックスです。これは成功と見なされます。 – Hasturkun