O(log n) クエリと O(n log n) 前処理/スペースは、次のプロパティを持つ多数区間を見つけて使用することで実現できます。
言い換えれば、多数区間の唯一の目的は、任意のクエリ インターバルに対して O(log n) 個の多数要素候補を提供することです。
このアルゴリズムは、次のデータ構造を使用します。
map<Value, vector<Position>>)。代わりunordered_mapに、パフォーマンスを向上させるためにここで使用することもできます (ただし、構造 #3 が適切な順序で満たされるように、すべてのキーを抽出して並べ替える必要があります)。vector<Interval>vector<small_map<Value, Data>>)。whereには、指定されたvalueDataを持つ要素の次/前の位置を指す構造 #1 からの適切なベクトルの 2 つのインデックスが含まれます。更新: @justhalf のおかげで、指定された値を持つ要素の累積頻度を格納する方が適切です。ペアの並べ替えられたベクトルとして実装できます。前処理により、既に並べ替えられた順序で要素が追加され、クエリは線形検索にのみ使用されます。Datasmall_mapsmall_map前処理:
クエリ:
s3[stop][value].prev - s3[start][value].next + 1ます。クエリ間隔の半分より大きい場合は、valueを返します。次/前のインデックスの代わりに累積度数を使用する場合は、s3[stop+1][value].freq - s3[start][value].freq代わりに計算します。アルゴリズムの主要部分は、位置のリストから多数決区間を取得することです。
number_of_matching_values_to_the_left - number_of_nonmatching_values_to_the_left.for (auto x: positions) if (x < prefix.back()) prefix.push_back(x);。reverse(positions); for (auto x: positions) if (x > suffix.back()) suffix.push_back(x);ます。多数区間のプロパティ 1 .. 3 は、このアルゴリズムによって保証されます。プロパティ #4 に関しては、多数区間の最大数でいくつかの要素をカバーすることが想像できる唯一の方法は、次のようなものです11111111222233455666677777777。ここでは要素4が間隔で覆われて2 * log nいるため、このプロパティは満たされているようです。この記事の最後で、このプロパティのより正式な証明を参照してください。
例：
入力配列 "0 1 2 0 0 1 1 0" の場合、次の位置リストが生成されます。
value positions
0 0 3 4 7
1 1 5 6
2 2
value の位置は0、次のプロパティを取得します。
weights: 0:1 3:0 4:1 7:0
prefix: 0:1 3:0 (strictly decreasing)
suffix: 4:1 7:0 (strictly increasing when scanning backwards)
intervals: 0->4 3->7 4->0 7->3
merged intervals: 0-7
value の位置は1、次のプロパティを取得します。
weights: 1:0 5:-2 6:-1
prefix: 1:0 5:-2
suffix: 1:0 6:-1
intervals: 1->none 5->6+1 6->5-1 1->none
merged intervals: 4-7
クエリ データ構造:
positions value next prev
0 0 0 x
1..2 0 1 0
3 0 1 1
4 0 2 2
4 1 1 x
5 0 3 2
...
クエリ [0,4]:
prev[4][0]-next[0][0]+1=2-0+1=3
query size=5
3>2.5, returned result 0
クエリ [2,5]:
prev[5][0]-next[2][0]+1=2-1+1=2
query size=4
2=2, returned result "none"
要素 "1" の検査は試行されないことに注意してください。これは、多数区間にこれらの区間のいずれも含まれていないためです。
プロパティ #4 の証明:
大多数区間は、すべての要素の厳密に 1/3 以上が対応する値を持つように構築されます。any*(m-1) value*m any*mこの比率は、たとえば のようなサブアレイでは 1/3 に最も近くなります01234444456789。
この証明をより明確にするために、各間隔を 2D の点として表すことができます。つまり、可能なすべての開始点を横軸で表し、すべての可能な終了点を縦軸で表します (下の図を参照)。
すべての有効な区間は、対角線上または上にあります。白い四角形は、一部の配列要素をカバーするすべての間隔を表します (右下隅に単位サイズの間隔として表されます)。
この白い長方形を、同じ右下隅を共有するサイズ 1、2、4、8、16、... の正方形で覆いましょう。これは、白い領域を黄色の領域と同様の O(log n) 領域 (および、このアルゴリズムでは無視されるサイズ 1 の単一間隔を含むサイズ 1 の単一正方形) に分割します。
黄色の領域に配置できる過半数区間の数を数えましょう。1 つの間隔 (対角隅に最も近い位置) は、対角隅から最も遠い間隔に属する要素の 1/4 を占めます (この最大の間隔には、黄色の領域の任意の間隔に属するすべての要素が含まれます)。これは、最小間隔には、黄色の領域全体で使用可能な値の1/12 を厳密に超える値が含まれることを意味します。したがって、黄色の領域に 12 個の間隔を配置しようとすると、さまざまな値に対して十分な要素がありません。したがって、黄色の領域には 11 以上の過半数区間を含めることはできません。11 * log n また、白い四角形には多数区間よりも多くの区間を含めることはできません。証明完了。
11 * log n過大評価です。先に述べたように、いくつかの要素をカバーする2 * log n 過半数以上の区間を想像するのは困難です。そして、この値でさえ、多数区間をカバーする平均数よりもはるかに大きくなっています。
C++11 実装。ideoneまたはここで参照してください。
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <random>
constexpr int SrcSize = 1000000;
constexpr int NQueries = 100000;
using src_vec_t = std::vector<int>;
using index_vec_t = std::vector<int>;
using weight_vec_t = std::vector<int>;
using pair_vec_t = std::vector<std::pair<int, int>>;
using index_map_t = std::map<int, index_vec_t>;
using interval_t = std::pair<int, int>;
using interval_vec_t = std::vector<interval_t>;
using small_map_t = std::vector<std::pair<int, int>>;
using query_vec_t = std::vector<small_map_t>;
constexpr int None = -1;
constexpr int Junk = -2;
src_vec_t generate_e()
{ // good query length = 3
src_vec_t src;
std::random_device rd;
std::default_random_engine eng{rd()};
auto exp = std::bind(std::exponential_distribution<>{0.4}, eng);
for (int i = 0; i < SrcSize; ++i)
{
int x = exp();
src.push_back(x);
//std::cout << x << ' ';
}
return src;
}
src_vec_t generate_ep()
{ // good query length = 500
src_vec_t src;
std::random_device rd;
std::default_random_engine eng{rd()};
auto exp = std::bind(std::exponential_distribution<>{0.4}, eng);
auto poisson = std::bind(std::poisson_distribution<int>{100}, eng);
while (int(src.size()) < SrcSize)
{
int x = exp();
int n = poisson();
for (int i = 0; i < n; ++i)
{
src.push_back(x);
//std::cout << x << ' ';
}
}
return src;
}
src_vec_t generate()
{
//return generate_e();
return generate_ep();
}
int trivial(const src_vec_t& src, interval_t qi)
{
int count = 0;
int majorityElement = 0; // will be assigned before use for valid args
for (int i = qi.first; i <= qi.second; ++i)
{
if (count == 0)
majorityElement = src[i];
if (src[i] == majorityElement)
++count;
else
--count;
}
count = 0;
for (int i = qi.first; i <= qi.second; ++i)
{
if (src[i] == majorityElement)
count++;
}
if (2 * count > qi.second + 1 - qi.first)
return majorityElement;
else
return None;
}
index_map_t sort_ind(const src_vec_t& src)
{
int ind = 0;
index_map_t im;
for (auto x: src)
im[x].push_back(ind++);
return im;
}
weight_vec_t get_weights(const index_vec_t& indexes)
{
weight_vec_t weights;
for (int i = 0; i != int(indexes.size()); ++i)
weights.push_back(2 * i - indexes[i]);
return weights;
}
pair_vec_t get_prefix(const index_vec_t& indexes, const weight_vec_t& weights)
{
pair_vec_t prefix;
for (int i = 0; i != int(indexes.size()); ++i)
if (prefix.empty() || weights[i] < prefix.back().second)
prefix.emplace_back(indexes[i], weights[i]);
return prefix;
}
pair_vec_t get_suffix(const index_vec_t& indexes, const weight_vec_t& weights)
{
pair_vec_t suffix;
for (int i = indexes.size() - 1; i >= 0; --i)
if (suffix.empty() || weights[i] > suffix.back().second)
suffix.emplace_back(indexes[i], weights[i]);
std::reverse(suffix.begin(), suffix.end());
return suffix;
}
interval_vec_t get_intervals(const pair_vec_t& prefix, const pair_vec_t& suffix)
{
interval_vec_t intervals;
int prev_suffix_index = 0; // will be assigned before use for correct args
int prev_suffix_weight = 0; // same assumptions
for (int ind_pref = 0, ind_suff = 0; ind_pref != int(prefix.size());)
{
auto i_pref = prefix[ind_pref].first;
auto w_pref = prefix[ind_pref].second;
if (ind_suff != int(suffix.size()))
{
auto i_suff = suffix[ind_suff].first;
auto w_suff = suffix[ind_suff].second;
if (w_pref <= w_suff)
{
auto beg = std::max(0, i_pref + w_pref - w_suff);
if (i_pref < i_suff)
intervals.emplace_back(beg, i_suff + 1);
if (w_pref == w_suff)
++ind_pref;
++ind_suff;
prev_suffix_index = i_suff;
prev_suffix_weight = w_suff;
continue;
}
}
// ind_suff out of bounds or w_pref > w_suff:
auto end = prev_suffix_index + prev_suffix_weight - w_pref + 1;
// end may be out-of-bounds; that's OK if overflow is not possible
intervals.emplace_back(i_pref, end);
++ind_pref;
}
return intervals;
}
interval_vec_t merge(const interval_vec_t& from)
{
using endpoints_t = std::vector<std::pair<int, bool>>;
endpoints_t ep(2 * from.size());
std::transform(from.begin(), from.end(), ep.begin(),
[](interval_t x){ return std::make_pair(x.first, true); });
std::transform(from.begin(), from.end(), ep.begin() + from.size(),
[](interval_t x){ return std::make_pair(x.second, false); });
std::sort(ep.begin(), ep.end());
interval_vec_t to;
int start; // will be assigned before use for correct args
int overlaps = 0;
for (auto& x: ep)
{
if (x.second) // begin
{
if (overlaps++ == 0)
start = x.first;
}
else // end
{
if (--overlaps == 0)
to.emplace_back(start, x.first);
}
}
return to;
}
interval_vec_t get_intervals(const index_vec_t& indexes)
{
auto weights = get_weights(indexes);
auto prefix = get_prefix(indexes, weights);
auto suffix = get_suffix(indexes, weights);
auto intervals = get_intervals(prefix, suffix);
return merge(intervals);
}
void update_qv(
query_vec_t& qv,
int value,
const interval_vec_t& intervals,
const index_vec_t& iv)
{
int iv_ind = 0;
int qv_ind = 0;
int accum = 0;
for (auto& interval: intervals)
{
int i_begin = interval.first;
int i_end = std::min<int>(interval.second, qv.size() - 1);
while (iv[iv_ind] < i_begin)
{
++accum;
++iv_ind;
}
qv_ind = std::max(qv_ind, i_begin);
while (qv_ind <= i_end)
{
qv[qv_ind].emplace_back(value, accum);
if (iv[iv_ind] == qv_ind)
{
++accum;
++iv_ind;
}
++qv_ind;
}
}
}
void print_preprocess_stat(const index_map_t& im, const query_vec_t& qv)
{
double sum_coverage = 0.;
int max_coverage = 0;
for (auto& x: qv)
{
sum_coverage += x.size();
max_coverage = std::max<int>(max_coverage, x.size());
}
std::cout << " size = " << qv.size() - 1 << '\n';
std::cout << " values = " << im.size() << '\n';
std::cout << " max coverage = " << max_coverage << '\n';
std::cout << " avg coverage = " << sum_coverage / qv.size() << '\n';
}
query_vec_t preprocess(const src_vec_t& src)
{
query_vec_t qv(src.size() + 1);
auto im = sort_ind(src);
for (auto& val: im)
{
auto intervals = get_intervals(val.second);
update_qv(qv, val.first, intervals, val.second);
}
print_preprocess_stat(im, qv);
return qv;
}
int do_query(const src_vec_t& src, const query_vec_t& qv, interval_t qi)
{
if (qi.first == qi.second)
return src[qi.first];
auto b = qv[qi.first].begin();
auto e = qv[qi.second + 1].begin();
while (b != qv[qi.first].end() && e != qv[qi.second + 1].end())
{
if (b->first < e->first)
{
++b;
}
else if (e->first < b->first)
{
++e;
}
else // if (e->first == b->first)
{
// hope this doesn't overflow
if (2 * (e->second - b->second) > qi.second + 1 - qi.first)
return b->first;
++b;
++e;
}
}
return None;
}
int main()
{
std::random_device rd;
std::default_random_engine eng{rd()};
auto poisson = std::bind(std::poisson_distribution<int>{500}, eng);
int majority = 0;
int nonzero = 0;
int failed = 0;
auto src = generate();
auto qv = preprocess(src);
for (int i = 0; i < NQueries; ++i)
{
int size = poisson();
auto ud = std::uniform_int_distribution<int>(0, src.size() - size - 1);
int start = ud(eng);
int stop = start + size;
auto res1 = do_query(src, qv, {start, stop});
auto res2 = trivial(src, {start, stop});
//std::cout << size << ": " << res1 << ' ' << res2 << '\n';
if (res2 != res1)
++failed;
if (res2 != None)
{
++majority;
if (res2 != 0)
++nonzero;
}
}
std::cout << "majority elements = " << 100. * majority / NQueries << "%\n";
std::cout << " nonzero elements = " << 100. * nonzero / NQueries << "%\n";
std::cout << " queries = " << NQueries << '\n';
std::cout << " failed = " << failed << '\n';
return 0;
}
関連作業：
この質問に対する他の回答で指摘されているように、この問題が既に解決されている他の作業があります: S. Durocher、M. He、I Munro、PK Nicholson、M. Skala による「定数時間と線形空間における範囲の多数派」。
このホワイト ペーパーで提示されているアルゴリズムは、クエリ時間:O(1)の代わりに、O(log n)およびスペース:のO(n)代わりに、より優れた漸近的な複雑さを備えていますO(n log n)。
スペースの複雑さが向上すると、このアルゴリズムはより大きなデータセットを処理できます (この回答で提案されているアルゴリズムと比較して)。前処理されたデータに必要なメモリが少なく、より規則的なデータ アクセス パターンがあれば、おそらく、このアルゴリズムはデータをより迅速に前処理できます。しかし、クエリ時間ではそれほど簡単ではありません...
論文からアルゴリズムに最も適した入力データがあるとしましょう: n=1000000000 (2013 年に 10..30 ギガバイトを超えるメモリを搭載したシステムを想像するのは困難です)。
この回答で提案されているアルゴリズムは、クエリごとに最大 120 (または 2 クエリ境界 * 2 * log n) の要素を処理する必要があります。ただし、線形検索と同様に、非常に単純な操作を実行します。また、連続する 2 つのメモリ領域にシーケンシャルにアクセスするため、キャッシュ フレンドリーです。
この論文のアルゴリズムは、クエリごとに最大 20 の操作 (または 2 つのクエリ境界 * 5 つの候補 * 2 つのウェーブレット ツリー レベル) を実行する必要があります。これは 6 分の 1 です。ただし、各操作はより複雑です。ビット カウンター自体の簡潔な表現の各クエリには、線形検索が含まれています (つまり、1 回ではなく 20 回の線形検索を意味します)。最悪なことに、そのような各操作は複数の独立したメモリ領域にアクセスする必要があるため (クエリのサイズが非常に小さく、したがって 4 倍のサイズが非常に小さい場合を除きます)、クエリはキャッシュに適していません。これは、各クエリ (while は一定時間の操作) がかなり遅く、おそらくここで提案されているアルゴリズムよりも遅いことを意味します。入力配列のサイズを小さくすると、ここで提案されたアルゴリズムがより高速になる可能性が高くなります。
この論文のアルゴリズムの実際的な欠点は、ウェーブレット ツリーと簡潔なビット カウンターの実装です。それらを最初から実装すると、かなり時間がかかる場合があります。既存の実装を使用することは必ずしも便利ではありません。
トリック
多数要素を探す場合、多数要素を持たない間隔を破棄できます。配列の多数要素を検索するを参照してください。これにより、これを非常に簡単に解決できます。
準備
準備時に、再帰的に配列を 2 つに分割し続け、これらの配列間隔をバイナリ ツリーに格納します。ノードごとに、配列間隔内の各要素の出現回数を数えます。O(1) の挿入と読み取りを提供するデータ構造が必要です。unsorted_multiset を使用することをお勧めします。これは、平均して必要に応じて動作します (ただし、最悪の場合の挿入は線形です)。また、間隔に多数要素があるかどうかを確認し、ある場合は保存します。
ランタイム
実行時に、範囲の多数要素を計算するように求められたら、ツリーに飛び込んで、指定された範囲を正確にカバーする間隔のセットを計算します。トリックを使用して、これらの間隔を組み合わせます。
配列 interval7 5 5 7 7 7と多数要素がある場合、多数要素がないため、7分割して破棄でき5 5 7 7ます。事実上、ファイブはセブンのうちの2つを飲み込みました。残っているのは、配列7 7、または2x7. この数を多数要素の2多数派カウントと呼び7ます。
配列区間の多数要素の多数決カウントは、多数要素の出現カウントから他のすべての要素の結合出現を差し引いたものです。
次のルールを使用して間隔を組み合わせ、潜在的な多数要素を見つけます。
- 大部分の要素を持たない区間を破棄
- 同じ過半数要素を持つ 2 つの配列を組み合わせるのは簡単です。要素の過半数カウントを合計するだけです。
2x7そして3x7なる5x7- 多数決要素が異なる 2 つの配列を組み合わせると、多数決数が多い方が優先されます。上位の多数派カウントから下位の多数派カウントを引き、結果の多数派カウントを見つけます。
3x7と2x3なり1x7ます。- 多数決要素が異なっていても多数決カウントが等しい場合は、両方の配列を無視します。
3x7そしてお互いを3x5打ち消し合う。
すべての間隔が破棄されるか結合されると、何も残されなくなります。この場合、多数決要素はありません。または、潜在的な多数要素を含む 1 つの結合間隔があります。すべての配列間隔 (以前に破棄されたものも含む) でこの要素の出現回数を検索して追加し、それが実際に多数要素であるかどうかを確認します。
例
配列1,1,1,2,2,3,3,2,2,2,3,2,2の場合、ツリーを取得します (大多数のカウント x 大多数の要素が括弧内にリストされています)
1,1,1,2,2,3,3,2,2,2,3,2,2
(1x2)
/ \
1,1,1,2,2,3,3 2,2,2,3,2,2
(4x2)
/ \ / \
1,1,1,2 2,3,3 2,2,2 3,2,2
(2x1) (1x3) (3x2) (1x2)
/ \ / \ / \ / \
1,1 1,2 2,3 3 2,2 2 3,2 2
(1x1) (1x3) (2x2) (1x2) (1x2)
/ \ / \ / \ / \ / \
1 1 1 2 2 3 2 2 3 2
(1x1) (1x1)(1x1)(1x2)(1x2)(1x3) (1x2)(1x2) (1x3) (1x2)
範囲 [5,10] (1 インデックス) は、間隔 2,3,3 (1x3)、2,2,2 (3x2) のセットによってカバーされます。それらには異なる大多数の要素があります。それらの過半数の数を差し引くと、2x2 が残ります。したがって、2 は潜在的な多数要素です。配列内の 2 の実際の出現回数を調べて合計します。1+3 = 6 のうちの 4 です。2 が多数要素です。
範囲 [1,10] は、区間 1,1,1,2,2,3,3 (多数要素なし) および 2,2,2 (3x2) のセットによってカバーされます。最初の間隔は多数要素がないため無視します。したがって、2 が多数要素になる可能性があります。すべての間隔で 2 の出現回数を合計します: 2+3 = 10 のうち 5。多数決要素はありません。
実際、一定の時間と線形空間で実行できます（！）
https://cs.stackexchange.com/questions/16671/range-majority-queries-most-freqent-element-in-rangeおよびS. Durocher、M. He、I Munro、PK Nicholson、M. Skala、Rangeを参照してください。定数時間と線形空間での多数派、Information and Computation 222 (2013) 169–179、Elsevier。
それらの準備時間は O(n log n)、必要なスペースは O(n)、クエリは O(1) です。これは理論的な論文であり、すべてを理解しているとは言えませんが、実装するのは不可能ではないようです。ウェーブレット ツリーを使用しています。
ウェーブレット ツリーの実装については、https://github.com/fclaude/libcdsを参照してください。
無制限のメモリがある場合は、O(N) 時間でもデータ範囲を制限できます (short int など) 。
合計で O(1) + O(N) 操作。
また、配列 X の代わりにマップを使用する場合は、O(N) メモリで自分を制限できます。ただし、ステージ 1 の各反復で要素を見つける必要があります。したがって、O(N*log(N)) 時間が必要になります。合計で。
MAX Heap を使用できます。数値の頻度を Keeping Max Heap プロパティの決定要因として使用できます。たとえば、次の入力配列の場合などです。
1 5 2 7 7 7 8 4 6 5
Heap would have all distinct elements with their frequency associated with them
Element = 1 Frequency = 1,
Element = 5 Frequency = 2,
Element = 2 Frequency = 1,
Element = 7 Frequency = 3,
Element = 8 Frequency = 1,
Element = 4 Frequency = 1,
Element = 6 Frequency = 1
その MAX ヒープとして、頻度 3 の要素 7 はルート レベルになります。入力範囲にこの要素が含まれているかどうかを確認します。はいの場合、これが答えです。いいえの場合は、入力範囲に従って左のサブツリーまたは右のサブツリーに移動し、実行します。同じチェック。
O(N) は、ヒープの作成中に 1 回だけ必要になりますが、ヒープが作成されると、検索が効率的になります。
編集：申し訳ありませんが、別の問題を解決していました。
配列をソートし、ペア (値、出現回数) の順序付きリストを作成しますO(N log N).。
1 5 2 7 7 7 8 4 6
そうなる
(1,1) (2,1) (4,1) (5,1) (6,1) (7,3) (8,1)
この配列の上に、ペア ( best_value_or_none, max_occurrences) でバイナリ ツリーを構築します。次のようになります。
(1,1) (2,1) (4,1) (5,1) (6,1) (7,3) (8,1)
\ / \ / \ / |
(0,1) (0,1) (7,3) (8,1)
\ / \ /
(0,1) (7,3)
\ /
(7,3)
この構造には間違いなく派手な名前が付いていますが、覚えていません:)
ここからO(log N)、任意の間隔のモードをフェッチします。O(log N)任意の間隔は、事前計算された間隔に分割できます。例えば：
[4, 7] = [4, 5] + [6, 7]
f([4,5]) = (0,1)
f([6,7]) = (7,3)
結果は (7,3) です。