O(log n) requêtes et O(n log n) prétraitement/espace pourrait être atteint en trouvant et en utilisant intervalles de majorité avec les propriétés suivantes :
- Pour chaque valeur à partir du tableau d'entrée, il peut y avoir un ou plusieurs intervalles de majorité (ou il peut n'y en avoir aucun si les éléments avec ces valeurs sont trop épars ; nous n'avons pas besoin de intervalles de majorité de longueur 1 car ils peuvent être utiles uniquement pour les intervalles de requête de taille 1 qui sont mieux traités comme un cas spécial).
- Si l'intervalle de requête se trouve complètement à l'intérieur d'une de ces intervalles de majorité correspondant valeur mai être l'élément majoritaire de cet intervalle d'interrogation.
- S'il n'y a pas de intervalle majoritaire contenant complètement l'intervalle de requête, correspondant valeur ne peut pas être l'élément majoritaire de cet intervalle d'interrogation.
- Chaque élément du tableau d'entrée est couvert par O(log n) intervalles de majorité .
En d'autres termes, le seul but de intervalles de majorité est de fournir O(log n) candidats d'éléments majoritaires pour tout intervalle de requête.
Cet algorithme utilise les éléments suivants structures de données :
- Liste des postes pour chaque valeur à partir du tableau d'entrée (
map<Value, vector<Position>> ). Ou bien unordered_map peut être utilisé ici pour améliorer les performances (mais nous devrons extraire toutes les clés et les trier pour que la structure n°3 soit remplie dans le bon ordre).
- Liste des intervalles de majorité pour chaque valeur (
vector<Interval> ).
- Structure de données pour le traitement des requêtes (
vector<small_map<Value, Data>> ). Où Data contient deux index du vecteur approprié de la structure #1 pointant vers les positions suivantes/précédentes des éléments avec les valeurs suivantes valeur . Mise à jour : Grâce à @justhalf, il est préférable de stocker en Data les fréquences cumulées des éléments avec des valeur . small_map peut être implémenté comme un vecteur trié de paires - le prétraitement ajoutera les éléments déjà dans l'ordre trié et la requête utilisera la fonction small_map uniquement pour la recherche linéaire.
Prétraitement :
- Scanner le tableau d'entrée et pousser la position actuelle vers le vecteur approprié dans la structure #1.
- Effectuez les étapes 3 4 pour chaque vecteur de la structure #1.
- Transformer une liste de positions en une liste de intervalles de majorité . Voir les détails ci-dessous.
- Pour chaque indice du tableau d'entrée couvert par l'un des éléments suivants intervalles de majorité insérer des données dans l'élément approprié de la structure n° 3 : valeur et les positions des éléments précédents/suivants avec ceci valeur (ou la fréquence cumulée de cette valeur ).
Une requête :
- Si la longueur de l'intervalle de requête est égale à 1, l'élément correspondant du tableau source est renvoyé.
- Pour le point de départ de l'intervalle de requête, on obtient l'élément correspondant du vecteur de la 3ème structure. Pour chaque élément de la carte, effectuer l'étape 3. Scanner tous les éléments de la carte correspondant au point final de l'intervalle de requête en parallèle avec cette carte pour permettre une complexité O(1) pour l'étape 3 (au lieu de O(log log n)).
- Si la carte correspondant au point final de l'intervalle de requête contient des correspondances valeur , calculez
s3[stop][value].prev - s3[start][value].next + 1 . S'il est supérieur à la moitié de l'intervalle d'interrogation, on retourne valeur . Si les fréquences cumulatives sont utilisées à la place des indices suivant/précédent, calculez s3[stop+1][value].freq - s3[start][value].freq à la place.
- Si rien n'est trouvé à l'étape 3, renvoyer "Rien".
Partie principale de l'algorithme est d'obtenir intervalles de majorité de la liste des postes :
- Affecter poids à chaque position dans la liste :
number_of_matching_values_to_the_left - number_of_nonmatching_values_to_the_left .
- Filtre uniquement poids dans un ordre strictement décroissant (avec avidité) vers le tableau "préfixe" :
for (auto x: positions) if (x < prefix.back()) prefix.push_back(x); .
- Filtre uniquement poids dans un ordre strictement croissant (avec avidité, à rebours) vers le tableau "suffixe" :
reverse(positions); for (auto x: positions) if (x > suffix.back()) suffix.push_back(x); .
- Balayez les tableaux "prefix" et "suffix" ensemble et trouvez les intervalles de chaque élément "prefix" à la place correspondante dans le tableau "suffix" et de chaque élément "suffix" à la place correspondante dans le tableau "prefix". (Si le poids de tous les éléments "suffixe" est inférieur à celui de l'élément "préfixe" donné ou si leur position n'est pas à droite de celui-ci, aucun intervalle n'est généré ; s'il n'y a pas d'élément "suffixe" ayant exactement le poids de l'élément "préfixe" donné, trouver l'élément "suffixe" le plus proche ayant un poids plus grand et étendre l'intervalle avec cette différence de poids vers la droite).
- Fusionner les intervalles qui se chevauchent.
Propriétés 1 3 pour intervalles de majorité sont garanties par cet algorithme. Quant à la propriété n°4, la seule façon que je puisse imaginer pour couvrir un élément avec un nombre maximum de intervalles de majorité c'est comme ça : 11111111222233455666677777777 . Ici, l'élément 4 est couvert par 2 * log n intervalles, donc cette propriété semble être satisfaite. Voir la preuve plus formelle de cette propriété à la fin de ce billet.
Exemple :
Pour le tableau d'entrée "0 1 2 0 0 1 1 0", les listes de positions suivantes seraient générées :
value positions
0 0 3 4 7
1 1 5 6
2 2
Positions pour la valeur 0 obtiendra les propriétés suivantes :
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
Positions pour la valeur 1 obtiendra les propriétés suivantes :
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
Structure de données des requêtes :
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
...
Requête [0,4] :
prev[4][0]-next[0][0]+1=2-0+1=3
query size=5
3>2.5, returned result 0
Requête [2,5] :
prev[5][0]-next[2][0]+1=2-1+1=2
query size=4
2=2, returned result "none"
Notez qu'il n'y a aucune tentative d'inspecter l'élément "1" parce que son intervalle majoritaire ne comprend pas l'un ou l'autre de ces intervalles.
Preuve de la propriété n° 4 :
Intervalles de majorité sont construits de telle sorte que strictement plus d'un tiers de tous leurs éléments ont un correspondant valeur . Ce rapport est le plus proche de 1/3 pour les sous-réseaux tels que any*(m-1) value*m any*m par exemple, 01234444456789 .
Pour rendre cette preuve plus évidente, nous pouvons représenter chaque intervalle comme un point en 2D : chaque point de départ possible est représenté par l'axe horizontal et chaque point d'arrivée possible par l'axe vertical (voir le diagramme ci-dessous).
![enter image description here]()
Tous les intervalles valides sont situés sur ou au-dessus de la diagonale. Le rectangle blanc représente tous les intervalles couvrant un élément du tableau (représenté par un intervalle de taille unitaire dans son coin inférieur droit).
Recouvrons ce rectangle blanc de carrés de taille 1, 2, 4, 8, 16, ... partageant le même coin inférieur droit. Cela divise la zone blanche en O(log n) zones similaires à la zone jaune (et un seul carré de taille 1 contenant un seul intervalle de taille 1 qui est ignoré par cet algorithme).
Comptons combien intervalles de majorité peut être placé en zone jaune. Un intervalle (situé le plus près du coin diagonal) occupe 1/4 des éléments appartenant à l'intervalle le plus éloigné du coin diagonal (et ce plus grand intervalle contient tous les éléments appartenant à n'importe quel intervalle de la zone jaune). Cela signifie que le plus petit intervalle contient strictement plus de 1/12e des éléments appartenant à l'intervalle le plus éloigné du coin diagonal. valeurs disponible pour toute la zone jaune. Donc, si nous essayons de placer 12 intervalles dans la zone jaune, nous n'aurons pas assez d'éléments pour les différentes zones. valeurs . La zone jaune ne peut donc pas contenir plus de 11 intervalles de majorité . Et le rectangle blanc ne peut contenir plus de 11 * log n intervalles de majorité . Preuve complétée.
11 * log n est une surestimation. Comme je l'ai dit plus tôt, il est difficile d'imaginer plus que 2 * log n intervalles de majorité couvrant un élément. Et même cette valeur est beaucoup plus grande que le nombre moyen de recouvrement. intervalles de majorité .
Mise en œuvre de C++11. Vous pouvez le voir sur idéone ou ici :
#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;
}
Travail connexe :
Comme indiqué dans autre réponse à cette question Il existe d'autres travaux où ce problème est déjà résolu : "Range majority in constant time and linear space" par S. Durocher, M. He, I Munro, P.K. Nicholson, M. Skala .
L'algorithme présenté dans ce document a une meilleure complexité asymptotique pour le temps d'interrogation : O(1) au lieu de O(log n) et pour l'espace : O(n) au lieu de O(n log n) .
Une meilleure complexité spatiale permet à cet algorithme de traiter des ensembles de données plus importants (par rapport à l'algorithme proposé dans cette réponse). Moins de mémoire nécessaire pour les données prétraitées et un modèle d'accès aux données plus régulier, très probablement, permettent à cet algorithme de prétraiter les données plus rapidement. Mais ce n'est pas aussi facile avec le temps de requête...
Supposons que nous ayons des données d'entrée les plus favorables à l'algorithme de l'article : n=1000000000 (il est difficile d'imaginer un système avec plus de 10..30 gigaoctets de mémoire, en 2013).
L'algorithme proposé dans cette réponse doit traiter jusqu'à 120 (ou 2 limites de requête * 2 * log n) éléments pour chaque requête. Mais il effectue des opérations très simples, similaires à la recherche linéaire. Et il accède séquentiellement à deux zones de mémoire contiguës, ce qui le rend favorable au cache.
L'algorithme de l'article doit effectuer jusqu'à 20 opérations (ou 2 limites de requête * 5 candidats * 2 niveaux d'arbre d'ondelettes) pour chaque requête. C'est 6 fois moins. Mais chaque opération est plus complexe. Chaque requête pour la représentation succincte des compteurs de bits contient elle-même une recherche linéaire (ce qui signifie 20 recherches linéaires au lieu d'une). Le pire, c'est que chacune de ces opérations doit accéder à plusieurs zones de mémoire indépendantes (à moins que la taille de la requête et donc du quadruple soit très petite), ce qui fait que la requête n'est pas favorable au cache. Ce qui signifie que chaque requête (bien qu'il s'agisse d'une opération en temps constant) est assez lente, probablement plus lente que l'algorithme proposé ici. Si nous diminuons la taille du tableau d'entrée, les chances que l'algorithme proposé ici soit plus rapide augmentent.
L'inconvénient pratique de l'algorithme dans le document est l'arbre d'ondelettes et la mise en œuvre succincte du compteur de bits. Les mettre en œuvre à partir de zéro peut prendre beaucoup de temps. L'utilisation d'une implémentation préexistante n'est pas toujours pratique.
