API呼び出しからデータのランダムなスライスに効率的にアクセスするためのデータ構造

Question

APIのライブラリを書いて、順序付けられたデータストリームをプルダウンします。このAPIを使用すると、スライスごとにデータを呼び出すことができます。たとえば、アイテム15-25が必要な場合は、API呼び出しを行うことができます。

私たちが書いているライブラリでは、クライアントはデータのスライスを呼び出すことができますが、これらのapi呼び出しをできるだけ効率的にしたいと考えています。だからすでに21から30までのアイテムを頼んだら、それらの個々のデータアイテムを再び要求したくない。もし誰かが図書館に15-25を求めたら、私たちはapiを15-20に電話したいと思っています。私たちは既に持っているデータを検索し、そのデータを再度要求しないようにする必要があります。

これらのAPIコールの結果を格納するための最も効率的なデータ構造は何ですか？データセットは膨大ではないので、ローカルメモリでの検索時間はそれほど大きなものではありません。私たちはコードの簡潔さと清潔さを求めています。この問題にはいくつかの明白な答えがありますが、データ構造が変わっても気にしない優雅な解決策があるのではないかと不思議です。

参考のため、私たちはPythonでコーディングしていますが、この問題をエレガントに解決するデータ構造を探しています。

Answer 1

私は、begin - >（end、data）をマッピングするためにバランスのとれたバイナリツリー（例：http://pypi.python.org/pypi/bintrees/0.4.0）を使用します。新しい要求が[b、e]の範囲に入ると、bを検索して（b！= keyの場合は前のレコードに移動します）、eをもう一度検索した場合（また戻る）、結果キー間のすべてのエントリをスキャンします欠落している範囲をプルダウンし、すべてのキャッシュ間隔と新しいデータを1つの間隔にマージします。キャッシュ内のN個の区間については、各キャッシュ更新の償却されたO（log-N）コストが得られます。

begin（begin、end、data）タプルのリストを保持し、bisect_rightを使って検索することもできます。コスト：最悪の場合、更新ごとにO（N =キャッシュされた間隔の数）ですが、クライアントがデータを増加する順番で要求する傾向がある場合、キャッシュの更新はO（1）になります。

いずれの場合も、キャッシュ検索自体はO（log-N）です。

Answer 2

この問題を自己解決するためによく使用される標準的なデータ構造は、区間ツリーです。 （this Wikipedia articleを参照してください）問題は、送信したもの（どの間隔）が送信しようとしているものと重なっているかを知る必要があると考えることができます。 send（オーバーラップした間隔の数に対して線形時間です）、そこにいます。ウィキペディアの記事の下半分にある "Augmented"ツリーは実装が簡単に見えますが、私はそれに固執します。 "ログN"時間の複雑さ、償却またはそうでなければならない。