2

オブジェクトとそれが有効な期間を記述する次のデータ構造があります。以下の数字は UNIX タイムスタンプであると仮定します。

{
  "id": 1234,
  "valid_from": 2000
  "valid_to": 4000
},
{
 "id": 1235,
 "valid_from": 1000,
 "valid_to": 2200,
}
...

これらのアイテムを JavaScript にすばやく保存し、特定の時点で有効なアイテムを照会できるようにしたいと考えています。

たとえば、2100 で有効なオブジェクトを照会すると、[1234, 1235] が返されます。3999 で有効なオブジェクトを照会すると、[1234] が返され、4999 では何も返されません。

構造内に約 50 ～ 100k のアイテムのサイズがあり、検索速度を速くしたいのですが、挿入と削除は遅くなる可能性があります。

アイテムには重複する valid_from と valid_to の値があるため、重複をサポートする必要があります。項目が重複します。

構造に継続的にデータを挿入する必要があります (おそらく、初期ロードでは一括で挿入し、データの変更に応じて 1 回ずつ更新します)。また、レコードを定期的に変更するので、おそらく削除と挿入を行います。

これに対する最良のアプローチが非常に効率的な方法であるかわかりませんか？

アルゴリズムは私の得意分野ではありませんが、正しいアプローチを知っていれば、アルゴリズム自体を研究できます。

私の考え:

私は当初、重複キーと最も近いルックアップをサポートするように修正されたバイナリ サーチ ツリーを考えていましたが、これでは > valid_from または < valid_to のオブジェクトしかクエリできません。

これには、配列またはツリーを 2 等分してすべての項目 > valid_from を見つけてから、それぞれの項目を手動で valid_to をチェックする必要があります。

2 つの検索ツリー (valid_to と valid_from の 1 つ) を持つことができると思います。次に、結果から重複する ID を確認し、それらの ID を返すことができますか?

これはまだハックのように思えますか？誰かが推奨できるより良いアプローチはありますか、それともこれがどのように行われたかです。

4

1 に答える 1

0

開始/開始と有効期限/終了の 2 つのリストがあるとします。どちらも TIME でソートされています。

特定の時間が与えられた場合、二分探索によって基準を満たす最初のアイテムが各リストのどこにあるかを見つけることができます。各リストに二分探索による挿入を行うこともできます。

たとえば、1000 個の項目があり、開始位置が 342 の場合、項目 1 ～ 342 が可能であり、終了位置が 901 の場合、終了リストの項目 901 ～ 1000 が可能です。両方のサブリストを交差させる必要があります。

begin で 1 から 342 まで、end で 901 から 1000 までのアイテム ID を取得し、それらを別の配列に入れます (事前に割り当てられます)。配列をソートします。配列をトラバースします。同じ ID が 2 回続けて出現する場合は常に、ヒット、つまり有効な一致です。

于 2015-06-10T13:03:26.020 に答える