Double Possible:
Rolling médiane de l'algorithme en CÉtant donné que les entiers sont lues à partir d'un flux de données. Trouver la médiane des éléments de lire donc, pour l'efficacité.
La Solution que j'ai lu: On peut l'utiliser un max de tas sur le côté gauche pour représenter des éléments qui sont moins efficaces médiane, et un tas min sur le côté droit de représenter des éléments qui sont plus qu'efficace médiane.
Après le traitement d'un élément entrant, le nombre d'éléments dans le tas diffèrent au plus de 1 élément. Lorsque les deux tas contiennent le même nombre d'éléments, nous prenons la moyenne des tas de racine aussi efficace médiane. Lorsque le tas ne sont pas équilibrés, nous sélectionnons efficace médiane à partir de la racine du tas contenant plus d'éléments.
Mais comment pourrions-nous construire max de tas et de tas min-à-dire comment le saurions-nous de l'effectif médian ici? Je pense que nous avons insert 1 élément au max-tas, et puis la prochaine 1 élément en min tas, à l'instar de ce que nous ferons, pour tous les éléments. Corrigez-moi Si je me trompe ici.
Réponses
Trop de publicités?
Il y a un certain nombre de différentes solutions pour trouver de l'exécution de la médiane à partir des données en streaming, je vais brièvement parler d'eux à la fin de la réponse.
La question est de connaître les détails de la une solution spécifique (tas max/min tas de solution), et comment tas de solution basée sur les œuvres est expliqué ci-dessous:
Pour les deux premiers éléments ajouter de la plus petite à la maxHeap sur la gauche, et plus grand pour la minHeap sur la droite. Ensuite, processus de 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 à un moment donné, vous pouvez calculer la médiane comme ceci:
If the heaps contain equal elements;
median = (root of maxHeap + root of minHeap)/2
Else
median = root of the heap with more elements
Maintenant, je vais parler en général, le problème, comme promis, le début de la question. Trouver exécutant la médiane à partir d'un flux de données est un problème difficile, et de trouver une solution exacte avec les contraintes de mémoire de manière efficace 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 est une partie intégrante de type, alors nous pouvons utiliser le comptage de tri, qui peut vous donner une constante de la mémoire de la constante de temps de l'algorithme. Tas en fonction de la solution est plus générale de la solution, car il peut être utilisé pour d'autres types de données (en double). Et enfin, si la médiane exacte n'est pas nécessaire et une approximation est suffisante, vous pouvez juste essayer d'estimer une fonction de densité de probabilité pour les données et l'estimation médiane de l'aide que.
Si la variance de l'entrée est statistiquement la distribution (par exemple, normale , log-normale, etc...) alors réservoir d'échantillonnage est une façon raisonnable de l'estimation des percentiles/médianes d'un arbitrairement long flot 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 tout percentile) est alors une simple question de tri le réservoir et l'interrogation sur le point intéressant.
Depuis le réservoir est de taille fixe, le tri peut être considéré comme efficace O(1) - et cette méthode fonctionne avec les deux constantes de temps de la consommation de mémoire.
Si vous ne pouvez pas contenir tous les éléments en mémoire à la fois, ce problème devient beaucoup plus difficile. Le tas solution exige de vous avoir tous les éléments en mémoire à la fois. Ce n'est pas possible dans la plupart des applications du monde réel de ce problème.
Au lieu de cela, comme vous le voyez numéros, de garder trace de compter le nombre de fois que vous voyez chaque entier. En supposant que 4 octets entiers, c'est 2^32 seaux, ou tout au plus 2^33 entiers (clé et le nombre de chaque type 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 le compte de ces entrées sont à 0 (c'est à dire. comme un defaultdict en python). Cela prend un temps constant pour insérer chaque nouveau entier.
Ensuite, à tout moment, pour trouver la médiane, il suffit d'utiliser le compte pour déterminer le nombre entier est le milieu de l'élément. Cela prend un temps constant (bien qu'une grande constante, mais constante, néanmoins).
Le moyen le plus efficace pour calculer un rang centile d'un ruisseau que j'ai trouvé est le P2 algorithme: Raj Jain, internet imrich Chlamtac: P2 Algorithme pour le Calcul Dynamique de la Quantiiles des Histogrammes et 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. De l'abstrait:
Un algorithme heuristique est proposée pour le calcul dynamique qf de 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 est très petite, et fixe les exigences de stockage, indépendamment du nombre d'observations. Cela le rend idéal pour la mise en œuvre dans un quantile de la puce qui peuvent être utilisés dans l'industrie des contrôleurs et des enregistreurs. L'algorithme est de plus en plus à l'histogramme de traçage. La précision de l'algorithme est analysé.
Ce problème a une solution exacte qui a seulement besoin de n plus récemment vu des éléments à être conservés en mémoire. Il est rapide et échelles.
Un indexables skiplist prend en charge O(ln n) d'insertion, de suppression, et indexé de recherche de l'arbitraire des éléments tout en conservant l'ordre de tri. Lorsqu'il est couplé avec une file d'attente FIFO qui suit la n-iè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 des code de travail (un facile-à-comprendre la version de la classe et une optimisation du générateur de version avec la fraise skiplist code inline):
