Trouver la médiane courante à partir d'un flux d'entiers [dupliquer]
possibilité de dupliquer:
algorithme de la médiane mobile en C
étant donné que les entiers sont lus à partir d'un flux de données. Trouver la médiane des éléments lus jusqu'à présent de manière efficace.
Solution j'ai lu: Nous pouvons utiliser un tas max sur le côté gauche pour représenter les éléments qui sont moins que la médiane effective, et un tas min sur le côté droit de représenter les éléments qui sont supérieures à la médiane.
après traitement d'un élément entrant, le nombre d'éléments dans les tas diffère tout au plus de 1 élément. Lorsque les deux tas contiennent le même nombre d'éléments, nous trouvons la moyenne des données racine du tas comme médiane efficace. Lorsque le tas ne sont pas équilibrés, nous sélectionnons les efficace médiane à partir de la racine du tas contenant plus d'éléments.
mais comment construire un tas max et min heap c'est-à-dire comment connaîtrions-nous la médiane effective ici? Je pense que nous insérerions un élément dans max-heap, puis un autre dans min-heap, et ainsi de suite pour tous les éléments. Corrigez-moi Si je me trompe ici.
8 réponses
il existe un certain nombre de solutions différentes pour trouver la médiane courante à partir de données en continu, je vais en parler brièvement à la toute fin de la réponse.
la question porte sur les détails de la solution spécifique (max heap / min heap solution), et comment fonctionne la solution basée sur le tas est expliqué ci-dessous:
pour les deux premiers éléments Ajouter un plus petit au maxHeap sur la gauche, et un plus grand au minHeap sur la droite. Ensuite, le processus de les flux de données 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
puis à 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
maintenant je vais parler du problème en général comme promis au début de la réponse. Trouver la médiane courante à partir d'un flux de données est un problème difficile, et trouver une solution exacte avec des contraintes de mémoire efficaces est probablement impossible pour le cas général. D'autre part, si les données ont certaines caractéristiques que nous pouvons exploiter, nous pouvons développer efficace des solutions spécialisées. Par exemple, si nous savons que les données sont un type intégral , alors nous pouvons utiliser counting sort , qui peut vous donner un algorithme de mémoire constante temps. La solution basée sur le tas est une solution plus générale car elle peut être utilisée pour d'autres types de données (doubles). Et enfin, si la médiane exacte n'est pas nécessaire et une approximation est suffisante, vous pouvez simplement essayer d'estimer une probabilité la fonction de densité pour les données et estimer la médiane en utilisant cela.
si vous ne pouvez pas garder tous les objets en mémoire à la fois, ce problème devient beaucoup plus difficile. La solution heap vous demande de garder tous les éléments en mémoire en même temps. Ce n'est pas possible dans la plupart des applications du monde réel de ce problème.
au lieu de cela, comme vous voyez les nombres, gardez la trace du Compter du nombre de fois que vous voyez chaque entier. En supposant 4 nombres entiers de octets, c'est-à-dire 2^32 seaux, ou au plus 2^33 entiers (touche et compte pour chaque int), qui est de 2^35 octets ou 32 Go. Il 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.-à-d. comme un defaultdict en python). Cela prend un temps constant pour insérer chaque nouveau entier.
puis à n'importe quel point, pour trouver la médiane, il suffit d'utiliser les comptes pour déterminer quel entier est l'élément central. Cela prend du temps constant (bien qu'il s'agisse d'une constante importante, mais constante).
si la variance de l'entrée est statistiquement distribuée (par exemple normale , log-normale)... etc) puis l'échantillonnage du réservoir est un moyen raisonnable d'estimer les percentiles / médians à partir d'un cours d'eau 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 une course, uniforme (juste), un échantillon de toutes les entrées - indépendamment de la taille. Trouver la médiane (ou n'importe quel centile) est alors une question simple de trier le réservoir et de sonder le point intéressant.
puisque le réservoir est de taille fixe, le sort peut être considéré comme effectivement O(1) - et cette méthode fonctionne avec le temps constant et la consommation de mémoire.
la manière la plus efficace de calculer un centile d'un flux que j'ai trouvé est l'algorithme P2: Raj Jain, Imrich Chlamtac: L'algorithme P2 pour le calcul dynamique des Quantiiles et des histogrammes sans stocker les Observations. Commun. ACM 28(10): 1076-1085 (1985)
L'algorithme est simple à mettre en œuvre et fonctionne très bien. C'est une estimation, cependant, donc gardez cela à l'esprit. Extrait du résumé:
un algorithme heuristique est proposé pour le calcul dynamique qf la médiane et d'autres quantiles. Les estimations sont produites dynamiquement que les observations sont générés. Les observations ne sont pas stockées; par conséquent, l'algorithme a une très petite et fixe exigence de stockage indépendamment du nombre d'observations. Cela le rend idéal pour la mise en œuvre dans une puce quantile qui peut être utilisé dans les contrôleurs industriels et enregistreurs. L'algorithme est ensuite étendu à histogramme de traçage. La précision de l'algorithme est analysé.
ce problème a une solution exacte qui n'a besoin que des éléments n les plus récents pour être gardés en mémoire. Il est rapide et échelles.
An indexable skiplist supports o(LN n) insertion, suppression, et recherche indexée d'éléments arbitraires tout en maintenant l'ordre trié. Couplée à une file D'attente FIFO qui suit la n-è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 indexable skiplist inlined):
une façon intuitive de penser à cela est que si vous aviez un arbre binaire complètement équilibré, alors 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 du dernier niveau.
donc ce que nous pouvons faire à la place est d'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érieure à la médiane. Les deux arbres doivent être maintenus à la même taille.
lorsque nous obtenons un nouvel entier du flux de données, nous le comparons à la médiane. Si elle est supérieure à la médiane, on l'ajoute à l'arbre de droite. Si les deux tailles d'arbre diffèrent plus de 1, nous enlevons l'élément min de l'arbre droit, en faisons la nouvelle médiane, et mettons l'ancienne médiane dans l'arbre 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 étiez intéressé par la médiane. La complexité de l'algorithme basé sur les tas serait O(N log N + K).
envisager la variante suivante. Plunk les nombres dans un tableau, et pour chaque requête, exécuter l'algorithme de sélection linéaire (en utilisant le quicksort pivot, 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), ce dernier algorithme est en fait plus efficace et vice versa.
vous ne pouvez pas faire ça avec un seul tas? mise à Jour: pas de. Voir le commentaire.
Invariant: après avoir lu 2*n entrées, Le min-tas tient le n le plus grand d'entre eux.
: Lire 2 entrées. Ajoutez les deux au tas, et retirez le tas min. Cela rétablit l'invariant.
ainsi quand 2n entrées ont été lues, Le min de tas est le nième plus grand. Il faut être une petite complication supplémentaire pour faire la moyenne des deux éléments autour de la position médiane et pour traiter les requêtes après un nombre impair d'entrées.