Preciso calcular a mediana em execução:
Entrada: , , vetor .
Saída: vetor , em que é a mediana de .y i ( x i , x i + 1 , … , x i + k - 1 )
(Sem trapacear com aproximações; eu gostaria de ter soluções exatas. Os elementos são números inteiros grandes.)
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 )
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.).k
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 )
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 8
- ≈ 8s: classificando vetores com elementos cadak
- ≈ 10s: classificando um vetor com elementos
- Anos 80: inserções e exclusões em uma tabela de tamanho
- ≈ 390s: inserções e exclusões em uma árvore de pesquisa equilibrada de tamanhok
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 .
(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.
fonte
Respostas:
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 = 2S n n−1 S S n−1 S . As medianas de execução deste entrada são o mesmo que a ordem de classificação de S .k=2n−1 S
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)
fonte
Edit: Este algoritmo agora é apresentado aqui: http://arxiv.org/abs/1406.1717
Sim, para resolver esse problema, é suficiente executar as seguintes operações:
Muito grosso modo, a ideia é esta:
Para cada :i
Aqui está um exemplo de implementação e benchmarks:
fonte
fonte