Algoritmo não trivial para calcular uma mediana da janela deslizante

25

Preciso calcular a mediana em execução:

  • Entrada: n , k , vetor .(x1,x2,,xn)

  • Saída: vetor , em que é a mediana de .y i ( x i , x i + 1 , , x i + k - 1 )(y1,y2,,ynk+1)yi(xi,xi+1,,xi+k1)

(Sem trapacear com aproximações; eu gostaria de ter soluções exatas. Os elementos são números inteiros grandes.)xi

Existe um algoritmo trivial que mantém uma árvore de pesquisa de tamanho ; o tempo total de execução é . (Aqui, uma "árvore de pesquisa" refere-se a alguma estrutura de dados eficiente que suporta inserções, exclusões e consultas medianas em tempo logarítmico.)O ( n log k )kO(nlogk)

No entanto, isso me parece um pouco estúpido. Aprenderemos efetivamente todas as estatísticas de pedidos em todas as janelas de tamanho , não apenas nas medianas. Além disso, na prática, isso não é muito atraente, especialmente se for grande (grandes árvores de pesquisa tendem a ser lentas, a sobrecarga no consumo de memória não é trivial, a eficiência do cache geralmente é baixa etc.).kkk

Podemos fazer algo substancialmente melhor?

Existem limites mais baixos (por exemplo, o algoritmo trivial é assintoticamente ideal para o modelo de comparação)?


Edit: David Eppstein deu um bom limite inferior para o modelo de comparação! Gostaria de saber se, no entanto, é possível fazer algo um pouco mais inteligente do que o algoritmo trivial?

Por exemplo, poderíamos fazer algo nesse sentido: dividir o vetor de entrada em partes do tamanho ; classifique cada parte (mantendo o controle das posições originais de cada elemento); e, em seguida, use o vetor classificado por partes para encontrar as medianas em execução de maneira eficiente sem nenhuma estrutura de dados auxiliar? É claro que isso ainda seria , mas, na prática, as matrizes de classificação tendem a ser muito mais rápidas do que manter as árvores de pesquisa.O ( n log k )kO(nlogk)


Edit 2: Saeed queria ver algumas razões pelas quais eu acho que a classificação é mais rápida do que as operações da árvore de pesquisa. Aqui estão referências muito rápidas, para , : n = 10 8k=107n=108

  • ≈ 8s: classificando vetores com elementos cadakn/kk
  • ≈ 10s: classificando um vetor com elementosn
  • Anos 80: inserções e exclusões em uma tabela de tamanhonk
  • ≈ 390s: inserções e exclusões em uma árvore de pesquisa equilibrada de tamanhoknk

A tabela de hash está lá apenas para comparação; não é de uso direto nesta aplicação.

Em resumo, temos quase uma diferença de fator 50 no desempenho da classificação versus operações equilibradas da árvore de pesquisa. E as coisas pioram se aumentarmos .k

(Detalhes técnicos: Dados = inteiros aleatórios de 32 bits. Computador = um laptop moderno típico. O código de teste foi escrito em C ++, usando as rotinas de biblioteca padrão (std :: sort) e estruturas de dados (std :: multiset, std :: Eu usei dois compiladores C ++ diferentes (GCC e Clang) e duas implementações diferentes da biblioteca padrão (libstdc ++ e libc ++). Tradicionalmente, std :: multiset era implementado como uma árvore vermelho-preta altamente otimizada.

Jukka Suomela
fonte
1
Eu não acho que você vai ser capaz de melhorar . A razão é, se você olhar para uma janela x t , . . . , x t + k -nlogk , você nunca pode descartar nenhum dos números x t + kxt,...,xt+k1 de ser mediana da janela futura. Isso significa que, a qualquer momento, você deve manter pelo menos kxt+k2,...,xt+k1 inteiros em uma estrutura de dados e parece não ser atualizada em menos de tempo de log. k2
RB
Seu algoritmo trivial para mim parece ser não O ( n log k ) , estou entendendo algo errado? E eu acho que por causa disso você tem problemas com o grande k , caso contrário, o fator logarítmico não é nada em aplicações práticas, também não há grande constante oculta nesse algoritmo. O((nk)klogk)O(nlogk)k
Saeed
@ Saeed: No algoritmo trivial, você processa os elementos um por um; no passo i você adiciona à árvore de pesquisa e (se i > k ) também remove x i - k da árvore de pesquisa. São n etapas, cada uma das quais leva tempo O ( log k ) . xii>kxiknO(logk)
Jukka Suomela 24/03
Quer dizer que você tem uma árvore de pesquisa equilibrada e não uma árvore de pesquisa casual?
Saeed
1
@ Saeed: Observe que, nos meus benchmarks, nem tentei encontrar medianas. Acabei de fazer inserções e n exclusões em uma árvore de pesquisa de tamanho k , e é garantido que essas operações levem tempo O ( log k ) . Você só precisa aceitar que as operações da árvore de pesquisa são muito lentas na prática, em comparação com a classificação. Você verá isso facilmente se tentar escrever um algoritmo de classificação que funcione adicionando elementos a uma árvore de pesquisa balanceada - ele certamente funciona em O ( n log n ) , mas será ridiculamente lento na prática e também desperdiçará muito. de memória. nnkO(logk)O(nlogn)
Jukka Suomela

Respostas:

32

Aqui está um limite inferior da classificação. Dado um conjunto de entrada de comprimento n a ser classificado, crie uma entrada para o seu problema mediano em execução que consiste em n - 1 cópias de um número menor que o mínimo de S , depois S em si e, em seguida, n - 1 cópias de um número maior que o máximo de S e defina k = 2Snn1SSn1S . As medianas de execução deste entrada são o mesmo que a ordem de classificação de S .k=2n1S

Assim, em um modelo de comparação de computação, é requerido tempo. Possivelmente, se suas entradas forem inteiras e você usar algoritmos de classificação inteira, poderá fazer melhor.Ω(nlogn)

David Eppstein
fonte
6
Essa resposta realmente me faz pensar se o inverso também é válido: dado um algoritmo de classificação eficiente, obtemos um algoritmo mediano de execução eficiente? (Por exemplo, faz no algoritmo inteiro triagem eficiente implica em correr algoritmo mediano eficiente para inteiros Ou faz um algoritmo de classificação IO-eficiente fornecer um correndo algoritmo mediano IO-eficientes?)
Jukka Suomela
1
Mais uma vez, muito obrigado pela sua resposta, ele realmente me colocou no caminho certo e inspirou o algoritmo de filtro mediano baseado em classificação! No final, pude encontrar um artigo de 1991 que apresentasse basicamente o mesmo argumento que você apresenta aqui, e Pat Morin apontou para outro artigo relevante de 2005; veja refs. [6] e [9] aqui .
Jukka Suomela
9

Edit: Este algoritmo agora é apresentado aqui: http://arxiv.org/abs/1406.1717


Sim, para resolver esse problema, é suficiente executar as seguintes operações:

  • Classifique vetores, cada um com k elementos.n/kk
  • Pós-processamento em tempo linear.

Muito grosso modo, a ideia é esta:

  • Considere dois blocos adjacentes de entrada, e b , ambos com elementos k ; deixar os elementos ser um 1 , um 2 , . . . , Um k eabka1,a2,...,ak na ordem de aparência no vetor de entrada xb1,b2,...,bkx .
  • Classifique esses blocos e aprenda a classificação de cada elemento dentro do bloco.
  • Aumentar os vectores de e b com ponteiros predecessor / sucessor de modo que, seguindo as cadeias ponteiro que pode atravessar os elementos em ordem crescente. Desta forma, temos construído duplamente listas ligadas a ' e b ' .abab
  • Um por um, exclua todos os elementos da lista vinculada , na ordem inversa da aparência b kb . Sempre que excluirmos um elemento,lembre-se de qual foi seu sucessor e predecessor no momento da exclusão.bk,bk1,...,b1
  • Agora manter "ponteiros medianos" e q que apontam para listas de um ' e b ' , respectivamente. Inicialize p no ponto médio de a ' e inicialize q no final da lista vazia b ' .pqabpaqb
  • Para cada :i

    • Exclua da lista a ' (é hora O ( 1 ) , apenas exclua da lista vinculada). Comparar um i com o elemento apontado por p para ver se excluído antes ou depois p .aiaO(1)aipp
    • Coloque volta à lista b em sua posição original (este é o tempo O ( 1 ) , memorizamos o antecessor e sucessor debibO(1)bibiqq .
    • pqabpqO(1)pqpq

k


Aqui está um exemplo de implementação e benchmarks:

n2106

  • O(nlogk) .
  • O(nlogk) , implementação em https://github.com/craffel/median-filter
  • O(nlogk) .
  • O(nk) .
  • k/2 ).
  • Eixo Y = tempo de execução em segundos.
  • Dados = números inteiros de 32 bits e números aleatórios de 64 bits, de várias distribuições.

tempos de execução

Jukka Suomela
fonte
3

mO(nlogm+mlogn)

O(logm)O(logn)O(logn) a cobrança ocorre apenas uma vez por mediana.

O(nlogm+mlogk)

Geoffrey Irving
fonte
Ops, isso não funciona como está escrito, pois se você não excluir elementos, as contagens não refletirão a nova janela. Não tenho certeza se isso pode ser corrigido, mas deixarei a resposta caso haja uma maneira.
Geoffrey Irving
O(nlogm)
nota lateral: A pergunta não está clara, a estrutura de dados subjacente não está definida, apenas sabemos algo muito vago. como você quer melhorar algo que você não sabe o que é? como você deseja comparar sua abordagem?
Saeed
1
Peço desculpas pelo trabalho incompleto. Fiz a pergunta concreta necessária para corrigir esta resposta aqui: cstheory.stackexchange.com/questions/21778/… . Se você achar apropriado, posso remover esta resposta até que a questão secundária seja resolvida.
Geoffrey Irving