データ構造/セクションルックアップのアルゴリズム

Question

各セクションのエンドポイントのリストがある場合、現在どのセクションを参照するためにどのようなデータ構造/アルゴリズムを使用すべきですか？例えば

、Iは、セクションヘッダとコンテンツを含むウェブページを持っている場合、

• 入門（100ピクセルで終わる）
• セクション1（350pxで終了）
• セクション2（700pxで終了）
• 結論（1200pxで終了）
• コメント

と私は現在130pxで、それは私が現在「セクション1」にいると返すべきです。

エンドポイント

from bisect import bisect_left 

arr = [100, 350, 700, 1200] 
pos = bisect_left(arr, 130, 0, arr[-1]) 

の配列をオプション1件の

バイナリ検索をしかし、これはまだ位置の変更ごとに（n個のログ）Oを取ることができます。現在の場所の

オプション2

ハッシュテーブルルックアップは、

lookup = {0: "Introduction" 
      1: "Introduction" 
      ... 
      10: "Section 1" 
      11: "Section 1" 
      ... 
     } 
section = lookup[130/10] 

これは高速ですが、それは一般的なデータ構造/アルゴリズムがありますスペース

---

の多くを無駄にこのタイプの問題を扱うのは？

Answer 1

私はあなたの最初のオプションが好きです。バイナリ検索はスキャンにとって非常に効率的で、2番目のオプションはスペース効率が良いと言います。

コンピュータグラフィックスの縮尺が従来の非常に一般的な解決策は2d k-treeで、メモリを浪費することなく座標を参照できるツリーが作成されます。具体的には、その探索、除去および挿入の複雑さはすべてO（log n）であり、その空間の複雑さはO（n）である。

あなたは1つの軸だけを扱っており、ウェブページは1〜100個のセクションを持つ傾向がある（つまり、何百万もあるとは思われませんが、何百万、何十億ものセクションを除いて）非常に単純な配列であり、測定可能な利益/必要がある場合は、より複雑なk-treeに移動します。これをCや他の言語で書いてメモリのレイアウトを制御すれば、現代のcpusとメモリ階層の設計（特にプリフェッチャとキャッシング）のために構造体の配列が非常に高速になります。

Answer 2

最も簡単で効果的なのは、O（LogN）の複雑さを持つバイナリ検索を使用することです。

あなたは2番目のオプションがより複雑なO（1）を持っていますが、事前投入では不利になります。バイナリ検索の事前設定がより簡単になりました。

ランタイムでセクションを更新しないと、これらの方法の両方が最適です。

セクションの実行時間の追加/削除/更新が必要な場合に必要なデータ構造。 O（N）で事前入力データを更新する必要があるためです。これは、更新/追加/削除セクション操作がO（N）までかかることを意味します。