Encontre mediana em execução a partir de um fluxo de números inteiros

223

Possível duplicado:
rolando o algoritmo mediano em C

Dado que números inteiros são lidos de um fluxo de dados. Encontre a mediana dos elementos lidos até agora de maneira eficiente.

Solução que li: Podemos usar um heap máximo no lado esquerdo para representar elementos menores que a mediana efetiva e um heap mínimo no lado direito para representar elementos que são maiores que a mediana efetiva.

Após o processamento de um elemento recebido, o número de elementos nos heaps diferem no máximo por 1 elemento. Quando os dois heaps contêm o mesmo número de elementos, encontramos a média dos dados raiz do heap como mediana efetiva. Quando os heaps não estão equilibrados, selecionamos a mediana efetiva da raiz do heap que contém mais elementos.

Mas como construiríamos um heap máximo e um heap mínimo, como saberíamos a mediana efetiva aqui? Eu acho que inseriríamos 1 elemento no max-heap e, em seguida, o próximo 1 elemento no min-heap, e assim por diante para todos os elementos. Corrija-me Se eu estiver errado aqui.

Luv
fonte
10
Algoritmo inteligente, usando pilhas. Do título, não consegui pensar imediatamente em uma solução.
Mooing Duck
1
A solução do vizir parece boa para mim, exceto pelo fato de eu estar assumindo (embora você não tenha declarado) que esse fluxo pode ser arbitrariamente longo, para que você não possa guardar tudo na memória. É esse o caso?
Running Wild
2
@RunningWild Para fluxos arbitrariamente longos, você pode obter a mediana dos últimos N elementos usando heaps Fibonacci (para obter exclusões de log (N)) e armazenando ponteiros para os elementos inseridos em ordem (por exemplo, um deque) e removendo os mais antigos elemento em cada etapa quando os montes estiverem cheios (talvez também mova coisas de um monte para o outro). Você pode ficar um pouco melhor que N armazenando o número de elementos repetidos (se houver muitas repetições), mas, em geral, acho que você precisa fazer algum tipo de suposição distributiva se quiser a mediana de todo o fluxo.
Dougal
2
Você pode começar com os dois montes vazios. Primeiro int entra em uma pilha; O segundo vai para o outro ou você move o primeiro item para o outro heap e insere. Este generaliza a "não permitir que um montão de ir maior do que o outro +1" e sem revestimento especial é necessária (o "valor da raiz" de uma pilha vazia pode ser definido como 0)
Jon Watte
Acabei de receber esta pergunta em uma entrevista do MSFT. Obrigado por postar
R Claven

Respostas:

383

Existem várias soluções diferentes para encontrar a mediana em execução a partir de dados transmitidos; falarei brevemente sobre elas no final da resposta.

A pergunta é sobre os detalhes de uma solução específica (max heap / min heap solution) e como a solução baseada em heap funciona é explicada abaixo:

Para os dois primeiros elementos, adicione um menor ao maxHeap à esquerda e outro maior ao minHeap à direita. Em seguida, processe os dados do fluxo um por um,

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

Então, a qualquer momento, você pode calcular a mediana assim:

   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

Agora vou falar sobre o problema em geral, como prometido no início da resposta. Encontrar mediana em execução a partir de um fluxo de dados é um problema difícil, e encontrar uma solução exata com restrições de memória com eficiência é provavelmente impossível para o caso geral. Por outro lado, se os dados têm algumas características que podemos explorar, podemos desenvolver soluções especializadas eficientes. Por exemplo, se sabemos que os dados são do tipo integral, podemos usar a classificação de contagem, que pode fornecer um algoritmo de tempo constante de memória constante. A solução baseada em heap é uma solução mais geral, porque também pode ser usada para outros tipos de dados (duplos). E, finalmente, se a mediana exata não for necessária e uma aproximação for suficiente, você pode apenas tentar estimar uma função de densidade de probabilidade para os dados e estimar a mediana usando isso.

Hakan Serce
fonte
6
Esses montes crescem sem limites (ou seja, uma janela de 100 elementos deslizando sobre 10 milhões de elementos exigiria que os 10 milhões de elementos fossem armazenados na memória). Veja abaixo outra resposta usando skiplists indexáveis ​​que exigem apenas que os 100 elementos vistos mais recentemente sejam mantidos na memória.
Raymond Hettinger
1
Você também pode ter uma solução de memória limitada usando pilhas, conforme explicado em um dos comentários da pergunta em si.
Hakan Serce
1
Você pode encontrar uma implementação da solução baseada em heap em c aqui.
precisa saber é o seguinte
1
Uau isso ajudou-me não só é resolver este problema específico, mas também me ajudou a aprender montes aqui é minha implementação básico em python: github.com/PythonAlgo/DataStruct
swati Saoji
2
@HakanSerce Você pode explicar por que fizemos o que fizemos? Quero dizer, posso ver isso funcionando, mas não sou capaz de entendê-lo intuitivamente.
shiva
51

Se você não conseguir armazenar todos os itens na memória de uma só vez, esse problema se tornará muito mais difícil. A solução de heap requer que você mantenha todos os elementos na memória de uma só vez. Isso não é possível na maioria das aplicações do mundo real desse problema.

Em vez disso, como você vê os números, acompanhe a contagem do número de vezes que vê cada número inteiro. Assumindo números inteiros de 4 bytes, são 2 ^ 32 buckets, ou no máximo 2 ^ 33 inteiros (chave e contagem para cada int), que são 2 ^ 35 bytes ou 32GB. Provavelmente será muito menor do que isso, porque você não precisa armazenar a chave ou contar para as entradas que são 0 (ou seja, como um padrão no python). Isso leva tempo constante para inserir cada novo número inteiro.

Então, a qualquer momento, para encontrar a mediana, basta usar as contagens para determinar qual número inteiro é o elemento do meio. Isso leva tempo constante (embora uma constante grande, mas constante, no entanto).

Andrew C
fonte
3
Se quase todos os números forem vistos uma vez, uma lista esparsa ocupará ainda mais memória. E parece bastante provável que, se você tiver tantos números, eles não se encaixam no número que a maioria dos números aparecerá uma vez. Apesar disso, esta é uma solução inteligente para contagens massivas de números.
Mooing Duck
1
Para uma lista esparsa, eu concordo, isso é pior em termos de memória. Embora se os números inteiros forem distribuídos aleatoriamente, você começará a receber duplicatas muito antes do que a intuição implica. Consulte mathworld.wolfram.com/BirthdayProblem.html . Portanto, tenho certeza de que isso entrará em vigor assim que você tiver alguns GBs de dados.
Andrew C
4
@ AndrewC, você pode explicar como levará um tempo constante para encontrar a mediana. Se eu vi n tipos diferentes de números inteiros, no pior dos casos, o último elemento pode ser a mediana. Isso faz com que a atividade mediana do achado O (n) seja encontrada.
shshnk
@shshnk Não é o número total de elementos que é >>> 2 ^ 35 neste caso?
VishAmdi #
@shshnk Você está certo que ainda é linear no número de diferentes números inteiros que você viu, como VishAmdi disse, a suposição que estou fazendo para esta solução é que n é o número de números que você viu, o que é muito maior que 2 ^ 33. Se você não vê tantos números, a solução maxheap é definitivamente melhor.
Andrew C
49

Se a variação da entrada for distribuída estatisticamente (por exemplo, normal, log-normal, etc.), a amostragem de reservatório é uma maneira razoável de estimar percentis / medianas a partir de um fluxo arbitrariamente longo de números.

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;
      }
  }
}

"reservatório" é então uma amostra uniforme e regular de todas as entradas - independentemente do tamanho. Encontrar a mediana (ou qualquer percentil) é uma questão direta de classificar o reservatório e pesquisar o ponto interessante.

Como o reservatório é de tamanho fixo, o tipo pode ser considerado efetivamente O (1) - e esse método é executado com tempo constante e consumo de memória.

Colm MacCárthaigh
fonte
por curiosidade, por que você precisa de variação?
lazycat
O fluxo pode retornar menos de elementos SIZE, deixando o reservatório meio vazio. Isso deve ser considerado ao calcular a mediana.
Alex
Existe uma maneira de tornar isso mais rápido calculando a diferença em vez da mediana? A amostra removida e adicionada e a mediana anterior são informações suficientes para isso?
inf3rno 14/04
30

A maneira mais eficiente de calcular um percentil de um fluxo que encontrei é o algoritmo P²: Raj Jain, Imrich Chlamtac: o algoritmo P² para cálculo dinâmico de quantiis e histogramas sem armazenar observações. Comum. ACM 28 (10): 1076-1085 (1985)

O algoritmo é simples de implementar e funciona extremamente bem. É uma estimativa, no entanto, tenha isso em mente. Do resumo:

Um algoritmo heurístico é proposto para o cálculo dinâmico da mediana e de outros quantis. As estimativas são produzidas dinamicamente à medida que as observações são geradas. As observações não são armazenadas; portanto, o algoritmo tem um requisito de armazenamento fixo muito pequeno, independentemente do número de observações. Isso o torna ideal para implementar em um chip quantil que pode ser usado em controladores e gravadores industriais. O algoritmo é estendido ainda mais à plotagem do histograma. A precisão do algoritmo é analisada.

Inferno Blazer
fonte
2
O esboço Count-Min é melhor que P ^ 2, pois também fornece um limite de erro, enquanto o último não.
SinoTrinity
1
Considere também "Computação on-line com eficiência de espaço de resumos quantílicos" de Greenwald e Khanna, que também fornece limites de erro e tem bons requisitos de memória.
Paul Chernoch
1
Além disso, para uma abordagem probabilística, consulte esta postagem no blog: research.neustar.biz/2013/09/16/… e o documento a que se refere está aqui: arxiv.org/pdf/1407.1121v1.pdf Isso é chamado de "Frugal Streaming "
Paul Chernoch
27

Se quisermos encontrar a mediana dos n elementos vistos mais recentemente, esse problema tem uma solução exata que só precisa que os n elementos vistos mais recentemente sejam mantidos na memória. É rápido e escala bem.

Um skiplist indexável suporta a inserção, remoção e pesquisa indexada de O (ln n) de elementos arbitrários enquanto mantém a ordem classificada. Quando acoplado a uma fila FIFO que rastreia a n-ésima entrada mais antiga, a solução é simples:

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]

Aqui estão os links para concluir o código de trabalho (uma versão de classe fácil de entender e uma versão otimizada do gerador com o código do skiplist indexável inline):

Raymond Hettinger
fonte
7
Se estou entendendo corretamente, isso apenas fornece uma mediana dos últimos N elementos vistos, nem todos os elementos até esse ponto. Isso parece uma solução realmente eficiente para essa operação.
Andrew C
16
Certo. A resposta soa como se fosse possível encontrar a mediana de todos os elementos mantendo apenas os últimos n elementos na memória - isso é impossível em geral. O algoritmo apenas encontra a mediana dos últimos n elementos.
Hans-Peter Störr
8
O termo "mediana em execução" é normalmente usado para se referir à mediana de um subconjunto de dados. O OP é usado como um termo comum de maneira não padronizada.
Rachel Hettinger
18

Uma maneira intuitiva de pensar sobre isso é que, se você tivesse uma árvore de pesquisa binária equilibrada completa, a raiz seria o elemento mediano, pois haveria o mesmo número de elementos menores e maiores. Agora, se a árvore não estiver cheia, esse não será o caso, pois haverá elementos ausentes no último nível.

Portanto, o que podemos fazer é ter a mediana e duas árvores binárias balanceadas, uma para elementos menores que a mediana e outra para elementos maiores que a mediana. As duas árvores devem ser mantidas no mesmo tamanho.

Quando obtemos um novo número inteiro do fluxo de dados, o comparamos com a mediana. Se for maior que a mediana, nós a adicionamos à árvore correta. Se os dois tamanhos de árvore diferirem mais de 1, removeremos o elemento min da árvore direita, tornaremos a nova mediana e colocaremos a mediana antiga na árvore esquerda. Da mesma forma para menores.

Irene Papakonstantinou
fonte
Como você irá fazer aquilo? "removemos o elemento min da árvore certa"
Hengameh 14/07/2015
2
Eu quis dizer árvores de pesquisa binária, então o elemento min fica totalmente a partir da raiz.
Irene Papakonstantinou
7

Eficiente é uma palavra que depende do contexto. A solução para esse problema depende da quantidade de consultas realizadas em relação à quantidade de inserções. Suponha que você esteja inserindo N números e K vezes no final do seu interesse pela mediana. A complexidade do algoritmo baseado em heap seria O (N log N + K).

Considere a seguinte alternativa. Plunk os números em uma matriz e, para cada consulta, execute o algoritmo de seleção linear (usando o pivô quicksort, por exemplo). Agora você tem um algoritmo com tempo de execução O (KN).

Agora, se K é suficientemente pequeno (consultas pouco frequentes), o último algoritmo é realmente mais eficiente e vice-versa.

Peter é
fonte
1
No exemplo de heap, a pesquisa é tempo constante, então acho que deve ser O (N log N + K), mas seu argumento ainda é válido.
Andrew C
Sim, bom ponto, irá editar isso. Você está certo N log N ainda é o termo principal.
Peteris
-2

Você não pode fazer isso com apenas uma pilha? Atualização: não. Veja o comentário.

Invariante: Depois de ler as 2*nentradas, o min-heap mantém a nmaior delas.

Loop: Leia 2 entradas. Adicione os dois à pilha e remova o mínimo da pilha. Isso restabelece o invariante.

Portanto, quando as 2nentradas são lidas, o mínimo da pilha é o enésimo maior. Será necessário um pouco de complicação extra para calcular a média dos dois elementos em torno da posição mediana e lidar com consultas após um número ímpar de entradas.

Darius Bacon
fonte
1
Não funciona: você pode soltar coisas que, mais tarde, ficam perto do topo. Por exemplo, tentar a sua algoritmo com os números de 1 a 100, mas em ordem inversa: 100, 99, ..., 1.
zellyn
Obrigado, Zellyn. Tolo de minha parte me convencer de que o invariante foi restabelecido.
Darius Bacon