Trouver une médiane en cours d’exécution à partir d’un stream d’entiers

Duplication possible:
Algorithme médian roulant en C

Étant donné que les entiers sont lus à partir d’un stream de données. Trouver la médiane des éléments lus de manière efficace.

Solution J’ai lu: Nous pouvons utiliser un tas max sur le côté gauche pour représenter des éléments inférieurs à la médiane effective et un tas minimal sur le côté droit pour représenter des éléments 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 de base du tas comme médiane efficace. Lorsque les tas ne sont pas équilibrés, nous sélectionnons la médiane effective à partir de la racine du tas contenant plus d’éléments.

Mais comment pourrions-nous construire un tas maximum et un tas minimal, par exemple, comment pourrions-nous connaître la médiane effective ici? Je pense que nous devrions insérer 1 élément dans max-heap, puis 1 é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 une médiane courante à partir de données diffusées, je vais en parler brièvement à la toute fin de la réponse.

La question concerne les détails de la solution spécifique (solution de segment de mémoire max heap / min), et explique comment fonctionne la solution basée sur le segment de mémoire:

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 du stream une par une,

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, à n’importe quel 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 une solution médiane à partir d’un stream de données est un problème difficile, et il est probablement impossible de trouver une solution exacte avec des contraintes de mémoire pour le cas général. D’autre part, si les données peuvent présenter certaines caractéristiques, nous pouvons développer des solutions spécialisées efficaces. Par exemple, si nous soaps que les données sont de type intégral, nous pouvons utiliser le sorting par comptage , ce qui peut vous donner un algorithme à temps constant et à 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 requirejse et qu’une approximation est suffisante, vous pouvez simplement essayer d’estimer une fonction de densité de probabilité pour les données et estimer la médiane à l’aide de cette fonction.

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 exige que vous gardiez tous les éléments en mémoire en même temps. Cela n’est pas possible dans la plupart des applications réelles de ce problème.

Au lieu de cela, lorsque vous voyez des nombres, suivez le nombre de fois où vous voyez chaque nombre entier. En supposant des entiers de 4 octets, soit 2 ^ 32 seaux, ou au plus 2 ^ 33 entiers (clé et nombre pour chaque int), soit 2 ^ 35 octets ou 32 Go. Ce sera probablement beaucoup moins que cela parce que vous n’avez pas besoin de stocker la clé ou de compter pour les entrées qui sont 0 (c’est-à-dire comme un defaultdict en python). Cela prend un temps constant pour insérer chaque nouvel entier.

Alors, à tout moment, pour trouver la médiane, utilisez simplement les décomptes pour déterminer quel entier est l’élément du milieu. Cela prend un temps constant (quoique constant, mais néanmoins constant).

Si la variance de l’entrée est dissortingbuée statistiquement (par exemple, normale, log-normale, etc.), l’échantillonnage du réservoir est une manière raisonnable d’estimer les centiles / médianes à partir d’un stream de nombres arbitrairement long.

 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 toutes les entrées - quelle que soit leur taille. Trouver la médiane (ou tout autre percentile) est donc une question simple de sorting du réservoir et de sondage du point intéressant.

Puisque le réservoir est de taille fixe, le sorting peut être considéré comme étant effectivement O (1) - et cette méthode s'exécute à la fois avec une consommation de temps et de mémoire constante.

La méthode la plus efficace pour calculer un percentile d’un stream que j’ai trouvé est l’algorithme P²: Raj Jain, Imrich Chlamtac: l’algorithme P² pour le calcul dynamic des quantiiles et des histogrammes sans stocker d’observations. Commun. ACM 28 (10): 1076-1085 (1985)

L’algorithme est simple à mettre en œuvre et fonctionne extrêmement bien. C’est une estimation, cependant, gardez cela à l’esprit. De l’abstrait:

Un algorithme heuristique est proposé pour le calcul dynamic de la médiane et des autres quantiles. Les estimations sont produites dynamicment à 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 de quantile pouvant être utilisée dans les contrôleurs et enregistreurs indussortingels. L’algorithme est encore étendu au tracé d’histogramme. La précision de l’algorithme est analysée.

Ce problème a une solution exacte qui nécessite seulement que les n éléments les plus récemment vus soient conservés en mémoire. C’est rapide et bien adapté.

Un skiplist indexable prend en charge l’insertion, la suppression et la recherche indexée d’O (ln n) tout en maintenant l’ordre de sorting. Lorsqu’elle est associée à une queue FIFO permettant de suivre 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 pour compléter le code de travail (une version de classe facile à comprendre et une version de générateur optimisée avec le code skiplist indexable en ligne):

Une manière intuitive de penser à cela est que si vous aviez un arbre binary équilibré, la racine serait l’élément médian, car il y aurait le même nombre d’éléments plus petits et plus grands. Maintenant, si l’arbre n’est pas plein, ce ne sera pas tout à fait le cas puisqu’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 binarys é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 stream de données, nous le comparons à la médiane. Si elle est supérieure à 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 droit, 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érez N nombres et K fois vers la fin, vous êtes intéressé par la médiane. La complexité de l’algorithme basé sur le tas serait O (N log N + K).

Considérons l’alternative suivante. Plunk les nombres dans un tableau, et pour chaque requête, exécutez l’algorithme de sélection linéaire (en utilisant le pivot de sorting rapide, par exemple). Maintenant, vous avez un algorithme avec le temps d’exécution O (KN).

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

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

Invariant: Après avoir lu 2*n entrées, le min-heap contient le n plus grand.

Boucle: Lire 2 entrées. Ajoutez-les à la fois au tas et supprimez le min du tas. Cela rétablit l’invariant.

Donc, lorsque 2n entrées ont été lues, le min du tas est le nième plus grand. La moyenne des deux éléments autour de la position médiane et la gestion des requêtes après un nombre impair d’entrées nécessiteront une complication supplémentaire.