Trouver la médiane en cours d'exécution à partir d'un flux d'entiers

Duplicata possible:
Algorithme de médiane mobile en C

Étant donné que les entiers sont lus dans un flux de données. Trouvez la médiane des éléments lus jusqu'à présent de manière efficace.

Solution que j'ai lue: nous pouvons utiliser un tas max sur le côté gauche pour représenter les éléments qui sont inférieurs à la médiane effective, et un tas min sur le côté droit pour représenter les éléments qui sont supérieurs à la médiane effective.

Après avoir traité un élément entrant, le nombre d'éléments en tas diffère au maximum de 1 élément. Lorsque les deux tas contiennent le même nombre d'éléments, nous trouvons la moyenne des données racines du tas comme médiane efficace. Lorsque les tas ne sont pas équilibrés, nous sélectionnons la médiane effective dans la racine du tas contenant plus d'éléments.

Mais comment pourrions-nous construire un tas max et un tas min, c'est-à-dire comment pourrions-nous connaître la médiane efficace ici? Je pense que nous insérerions 1 élément dans max-heap puis le prochain élément dans min-heap, et ainsi de suite pour tous les éléments. Corrigez-moi si je me trompe ici.

Il existe un certain nombre de solutions différentes pour trouver la médiane en cours d'exécution à partir de données en streaming, j'en parlerai brièvement à la toute fin de la réponse.

La question concerne les détails d'une solution spécifique (solution de segment de mémoire max / segment de mémoire) et le fonctionnement de la solution basée sur le segment de mémoire est expliqué ci-dessous:

Pour les deux premiers éléments, ajoutez un plus petit au maxHeap à gauche et un plus grand au minHeap à droite. Ensuite, traitez les données de flux un par un,

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

Ensuite, à tout moment, vous pouvez calculer la médiane comme ceci:

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

Je vais maintenant parler du problème en général, comme promis au début de la réponse. Trouver la médiane en cours d'exécution à partir d'un flux de données est un problème difficile, et trouver une solution exacte avec des contraintes de mémoire efficacement est probablement impossible dans le cas général. D'un autre côté, si les données ont certaines caractéristiques que nous pouvons exploiter, nous pouvons développer des solutions spécialisées efficaces. Par exemple, si nous savons que les données sont de type intégral, nous pouvons utiliser le tri par comptage, ce qui peut vous donner un algorithme à temps constant de mémoire constante. La solution basée sur le tas est une solution plus générale car elle peut également être utilisée pour d'autres types de données (doubles). Et enfin, si la médiane exacte n'est pas requise et qu'une approximation suffit, vous pouvez simplement essayer d'estimer une fonction de densité de probabilité pour les données et d'estimer la médiane à l'aide de cela.

Si vous ne pouvez pas conserver tous les éléments en mémoire à la fois, ce problème devient beaucoup plus difficile. La solution de tas vous oblige à conserver tous les éléments en mémoire à la fois. Ce n'est pas possible dans la plupart des applications réelles de ce problème.

Au lieu de cela, comme vous voyez les chiffres, gardez une trace du nombre du nombre de fois que vous voyez chaque entier. En supposant des entiers de 4 octets, cela représente 2 ^ 32 compartiments, ou tout au plus 2 ^ 33 entiers (clé et nombre pour chaque entier), soit 2 ^ 35 octets ou 32 Go. Ce sera probablement beaucoup moins que cela, car vous n'avez pas besoin de stocker la clé ou de compter pour les entrées qui sont 0 (c'est-à-dire comme un défaut par défaut en python). Cela prend un temps constant pour insérer chaque nouvel entier.

Ensuite, à tout moment, pour trouver la médiane, utilisez simplement les nombres pour déterminer quel entier est l'élément central. Cela prend un temps constant (certes une grande constante, mais néanmoins constante).

Si la variance de l'entrée est distribuée statistiquement (par exemple, normale, log-normale, etc.), l'échantillonnage du réservoir est un moyen raisonnable d'estimer les centiles / médianes à partir d'un flux arbitrairement long de nombres.

int n = 0;  // Running count of elements observed so far  
#define SIZE 10000
int reservoir[SIZE];  

while(streamHasData())
{
  int x = readNumberFromStream();

  if (n < SIZE)
  {
       reservoir[n++] = x;
  }         
  else 
  {
      int p = random(++n); // Choose a random number 0 >= p < n
      if (p < SIZE)
      {
           reservoir[p] = x;
      }
  }
}

"réservoir" est alors un échantillon courant, uniforme (juste) de tous les intrants, quelle que soit leur taille. Trouver la médiane (ou n'importe quel percentile) est alors une question simple de trier le réservoir et d'interroger le point intéressant.

Comme le réservoir est de taille fixe, le tri peut être considéré comme étant effectivement O (1) - et cette méthode fonctionne à la fois avec une consommation de temps et de mémoire constante.

Le moyen le plus efficace pour calculer un centile d'un flux que j'ai trouvé est l'algorithme P²: Raj Jain, Imrich Chlamtac: L'algorithme P² pour le calcul dynamique des quantiiles et des histogrammes sans stocker les observations. Commun. ACM 28 (10): 1076-1085 (1985)

L'algorithme est simple à implémenter et fonctionne extrêmement bien. C'est une estimation, cependant, gardez cela à l'esprit. Du résumé:

Un algorithme heuristique est proposé pour le calcul dynamique qf de la médiane et d'autres quantiles. Les estimations sont produites dynamiquement à mesure que les observations sont générées. Les observations ne sont pas stockées; par conséquent, l'algorithme a une exigence de stockage très petite et fixe quel que soit le nombre d'observations. Cela le rend idéal pour l'implémentation dans une puce quantile qui peut être utilisée dans les contrôleurs et enregistreurs industriels. L'algorithme est en outre étendu au tracé d'histogramme. La précision de l'algorithme est analysée.

Si nous voulons trouver la médiane des n derniers éléments vus, ce problème a une solution exacte qui n'a besoin que des n derniers éléments vus pour être gardés en mémoire. Il est rapide et évolue bien.

Un skiplist indexable prend en charge l'insertion, la suppression et la recherche indexée O (ln n) d'éléments arbitraires tout en maintenant l'ordre trié. Lorsqu'elle est couplée à une file d'attente FIFO qui suit la nième entrée la plus ancienne, la solution est simple:

class RunningMedian:
    'Fast running median with O(lg n) updates where n is the window size'

    def __init__(self, n, iterable):
        self.it = iter(iterable)
        self.queue = deque(islice(self.it, n))
        self.skiplist = IndexableSkiplist(n)
        for elem in self.queue:
            self.skiplist.insert(elem)

    def __iter__(self):
        queue = self.queue
        skiplist = self.skiplist
        midpoint = len(queue) // 2
        yield skiplist[midpoint]
        for newelem in self.it:
            oldelem = queue.popleft()
            skiplist.remove(oldelem)
            queue.append(newelem)
            skiplist.insert(newelem)
            yield skiplist[midpoint]

Voici des liens vers le code de travail complet (une version de classe facile à comprendre et une version de générateur optimisée avec le code skiplist indexable en ligne):

• http://code.activestate.com/recipes/576930-efficient-running-median-using-an-indexable-skipli/

• http://code.activestate.com/recipes/577073 .

Une façon intuitive de penser à cela est que si vous aviez un arbre de recherche binaire équilibré complet, alors la racine serait l'élément médian, car il y aurait le même nombre d'éléments de plus en plus petits. Maintenant, si l'arbre n'est pas plein, ce ne sera pas tout à fait le cas car il y aura des éléments manquants au dernier niveau.

Donc, ce que nous pouvons faire à la place, c'est avoir la médiane et deux arbres binaires équilibrés, un pour les éléments inférieurs à la médiane et un pour les éléments supérieurs à la médiane. Les deux arbres doivent être conservés à la même taille.

Lorsque nous obtenons un nouvel entier du flux de données, nous le comparons à la médiane. S'il est supérieur à la médiane, nous l'ajoutons à l'arbre de droite. Si les deux tailles d'arbre diffèrent de plus de 1, nous supprimons l'élément min de l'arbre de droite, en faisons la nouvelle médiane et mettons l'ancienne médiane dans l'arbre de gauche. De même pour les plus petits.

Efficace est un mot qui dépend du contexte. La solution à ce problème dépend de la quantité de requêtes effectuées par rapport à la quantité d'insertions. Supposons que vous insériez N nombres et K fois vers la fin qui vous intéressait dans la médiane. La complexité de l'algorithme basé sur le tas serait O (N log N + K).

Considérez l'alternative suivante. Plongez les nombres dans un tableau et, pour chaque requête, exécutez l'algorithme de sélection linéaire (en utilisant le pivot de tri rapide, par exemple). Vous disposez maintenant d'un algorithme avec le temps d'exécution O (KN).

Maintenant, si K est suffisamment petit (requêtes peu fréquentes), ce dernier algorithme est en fait plus efficace et vice versa.

Tu ne peux pas faire ça avec un seul tas? Mise à jour: non. Voir le commentaire.

Invariant: après avoir lu les 2*nentrées, le min-tas contient le nplus grand d'entre eux.

Boucle: lecture de 2 entrées. Ajoutez-les tous les deux au tas et supprimez le min du tas. Cela rétablit l'invariant.

Ainsi, lorsque les 2nentrées ont été lues, le min du tas est le nième plus grand. Il faudra une petite complication supplémentaire pour faire la moyenne des deux éléments autour de la position médiane et pour gérer les requêtes après un nombre impair d'entrées.