trouver la médiane dans une fenêtre mobile de taille fixe le long d’une longue séquence de données

O (n * lg m) est facile:

Maintenez simplement votre fenêtre sous la forme de deux std::set s, un pour la moitié inférieure et un pour la moitié supérieure. L’insertion d’un nouvel élément coûte O (lg m), la recherche et le retrait d’un ancien élément coûte la même chose. Déterminer la médiane en utilisant la méthode que vous avez décrite dans votre question coûte 0 (1).

Lorsque vous faites glisser la fenêtre sur votre séquence, à chaque itération, vous supprimez l’élément qui tombe de la fenêtre (O (lg m)), insérez le nouvel élément (O (lg m)) et calculez la médiane (O (1)). , résultant en un total de O (n mg).

Cette solution utilise l’espace O (m), bien sûr, mais je ne pense pas que vous puissiez vous en sortir sans stocker le contenu de la fenêtre.

J’ai implémenté presque exactement l’algorithme que vous décrivez ici: http://ideone.com/8VVEa , et je l’ai décrit ici: Médiane évolutive dans l’implémentation C – Turlach

Pour résoudre le problème de la recherche du plus ancien, vous devez conserver les valeurs dans un tampon circulaire afin de toujours avoir un pointeur sur le plus ancien. Ce que vous stockez dans le tas sont des index de mémoire tampon. L’espace requirejs est donc de 2M, et chaque mise à jour est de 0 (lg M).

Même réponse que hc_ mais au lieu d’utiliser un stock BST, utilisez une version où chaque nœud a le nombre d’éléments dans ce sous-arbre. Cette manière de calculer la médiane est O (log (m)).

J’ai donné cette réponse à la question “médiane évolutive en C”

Je ne pouvais pas trouver une implémentation moderne d’une structure de données c ++ avec des statistiques d’ordre. J’ai donc fini par implémenter les deux idées dans le lien des codeurs supérieurs ( Match Editorial : faites défiler jusqu’à FloatingMedian).

Deux multisets

La première idée divise les données en deux structures de données (tas, multisets, etc.) avec O (ln N) par insertion / suppression ne permet pas de modifier le quantile de manière dynamic sans coût élevé. C’est-à-dire que nous pouvons avoir une médiane ou des 75% glissants, mais pas les deux en même temps.

Arbre de segment

La deuxième idée utilise une arborescence de segments qui est O (ln N) pour les insertions / suppressions / requêtes mais qui est plus flexible. Le meilleur de tous le “N” est la taille de votre plage de données. Donc, si votre médiane mobile a une fenêtre d’un million d’articles, mais que vos données varient du 1..65536, il ne vous faudra que 16 opérations par mouvement de la fenêtre mobile de 1 million !! (Et vous avez seulement besoin de 65536 * sizeof (counting_type) octets, par exemple 65536 * 4).

Arbres statistiques d’ordre GNU

Juste avant d’abandonner, j’ai trouvé que stdlibc ++ contient des arbres de statistiques de commande !!!

Celles-ci ont deux opérations critiques:

 iter = tree.find_by_order(value) order = tree.order_of_key(value) 

Consultez le manuel de libstdc ++ policy_based_data_structures_test (recherchez “split and join”).

J’ai encapsulé l’arborescence pour l’utiliser dans un en-tête pratique pour les compilateurs prenant en charge les typedefs de style c ++ 0x / c ++ 11:

 #if !defined(GNU_ORDER_STATISTIC_SET_H) #define GNU_ORDER_STATISTIC_SET_H #include  #include  // A red-black tree table storing ints and their order // statistics. Note that since the tree uses // tree_order_statistics_node_update as its update policy, then it // includes its methods by_order and order_of_key. template  using t_order_statistic_set = __gnu_pbds::tree< T, __gnu_pbds::null_type, std::less, __gnu_pbds::rb_tree_tag, // This policy updates nodes' metadata for order statistics. __gnu_pbds::tree_order_statistics_node_update>; #endif //GNU_ORDER_STATISTIC_SET_H 

J’attache mon arbre de segment (voir mon autre article) qui permet d’interroger très efficacement la dissortingbution de la fréquence des comptes.

Ceci implémente la structure de données suivante:

 |-------------------------------| |---------------|---------------| |-------|-------|-------|-------| |---|---|---|---|---|---|---|---| 0 1 2 3 4 5 6 7 

Chaque segment conserve le nombre d’éléments de comptage dans la plage qu’il couvre. J’utilise 2N segments pour une plage de valeur de 1..N. Celles-ci sont placées dans un seul vecteur déployé plutôt que dans le format d’arborescence figuré ci-dessus.

Donc, si vous calculez des médianes sur un ensemble d’entiers allant de 1..65536, vous n’avez besoin que de 128 Ko pour les stocker et pouvez insérer / supprimer / interroger en utilisant O (ln N) où N = la taille de la plage soit 2 ** 16 opérations.

C’est un gros gain si la plage de données est beaucoup plus petite que votre fenêtre déroulante.

 #if !defined(SEGMENT_TREE_H) #define SEGMENT_TREE_H #include  #include  #include  #include  #ifndef NDEBUG #include  #endif template class t_segment_tree { static const unsigned cnt_elements = (1 << BITS); static const unsigned cnt_storage = cnt_elements << 1; std::array counts; unsigned count; #ifndef NDEBUG std::multiset elements; #endif public: //____________________________________________________________________________________ // constructor //____________________________________________________________________________________ t_segment_tree(): count(0) { std::fill_n(counts.begin(), counts.size(), 0); } //~t_segment_tree(); //____________________________________________________________________________________ // size //____________________________________________________________________________________ unsigned size() const { return count; } //____________________________________________________________________________________ // constructor //____________________________________________________________________________________ void insert(unsigned x) { #ifndef NDEBUG elements.insert(x); assert("...............This element is too large for the number of BITs!!..............." && cnt_elements > x); #endif unsigned ii = x + cnt_elements; while (ii) { ++counts[ii - 1]; ii >>= 1; } ++count; } //____________________________________________________________________________________ // erase // assumes erase is in the set //____________________________________________________________________________________ void erase(unsigned x) { #ifndef NDEBUG // if the assertion failed here, it means that x was never "insert"-ed in the first place assert("...............This element was not 'insert'-ed before it is being 'erase'-ed!!..............." && elements.count(x)); elements.erase(elements.find(x)); #endif unsigned ii = x + cnt_elements; while (ii) { --counts[ii - 1]; ii >>= 1; } --count; } // //____________________________________________________________________________________ // kth element //____________________________________________________________________________________ unsigned operator[](unsigned k) { assert("...............The kth element: k needs to be smaller than the number of elements!!..............." && k < size()); unsigned ii = 1; while (ii < cnt_storage) { if (counts[ii - 1] <= k) k -= counts[ii++ - 1]; ii <<= 1; } return (ii >> 1) - cnt_elements; } }; #endif