StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>O(log n) queries and O(n log n) preprocessing/space could be achieved by finding and using <em>majority intervals</em> with following properties:</p> <ol> <li>For each <em>value</em> from input array there may be one or several <em>majority intervals</em> (or there may be none if elements with these values are too sparse; we don't need <em>majority intervals</em> of length 1 because they may be useful only for query intervals of size 1 which are better handled as a special case).</li> <li>If query interval lies completely inside one of these <em>majority intervals</em>, corresponding <em>value</em> <strong>may</strong> be the majority element of this query interval.</li> <li>If there is no <em>majority interval</em> completely containing query interval, corresponding <em>value</em> <strong>cannot</strong> be the majority element of this query interval.</li> <li>Each element of input array is covered by O(log n) <em>majority intervals</em>.</li> </ol> <p>In other words, the only purpose of <em>majority intervals</em> is to provide O(log n) majority element candidates for any query interval.</p> <p>This algorithm uses following <strong>data structures</strong>:</p> <ol> <li>List of positions for each <em>value</em> from input array (<code>map<Value, vector<Position>></code>). Alternatively <code>unordered_map</code> may be used here to improve performance (but we'll need to extract all keys and sort them so that structure #3 is filled in proper order).</li> <li>List of <em>majority intervals</em> for each <em>value</em> (<code>vector<Interval></code>).</li> <li>Data structure for handling queries (<code>vector<small_map<Value, Data>></code>). Where <code>Data</code> contains two indexes of appropriate vector from structure #1 pointing to next/previous positions of elements with given <em>value</em>. <strong>Update:</strong> Thanks to @justhalf, it is better to store in <code>Data</code> cumulative frequencies of elements with given <em>value</em>. <code>small_map</code> may be implemented as sorted vector of pairs - preprocessing will append elements already in sorted order and query will use <code>small_map</code> only for linear search.</li> </ol> <p><strong>Preprocessing:</strong></p> <ol> <li>Scan input array and push current position to appropriate vector in structure #1.</li> <li>Perform steps 3 .. 4 for every vector in structure #1.</li> <li>Transform list of positions into list of <em>majority intervals</em>. See details below.</li> <li>For each index of input array covered by one of <em>majority intervals</em>, insert data to appropriate element of structure #3: <em>value</em> and positions of previous/next elements with this <em>value</em> (or cumulative frequency of this <em>value</em>).</li> </ol> <p><strong>Query:</strong></p> <ol> <li>If query interval length is 1, return corresponding element of source array.</li> <li>For starting point of query interval get corresponding element of 3rd structure's vector. For each element of the map perform step 3. Scan all elements of the map corresponding to ending point of query interval in parallel with this map to allow O(1) complexity for step 3 (instead of O(log log n)).</li> <li>If the map corresponding to ending point of query interval contains matching <em>value</em>, compute <code>s3[stop][value].prev - s3[start][value].next + 1</code>. If it is greater than half of the query interval, return <em>value</em>. If cumulative frequencies are used instead of next/previous indexes, compute <code>s3[stop+1][value].freq - s3[start][value].freq</code> instead.</li> <li>If nothing found on step 3, return "Nothing".</li> </ol> <p><strong>Main part</strong> of the algorithm is getting <em>majority intervals</em> from list of positions:</p> <ol> <li>Assign <em>weight</em> to each position in the list: <code>number_of_matching_values_to_the_left - number_of_nonmatching_values_to_the_left</code>.</li> <li>Filter only <em>weights</em> in strictly decreasing order (greedily) to the "prefix" array: <code>for (auto x: positions) if (x < prefix.back()) prefix.push_back(x);</code>.</li> <li>Filter only <em>weights</em> in strictly increasing order (greedily, backwards) to the "suffix" array: <code>reverse(positions); for (auto x: positions) if (x > suffix.back()) suffix.push_back(x);</code>.</li> <li>Scan "prefix" and "suffix" arrays together and find intervals from every "prefix" element to corresponding place in "suffix" array and from every "suffix" element to corresponding place in "prefix" array. (If all "suffix" elements' weights are less than given "prefix" element or their position is not to the right of it, no interval generated; if there is no "suffix" element with exactly the weight of given "prefix" element, get nearest "suffix" element with larger weight and extend interval with this weight difference to the right).</li> <li>Merge overlapping intervals.</li> </ol> <p>Properties 1 .. 3 for <em>majority intervals</em> are guaranteed by this algorithm. As for property #4, the only way I could imagine to cover some element with maximum number of <em>majority intervals</em> is like this: <code>11111111222233455666677777777</code>. Here element <code>4</code> is covered by <code>2 * log n</code> intervals, so this property seems to be satisfied. See more formal proof of this property at the end of this post.</p> <p><strong>Example:</strong></p> <p>For input array "0 1 2 0 0 1 1 0" the following lists of positions would be generated:</p> <pre><code>value positions 0 0 3 4 7 1 1 5 6 2 2 </code></pre> <p>Positions for value <code>0</code> will get the following properties:</p> <pre><code>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 </code></pre> <p>Positions for value <code>1</code> will get the following properties:</p> <pre><code>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 </code></pre> <p>Query data structure:</p> <pre><code>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 ... </code></pre> <p>Query [0,4]:</p> <pre><code>prev[4][0]-next[0][0]+1=2-0+1=3 query size=5 3>2.5, returned result 0 </code></pre> <p>Query [2,5]:</p> <pre><code>prev[5][0]-next[2][0]+1=2-1+1=2 query size=4 2=2, returned result "none" </code></pre> <p>Note that there is no attempt to inspect element "1" because its <em>majority interval</em> does not include either of these intervals.</p> <p><strong>Proof of property #4:</strong></p> <p><em>Majority intervals</em> are constructed in such a way that strictly more than 1/3 of all their elements have corresponding <em>value</em>. This ratio is nearest to 1/3 for sub-arrays like <code>any*(m-1) value*m any*m</code>, for example, <code>01234444456789</code>.</p> <p>To make this proof more obvious, we could represent each interval as a point in 2D: every possible starting point represented by horizontal axis and every possible ending point represented by vertical axis (see diagram below).</p> <p><img src="https://i.stack.imgur.com/W0K6T.png" alt="enter image description here"></p> <p>All valid intervals are located on or above diagonal. White rectangle represents all intervals covering some array element (represented as unit-size interval on its lower right corner).</p> <p>Let's cover this white rectangle with squares of size 1, 2, 4, 8, 16, ... sharing the same lower right corner. This divides white area into O(log n) areas similar to yellow one (and single square of size 1 containing single interval of size 1 which is ignored by this algorithm).</p> <p>Let's count how many <em>majority intervals</em> may be placed into yellow area. One interval (located at the nearest to diagonal corner) occupies 1/4 of elements belonging to interval at the farthest from diagonal corner (and this largest interval contains all elements belonging to any interval in yellow area). This means that smallest interval contains strictly more than 1/12 <em>values</em> available for whole yellow area. So if we try to place 12 intervals to yellow area, we have not enough elements for different <em>values</em>. So yellow area cannot contain more than 11 <em>majority intervals</em>. And white rectangle cannot contain more than <code>11 * log n</code> <em>majority intervals</em>. Proof completed.</p> <p><code>11 * log n</code> is overestimation. As I said earlier, it's hard to imagine more than <code>2 * log n</code> <em>majority intervals</em> covering some element. And even this value is much greater than average number of covering <em>majority intervals</em>.</p> <p><strong>C++11 implementation.</strong> See it either at <a href="http://ideone.com/FLSDhe" rel="nofollow noreferrer">ideone</a> or here:</p> <pre><code>#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; } </code></pre> <p><strong>Related work:</strong></p> <p>As pointed in <a href="https://stackoverflow.com/a/19895770/1009831">other answer to this question</a>, there is other work where this problem is already solved: <a href="http://www.cs.umanitoba.ca/~durocher/research/pubs/durocherInfoComp2013.pdf" rel="nofollow noreferrer">"Range majority in constant time and linear space" by S. Durocher, M. He, I Munro, P.K. Nicholson, M. Skala</a>.</p> <p>Algorithm presented in this paper has better asymptotic complexities for query time: <code>O(1)</code> instead of <code>O(log n)</code> and for space: <code>O(n)</code> instead of <code>O(n log n)</code>.</p> <p>Better space complexity allows this algorithm to process larger data sets (comparing to the algorithm proposed in this answer). Less memory needed for preprocessed data and more regular data access pattern, most likely, allow this algorithm to preprocess data more quickly. But it is not so easy with query time...</p> <p>Let's suppose we have input data most favorable to algorithm from the paper: n=1000000000 (it's hard to imagine a system with more than 10..30 gigabytes of memory, in year 2013).</p> <p>Algorithm proposed in this answer needs to process up to 120 (or 2 query boundaries * 2 * log n) elements for each query. But it performs very simple operations, similar to linear search. And it sequentially accesses two contiguous memory areas, so it is cache-friendly.</p> <p>Algorithm from the paper needs to perform up to 20 operations (or 2 query boundaries * 5 candidates * 2 wavelet tree levels) for each query. This is 6 times less. But each operation is more complex. Each query for succinct representation of bit counters itself contains a linear search (which means 20 linear searches instead of one). Worst of all, each such operation should access several independent memory areas (unless query size and therefore quadruple size is very small), so query is cache-unfriendly. Which means each query (while is a constant-time operation) is pretty slow, probably slower than in algorithm proposed here. If we decrease input array size, increased are the chances that proposed here algorithm is quicker.</p> <p>Practical disadvantage of algorithm in the paper is wavelet tree and succinct bit counter implementation. Implementing them from scratch may be pretty time consuming. Using a pre-existing implementation is not always convenient.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload