- A mediana pode ser encontrada facilmente com ordenação, mas por causa do custo de ordenar, até o problema de selecionar um único elemento fica preso ao limite de O(n log n)
- quickselect explora recursivamente apenas o lado necessário e pode encontrar o k-ésimo elemento ou a mediana em O(n) em média
- Um pivô aleatório funciona bem na prática, mas se continuar escolhendo pivôs ruins, remove apenas um elemento por vez e pode degradar até O(n²)
- median-of-medians escolhe novamente uma mediana a partir das medianas de grupos de 5, permitindo remover pelo menos 30% dos elementos mesmo no pior caso
- Em implementações reais, o custo de calcular o pivô pode ser alto, então o introselect, que combina quickselect e heapselect como na biblioteca padrão do C++, pode ser uma escolha mais prática
Limites de encontrar a mediana com ordenação
- A forma mais simples de calcular a mediana é ordenar a lista e então pegar o valor no índice central
- Em listas com tamanho ímpar, retorna-se o elemento do meio; em listas com tamanho par, retorna-se a média dos dois elementos centrais
- Como a complexidade mais rápida de uma ordenação baseada em comparação é O(n log n), o tempo de execução desse método também é dominado pela ordenação
- A vantagem é que o código é simples, mas ele faz mais trabalho do que o necessário quando se quer encontrar apenas uma mediana
quickselect e o O(n) médio
- quickselect é um algoritmo recursivo criado por Tony Hoare e pode encontrar não só a mediana, mas qualquer k-ésimo elemento de uma lista
- O fluxo básico é dividir a lista com base em um pivô e depois continuar a busca apenas no lado em que está o k-ésimo elemento
- Escolhe-se um pivô (
pivot) da lista
- A lista é dividida em elementos menores ou iguais ao pivô e elementos maiores que o pivô
- Determina-se em qual lado está o k-ésimo elemento procurado e faz-se a chamada recursiva apenas naquela sublista
- Ao descer para a sublista da direita, ajusta-se o valor de
k pelo número de elementos da esquerda que já foram descartados
- Na lista de exemplo
[9,1,0,2,3,4,6,8,7,10,5], como o tamanho é 11, procura-se o 6º menor elemento e, reduzindo o intervalo conforme o pivô, o algoritmo retorna 5 no fim
quickselect_median encontra um único índice central com quickselect quando o tamanho da lista é ímpar e, quando é par, encontra os dois índices centrais e tira a média- Se o pivô dividir a lista quase pela metade, o volume de trabalho será
n + n/2 + n/4 + ... = 2n, o que resulta em O(n)
Para evitar o pior caso, é preciso um bom pivô
- O O(n) médio do quickselect depende da condição de que a escolha do pivô seja suficientemente boa
- Se houver azar e o pivô escolhido em cada etapa for, por exemplo, sempre o valor máximo, apenas um elemento será removido por etapa, levando a O(n²)
- Para garantir tempo linear mesmo no pior caso, é preciso fornecer ao quickselect um pivô suficientemente bom em tempo linear
- Esse algoritmo de escolha de pivô foi desenvolvido em 1973 por Blum, Floyd, Pratt, Rivest e Tarjan, e o artigo relacionado está em 1973 paper
Seleção de pivô com median-of-medians
- median-of-medians é o procedimento para escolher um bom pivô que será usado pelo quickselect
- O fluxo de implementação é o seguinte
- Se houver menos de 5 elementos, usa-se a função tradicional de mediana baseada em ordenação
- A lista é dividida em grupos de 5 elementos
- Grupos incompletos com menos de 5 elementos são descartados para simplificar
- Cada grupo é ordenado e a mediana no índice 2 é coletada
- Em seguida, encontra-se novamente a mediana da lista dessas medianas e ela é retornada como pivô
- Como o tamanho de cada grupo é fixo em 5, a ordenação de cada grupo é tratada como tempo constante e, no total, isso continua sendo um trabalho de O(n)
- A chamada recursiva para encontrar a mediana das medianas entra na análise como um subproblema de tamanho
n/5
Por que é possível remover pelo menos 30%
- Se imaginarmos os grupos de 5 ordenados e dispostos em colunas, e depois ordenarmos novamente suas medianas para escolher a mediana das medianas, dá para analisar a qualidade do pivô
- Mesmo no pior caso, em que o pivô fica o mais deslocado possível para a frente, ainda é garantido que certos quadrantes terão elementos menores ou maiores que o pivô
- Pegando 3 elementos de cada coluna e considerando metade das colunas, é possível remover pelo menos
3/5 * 1/2 * n = 3/10 n elementos
- Proporção garantida de remoção: {p:30}
- O tempo total de execução pode ser expresso pela seguinte recorrência
T(n) = n + T(n/5) + T(7n/10)
- Aqui,
n corresponde ao trabalho de particionamento, T(n/5) ao cálculo de median-of-medians e T(7n/10) à busca recursiva do quickselect
- Como essa recorrência tem dois termos recursivos, não dá para aplicar diretamente o teorema mestre simples, e uma prova por indução é o método mais intuitivo
Resultado da combinação: encontrar a mediana em tempo linear
- O quickselect consegue encontrar a mediana em tempo linear quando recebe um pivô suficientemente bom
- O median-of-medians consegue escolher em O(n) o bom pivô de que o quickselect precisa
- Ao combinar os dois algoritmos, obtém-se um algoritmo para encontrar a mediana ou o n-ésimo elemento de uma lista em tempo linear
Escolhas em implementações reais
- Na prática, escolher um pivô aleatório quase sempre é suficiente
- Embora median-of-medians também seja linear, na prática ele pode ser lento por causa do alto custo de calcular o pivô
- A biblioteca padrão do C++ usa introselect, que combina heapselect e quickselect e tem limite superior de O(n log n)
- O introselect normalmente começa com um algoritmo rápido, mas com limite superior ruim, e muda para um algoritmo mais lento, porém com limite superior melhor, quando não consegue escolher um pivô eficaz
- Na comparação pelo número de elementos examinados pela função quickselect, o pivô determinístico quase sempre considerou menos elementos do que o pivô aleatório, mas essa comparação não inclui o custo de calcular o median-of-medians
- O new paper, publicado em 2017, apresenta um caminho para tornar a abordagem de median-of-medians competitiva com outros algoritmos de seleção
1 comentários
Comentários do Hacker News
Há cerca de 4 anos, comparei vários algoritmos de mediana, e o texto acabou ficando bem mais longo do que eu esperava :)
https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/
Há 10 a 15 anos, eu precisava encontrar regularmente a mediana de bilhões de valores extraídos de itens de log de vários quilobytes. Na época, usávamos MapReduce para processamento em grande escala, e, com esse volume de dados, precisávamos não só de tempo linear, mas, se possível, de uma abordagem distribuída em várias máquinas em uma única passagem
Ajudava saber a precisão e o intervalo dos dados. Os valores eram tempos em milissegundos inteiros, portanto não negativos, e também sabíamos que o percentil 90 ficava bem abaixo de 1 segundo
Normalmente, encontrar a mediana exige algo parecido com ordenação, mas, nessas condições, dá para usar bucket sort. Basta criar um dicionário, isto é, um histograma, com a chave sendo o tempo em milissegundos inteiros e o valor sendo o número de ocorrências
Como não sabíamos o tempo máximo, para evitar que o dicionário explodisse de tamanho, colocávamos todos os valores acima de 999 ms no bucket de 999 ms; assim, tudo ficava limitado a cerca de 2000 inteiros no total, entre chaves e valores de 0 a 999. Essa parte era diferente de um bucket sort comum, era muito fácil de processar em uma única passagem mesmo distribuindo com MapReduce, e depois bastava extrair a mediana do histograma
O número 10.000 foi arbitrário, mas dá para calcular estatisticamente quantas amostras são necessárias para o nível de confiança desejado, e suspeito que não seja um número tão enorme assim
Em alguns sistemas com que trabalhei, o Prometheus parecia impor um limite de cerca de 10 segundos para latência. Então requisições que ultrapassavam esse limite eram todas registradas como 10 segundos, mesmo que na prática pudessem ter demorado mais. Interessante
Em 2017 saiu um novo artigo que tornou a abordagem median-of-medians competitiva com outros algoritmos de seleção, e há um pós-escrito dizendo que o autor do artigo, Andrei Alexandrescu, avisou sobre isso
Ele também fez uma palestra sobre o próprio algoritmo em 2016. Ele é uma pessoa divertida de assistir, recomendo muito
There's Treasure Everywhere - Andrei Alexandrescu
https://www.youtube.com/watch?v=fd1_Miy1Clg
Se você usa software, recomendo assistir e ler todos os textos e palestras do Andrei que conseguir encontrar. Essa palestra também é um verdadeiro tesouro
Na graduação, aprendi o algoritmo median-of-medians quickselect e fiquei muito impressionado. Implementei por conta própria, mas ele era terrivelmente lento. O tempo de execução crescia de forma linear, mas, para isso fazer diferença, a lista teria que ter pelo menos dezenas de bilhões de itens
Conversando sobre isso com um amigo da pós-graduação, ouvi algo como: “Ele é lento, mas o ponto importante é que prova que é possível fazer seleção em uma lista não ordenada em tempo O(n). Houve uma época em que nem se sabia se isso era possível; agora que sabemos que é, pode haver algoritmos lineares mais rápidos também”
Foi uma lição tão simples e ao mesmo tempo profunda que quase me candidatei à pós-graduação. Não sei se esse amigo se lembra dessa conversa, mas foi um momento de virada na minha formação
Também dá para pensar: “como já sabemos que existe algum algoritmo, então também pode existir um mais rápido”. Por que a existência de um algoritmo O(n) seria um sinal mais forte do que a existência de um algoritmo O(n log n)?
Acho que o fator constante desse algoritmo era algo em torno de 22, embora talvez fosse algum algoritmo relacionado
Um dos pontos interessantes do algoritmo median-of-medians é que a lista de autores é completamente estelar
Manuel Blum — vencedor do Prêmio Turing de 1995
Robert Floyd — vencedor do Prêmio Turing de 1978
Ron Rivest — vencedor do Prêmio Turing de 2002
Bob Tarjan — vencedor do Prêmio Turing de 1986 e primeiro vencedor do Prêmio Nevanlinna, em 1982
Vaughan Pratt — o único da lista que não ganhou o Prêmio Turing, mas é professor emérito de Stanford, liderou o projeto SUN antes de ele virar a Sun Microsystems, teve um papel importante no início da Sun como diretor de pesquisa e designer do logotipo da Sun, e deixou várias outras coisas legais, como os certificados de primalidade de Pratt
Quatro Prêmios Turing independentes e ainda uma SPARCstation: este artigo tem de tudo
A lista de autores é realmente impressionante
O “P” do algoritmo KMP também é Pratt
return l[len(l) / 2]Não sou especialista em Python, mas o operador
/em Python não retorna ponto flutuante? Por que não usar divisão inteira,//, em vez de usar um ponto flutuante como índice de array?Talvez não seja problema se o array não for muito grande, mas ainda assim tem bastante cheiro de código ruim. Se fosse um iniciante em Python que não sabia que existem dois operadores separados, até passaria; mas no texto há um código ainda mais estranho que usa divisão inteira em um ramo e divisão de ponto flutuante em outro
def quickselect_median(l, pivot_fn=random.choice):if len(l) % 2 == 1:return quickselect(l, len(l) // 2, pivot_fn)else:return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +quickselect(l, len(l) / 2, pivot_fn))Como já havia 50 comentários e aparentemente ninguém percebeu isso, só reforça meu preconceito anterior sobre a qualidade média do código Python
Acredito que indexar um array com ponto flutuante geraria uma exceção
Em vez de pseudocódigo, escolheram uma linguagem de programação real que parece pseudocódigo, e, para fins explicativos, acredito que o código provavelmente execute bem
Gostei muito de ler o texto original, mas a parte “se escolhermos o maior elemento como pivô em cada etapa, pode virar O(n²) em vez de O(n)” me incomodou
Se a preocupação é entrada adversarial, dá para embaralhar os dados antes em O(n) e impedir que isso seja forçado. Se os dados forem grandes demais para embaralhar, basta misturar uma vez quando os buckets ficarem pequenos o suficiente para serem embaralhados
Se você embaralhou, a probabilidade garante que o pior caso praticamente não aconteça. Se alguém disser que “tecnicamente” é possível, eu responderia que, “tecnicamente”, um atacante também poderia acertar todos os bits de uma chave privada de 256 bits
Nosso mundo é construído sobre probabilidades. Toda chave privada é protegida pela improbabilidade matemática de alguém adivinhá-la exatamente
Pelo que li, quickselect após embaralhamento é, na prática, O(n)
Ainda assim, se você puder confiar na aleatoriedade, a probabilidade de obter tempo de execução acima de O(n) é muito baixa
Floyd-Rivest também faz isso. Se me lembro bem, é um pouco mais eficiente
Mas nunca consegui entender como ele funciona
https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
Ao escolher o n-ésimo elemento, se n for muito pequeno ou muito grande, median-of-medians pode não ser a melhor opção
Em vez disso, dá para usar um pivô enviesado, como em [1], ou uma abordagem que chamo de “j-ésimo de k”. Floyd-Rivest também pode acelerar
Tenho um projeto de hobby que atinge throughput de 1,2 a 2,0 vezes maior em comparação com uma implementação bem feita de quickselect: https://github.com/koskinev/turboselect
Tenho interesse em materiais sobre algoritmos rápidos e genéricos de seleção in-place
[1] https://doi.org/10.4230/LIPIcs.SEA.2017.24
Também é possível usar algoritmos de streaming que calculam uma aproximação de quantis arbitrários sem armazenar todos os dados na memória
Podemos aceitar cálculo aproximado? Que suposições sobre os dados são necessárias para definir o limite de erro? Como verificar se essas suposições continuam válidas?
Pessoalmente, acho que eu tenderia para o algoritmo quickselect do texto original até chegar a uma situação em que fosse realmente necessário considerar uma abordagem de aproximação de mediana em streaming