10

私は最近、以下の問題についてコーディングの質問をされました。私はこの問題に対するいくつかの解決策を持っていますが、それらが最も効率的であるかどうかはよくわかりません。

問題：

テキスト範囲のセットを追跡するプログラムを作成します。始点と終点は文字列になります。

Text range example : [AbA-Ef]
 Aa would fall before this range
 AB would fall inside this range
 etc.

文字列の比較は次のようになります'A'<'a' <'B' <'b' ...'Z' <'z'

この範囲で次の操作をサポートする必要があります

  • 範囲の追加-該当する場合、範囲をマージする必要があります
  • 範囲の削除-追跡された範囲から範囲を削除し、範囲を再計算します
  • クエリ範囲-文字を指定すると、関数は、追跡された範囲の一部であるかどうかを返す必要があります。

追跡される範囲は不連続になる可能性があることに注意してください。

私の解決策：

私は2つのアプローチを思いついた。

  1. 範囲を二重リンクリストとして保存するか、
  2. 範囲は、実際のデータを持つリーフノードを持つある種のバランスの取れたツリーとして格納され、リンクリストとして相互接続されます。

このソリューションは十分に優れていると思いますか、それともこれら3つのAPIが最高のパフォーマンスを発揮するようにこれを行うためのより良い方法を考えることができますか？

4

4 に答える 4

10

おそらくインターバルツリーを探しているでしょう。

カスタムコンパレータでデータ構造を使用して「範囲内」を示すと、必要な操作を効率的に実行できます。

インターバルツリーは、実際には 2 番目のアイデアを実装する効率的な方法です ( Store ranges as a some sort of balanced tree)

于 2012-10-04T06:32:53.070 に答える
1

「範囲の削除」操作が何をするのかはっきりしていません。それをしますか。

  • 以前に挿入された範囲を削除し、残りの範囲のマージを再計算しますか？

  • 削除された範囲の一部が追加された回数に関係なく、その範囲の追跡を停止します。

アルゴリズム的には大きな違いはありません。それはただの簿記です。しかし、明確にすることが重要です。また、範囲は閉じていますか、それとも半分開いていますか？（アルゴリズムには影響しないが、実装には影響する別の詳細）。

この問題への基本的なアプローチは、追跡されたセットを互いに素な（重複しない）範囲のソートされたリストにマージすることです。ベクトルまたは二分探索木として、あるいは基本的にO（log n）探索をサポートする任意の構造として。

1つのアプローチは、すべての互いに素な範囲の両方のエンドポイントをデータ構造に配置することです。ターゲット値が範囲内にあるかどうかを確認するには、ターゲットよりも大きい最小のエンドポイントのインデックスを見つけます。インデックスが奇数の場合、ターゲットはある範囲にあります。それも外にあることを意味します。

または、すべての互いに素な範囲を開始点でインデックス付けします。ターゲット以下の最大の始点を検索してターゲットを見つけ、ターゲットを関連する終点と比較します。

私は通常、ソートされたベクトルを使用する最初のアプローチを使用します。これは、（a）スペースの使用率が重要であり、（b）挿入とマージが比較的まれである場合に考えられます。二分探索木では、2番目のアプローチに進みます。ただし、詳細と定数のみが異なります。

マージと削除は難しくありませんが、厄介なケースがいくつかあります。挿入/削除する範囲の端点に対応する範囲を見つけることから始め（標準の検索操作を使用）、2つの間のすべての範囲を削除し、端点をいじって部分的に重複する範囲を修正します。検索操作は常にO（log n）ですが、ツリー/ベクトルの操作はo（n）です（とにかく、挿入/削除された範囲が大きい場合）。

于 2012-10-04T05:20:21.240 に答える
0

Java や C++ を含むほとんどの言語には、ある種の順序付きマップまたは順序付きセットがあり、値を検索して、値の後の次の値または値の前の最初の値を見つけることができます。これをビルディングブロックとして使用できます-ばらばらの範囲のセットが含まれている場合、範囲の最小要素、範囲の最大要素、範囲の最小要素、および範囲の最大要素が続きます。範囲など。範囲を追加すると、このプロパティが保持されているかどうかを確認できます。そうでない場合は、範囲をマージする必要があります。同様に、削除するときにこれを保持する必要があります。次に、クエリ ポイントの直前に最小の要素があり、直後に最大の要素があるかどうかを確認するだけで、クエリを実行できます。

独自のデータ構造を最初から作成したい場合は、何らかの基数トライ構造について考えます。これにより、文字列の比較を何度も繰り返す必要がなくなるからです。

于 2012-10-04T05:35:46.797 に答える
0

B +ツリーに行くと思います.2番目のアプローチとして言及したのと同じです。

B+ ツリーのいくつかのプロパティを次に示します。

  1. すべてのデータはリーフ ノードに格納されます。
  2. すべての葉は同じレベルにあります。
  3. すべてのリーフ ノードには、他のリーフ ノードへのリンクがあります。

以下に、いくつかのアプリケーション B+ ツリーを示します。

  1. ツリー内の要素を見つけるために必要な I/O 操作の数を減らします。
  2. 多くの場合、データベース インデックスの実装で使用されます。
  3. B+ ツリーの主な価値は、ブロック指向のストレージ コンテキスト (特にファイル システム) で効率的に検索できるようにデータを格納することです。
  4. NTFS は、ディレクトリのインデックス作成に B+ ツリーを使用します。

基本的に、範囲クエリのルックアップに役立ち、ツリーのトラバースを最小限に抑えます。

于 2016-08-01T03:08:21.993 に答える