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

223

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.

Luv
la source
10
Algorithme intelligent, utilisant des tas. D'après le titre, je ne pouvais pas immédiatement penser à une solution.
Mooing Duck
1
La solution de vizir me semble bonne, sauf que je supposais (bien que vous n'ayez pas déclaré) que ce flux pourrait être arbitrairement long, donc vous ne pouviez pas tout garder en mémoire. Est-ce le cas?
Running Wild
2
@RunningWild Pour les flux arbitrairement longs, vous pouvez obtenir la médiane des N derniers éléments en utilisant des tas de Fibonacci (pour obtenir des suppressions de journal (N)) et en stockant les pointeurs vers les éléments insérés dans l'ordre (par exemple, un deque), puis en supprimant les plus anciens. élément à chaque étape une fois que les tas sont pleins (peut-être aussi déplacer des choses d'un tas à l'autre). Vous pouvez obtenir un peu mieux que N en stockant le nombre d'éléments répétés (s'il y a beaucoup de répétitions), mais en général, je pense que vous devez faire une sorte d'hypothèses de distribution si vous voulez la médiane de l'ensemble du flux.
Dougal
2
Vous pouvez commencer avec les deux tas vides. Le premier int va dans un tas; la seconde va soit dans l'autre, soit vous déplacez le premier élément vers l'autre tas, puis vous l'insérez. Cela se généralise pour "ne pas autoriser un tas à aller plus grand que l'autre +1" et aucun boîtier spécial n'est nécessaire (la "valeur racine" d'un tas vide peut être définie comme 0)
Jon Watte
J'ai JUSTE obtenu cette question sur une interview MSFT. Merci d'avoir posté
R Claven

Réponses:

383

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.

Hakan Serce
la source
6
Ces tas grandissent sans limite (c'est-à-dire qu'une fenêtre de 100 éléments glissant sur 10 millions d'éléments nécessiterait que les 10 millions d'éléments soient tous stockés en mémoire). Voir ci-dessous pour une autre réponse en utilisant des skiplists indexables qui nécessitent seulement que les 100 éléments les plus récemment vus soient conservés en mémoire.
Raymond Hettinger
1
Vous pouvez également avoir une solution de mémoire bornée utilisant des tas, comme expliqué dans l'un des commentaires de la question elle-même.
Hakan Serce
1
Vous pouvez trouver une implémentation de la solution basée sur le tas en c ici.
AShelly
1
Wow, cela m'a aidé non seulement à résoudre ce problème spécifique, mais m'a également aidé à apprendre des tas ici est mon implémentation de base en python: github.com/PythonAlgo/DataStruct
swati saoji
2
@HakanSerce Pouvez-vous expliquer pourquoi nous avons fait ce que nous avons fait? Je veux dire que je peux voir cela fonctionne, mais je ne suis pas en mesure de le comprendre intuitivement.
shiva
51

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).

Andrew C
la source
3
Si presque tous les nombres sont vus une fois, alors une liste clairsemée prendra encore plus de mémoire. Et il semble plutôt probable que si vous avez tant de nombres qu'ils ne rentrent pas dans le nombre que la plupart des nombres apparaîtront une fois. Malgré cela, il s'agit d'une solution intelligente pour les nombres massifs de nombres.
Mooing Duck
1
Pour une liste clairsemée, je suis d'accord, c'est pire en termes de mémoire. Bien que si les nombres entiers sont distribués au hasard, vous commencerez à obtenir des doublons beaucoup plus tôt que ne le laisse entendre l'intuition. Voir mathworld.wolfram.com/BirthdayProblem.html . Je suis donc presque sûr que cela deviendra effectif dès que vous aurez même quelques Go de données.
Andrew C
4
@AndrewC pouvez-vous expliquer comment il faudra un temps constant pour trouver la médiane. Si j'ai vu n différents types d'entiers, dans le pire des cas, le dernier élément peut être la médiane. Cela rend l'activité médiane de recherche de O (n).
shshnk
@shshnk N n'est-il pas le nombre total d'éléments qui est >>> 2 ^ 35 dans ce cas?
VishAmdi
@shshnk Vous avez raison, le nombre d'entiers différents que vous avez vu est toujours linéaire, comme l'a dit VishAmdi, l'hypothèse que je fais pour cette solution est que n est le nombre de nombres que vous avez vus, ce qui est beaucoup plus grand que 2 ^ 33. Si vous ne voyez pas autant de chiffres, la solution maxheap est certainement meilleure.
Andrew C
49

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.

Colm MacCárthaigh
la source
par curiosité, pourquoi avez-vous besoin de variance?
LazyCat
Le flux peut renvoyer moins d'éléments SIZE que le réservoir à moitié vide. Cela doit être pris en compte lors du calcul de la médiane.
Alex
Existe-t-il un moyen d'accélérer cela en calculant la différence au lieu de la médiane? L'échantillon supprimé et ajouté et la médiane précédente sont-ils suffisamment d'informations pour cela?
inf3rno
30

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.

Hellblazer
la source
2
Count-Min Sketch est meilleur que P ^ 2 en ce qu'il donne également une limite d'erreur alors que ce dernier ne le fait pas.
sinoTrinity
1
Pensez également au «calcul en ligne efficace de l'espace des résumés quantiles» de Greenwald et Khanna, qui donne également des limites d'erreur et a de bonnes exigences en matière de mémoire.
Paul Chernoch
1
Aussi, pour une approche probabiliste, voir cet article de blog: research.neustar.biz/2013/09/16/… et le document auquel il se réfère est ici: arxiv.org/pdf/1407.1121v1.pdf Ceci est appelé "Frugal Streaming "
Paul Chernoch
27

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):

Raymond Hettinger
la source
7
Si je comprends bien cependant, cela ne vous donne qu'une médiane des N derniers éléments vus, pas tous les éléments jusqu'à ce point. Cela semble cependant être une solution vraiment astucieuse pour cette opération.
Andrew C
16
Droite. La réponse semble comme s'il était possible de trouver la médiane de tous les éléments en gardant simplement les n derniers éléments en mémoire - c'est impossible en général. L'algorithme trouve juste la médiane des n derniers éléments.
Hans-Peter Störr
8
Le terme «médiane en cours d'exécution» est généralement utilisé pour désigner la médiane d'un sous - ensemble de données. L'OP est utilisé un terme courant d'une manière non standard.
Rachel Hettinger
18

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.

Irene Papakonstantinou
la source
Comment allez-vous faire ça? "nous supprimons l'élément min de l'arbre de droite"
Hengameh
2
Je voulais dire des arbres de recherche binaires, donc l'élément min est complètement à gauche de la racine.
Irene Papakonstantinou
7

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.

Peter est
la source
1
Dans l'exemple du tas, la recherche est à temps constant, donc je pense que cela devrait être O (N log N + K), mais votre point est toujours valable.
Andrew C
Oui, bon point, éditera cela. Vous avez raison N log N est toujours le terme principal.
Peteris
-2

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.

Bacon Darius
la source
1
Cela ne fonctionne pas: vous pouvez laisser tomber des choses qui se révéleront plus tard près du sommet. Par exemple, essayez votre algorithme avec les nombres de 1 à 100, mais dans l'ordre inverse: 100, 99, ..., 1.
zellyn
Merci, zellyn. Idiot de ma part de me convaincre que l'invariant a été rétabli.
Darius Bacon