1

整数のリストから整数を検索する必要があります。それらを並べ替え、lower_bound を使用して、指定された整数が収まる範囲を見つけます。これには O(lgn) が必要です。これよりもうまくやる方法はありますか？

以下は改善のヒントです。

  1. 指定されたリストは常に正の整数です
  2. リストは固定です。挿入も削除もありません。

1 つの方法は、配列を作成し、配列にインデックスを付けることです。これは、スペース効率が悪い場合があります。unordered_map を使用できますか? どのハッシュ関数を定義すればよいですか?

// Sort in reverse order to aid the lookup process
vector<unsigned int> sortedByRange;
//... sortedByRange.push_back(..)
sort(sortedByRange.begin(), sortedByRange.end(), greater);
Range = (sortedByAddress_.begin() - sortedByRange.end();
std::cout<<"Range :"<<Range<<std::endl;    //prints 3330203948

std::pair<unsigned int, unsigned int> lookup(unsigned int addr){
    pair<unsigned int, unsigned int> result;
    vector<unsigned int>::iterator it = lower_bound(sortedByRange.begin(), 
                                           sortedByRange.end(), addr);
    result.first = *it;
    result.second = *(it++);
    return result;
}
4

3 に答える 3

1

合計範囲が大きくない場合は、任意のサイズのサンプリングされたインデックス配列を構築できます (どのくらいの RAM を投入したいですか?)

したがって、たとえば、データの合計範囲が 256M で、予備のメガバイトがある場合、データ範囲の 1K 間隔ごとの位置を格納します。次に、任意のデータ ポイントに対して、O(1) (実際には O(2) :) ) インデックス配列を調べて、そのデータ ポイントの妥当な範囲の下限と上限を見つけます。範囲。範囲のサイズが大きく変動しない場合は、平均一定時間のルックアップが得られるはずです。

問題に多くのメモリを投入したくない場合は、平均範囲サイズとファズ ファクターに基づいて線形推定値のペアを試すことができます。特定のデータポイントが含まれていないことが判明した場合は、完全なバイナリ検索にフォールバックできます。そうでない場合も、制限された範囲内のバイナリ検索は平均線形時間になるはずです。

手振りが十分に明確でない場合の最初の提案は次のとおりです。完全にテストされていないコードで、コンパイルも試みていません。整数型の使用は、控えめに言っても、ずさんです。使用する場合は、より美しくするようにしてください。また、インデックス範囲の開始を *begin_; に制限する必要がありました (ただし、制限しませんでした)。0 より大幅に大きい場合は、修正する必要があります。

// The provided range must be sorted, and value_type must be arithmetic.
template<type RandomIterator, unsigned long size>
class IndexedLookup {
 public:
  using value_type = typename RandomIterator::value_type;
  IndexedLookup(RandomIterator begin, RandomIterator end)
    : begin_(begin),
      end_(end),
      delta_(*(end_ - 1) / size) {
    for (unsigned long i = 0; i < size; ++i)
      index_[i] = std::lower_bound(begin_, end_, i * delta_) - begin_;
      // The above expression cannot be out of range
    index_[size] = end_ - begin_;
  }

  RandomIterator lookup(value_type needle) {
    int low = needle / delta_;
    return std::lower_bound(index_[begin_ + low],
                            index_[begin_ + low + 1],
                            needle);
  }

 private:
  RandomIterator begin_, end_;
  value_type delta_;
  std::array<int, size + 1> index_;
}
于 2012-09-26T04:58:07.697 に答える
0

方法 1:特定の数値がリストに含まれているかどうかを知りたいだけで、最大値が大きすぎない場合は、ビット フィールドの使用を検討できます。その場合、ルックアップは O(1) 操作になります。

方法 2:値の範囲が巨大 (小さな整数と大きな整数) であるが、リストのサイズが大きくない (数千など) 場合は、(プログラムで) ハッシュ関数を作成してみることができます。

  1. リスト内の の値に対して 1 対 1 です。
  2. range 0...の値が得られますが、十分N + mにm 小さいです。
  3. 比較的安価に計算できます。

次に、定数リストの値を配列に入れ、ハッシュ値でインデックスを付けて、特定の入力値が含まれているかどうかをすばやく確認できるようにします。リストに穴がある場合 (mゼロ以外)、穴は特別な値 (例: -1) で示されます。

包含テスト: 与えられた入力に対して 1. ハッシュ値を計算します。2. ハッシュ値の値が範囲外の場合、入力はリストにありません。3. それ以外の場合、ハッシュ値によってインデックス付けされた生成された配列の値が入力値と同じである場合にのみ、入力はリストに属します。

ハッシュ関数を作成する方法は、SO の別の質問に値します (文字列値の場合、この目的のためにツールを生成するツールが存在します)。:-)

制限:リストがコンパイル時に作成されず、プログラムの実行時に計算または受信される場合、この方法は適していません。また、このリストが頻繁に変更される場合、ハッシュ関数の生成に必要な計算時間とコードにより、このアプローチが不適切になる可能性があります。

于 2012-09-26T03:53:06.463 に答える