Meu algoritmo favorito: encontrar a mediana em tempo linear (2018)

Encontrando a mediana em O(n log n)

• A forma mais simples é ordenar a lista e depois escolher a mediana
• A complexidade de tempo da ordenação baseada em comparação é O(n log n)
• Exemplo de código:

  def nlogn_median(l):  
      l = sorted(l)  
      if len(l) % 2 == 1:  
          return l[len(l) // 2]  
      else:  
          return 0.5 * (l[len(l) // 2 - 1] + l[len(l) // 2])  
  

Encontrando a mediana em O(n) em média

• É possível encontrar a mediana em tempo linear em média usando o algoritmo "quickselect"

• Algoritmo recursivo desenvolvido por Tony Hoare

• Processo:

  1. Escolha um índice aleatório da lista e defina-o como pivô
  2. Divida a lista em dois grupos com base no pivô:
     • elementos menores ou iguais ao pivô
     • elementos maiores que o pivô
  3. Faça a busca recursiva no grupo que contém a mediana

• Exemplo de código:

  import random  
  
  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))  
  
  def quickselect(l, k, pivot_fn):  
      if len(l) == 1:  
          assert k == 0  
          return l[0]  
  
      pivot = pivot_fn(l)  
      lows = [el for el in l if el < pivot]  
      highs = [el for el in l if el > pivot]  
      pivots = [el for el in l if el == pivot]  
  
      if k < len(lows):  
          return quickselect(lows, k, pivot_fn)  
      elif k < len(lows) + len(pivots):  
          return pivots[0]  
      else:  
          return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)  
  

Prova do O(n) médio

• Quando o pivô divide a lista aproximadamente pela metade, cada chamada recursiva trabalha sobre metade dos dados da etapa anterior
• Prova matemática:

  C = n + n/2 + n/4 + n/8 + ... = 2n = O(n)  
  

O(n) determinístico

• Garante tempo linear mesmo no pior caso

• Usa o algoritmo "median-of-medians" para escolher o pivô

• Processo:

  1. Divida a lista em grupos de 5
  2. Ordene cada grupo e escolha a mediana
  3. Escolha a mediana das medianas como pivô

• Exemplo de código:

  def pick_pivot(l):  
      assert len(l) > 0  
  
      if len(l) < 5:  
          return nlogn_median(l)  
  
      chunks = chunked(l, 5)  
      full_chunks = [chunk for chunk in chunks if len(chunk) == 5]  
      sorted_groups = [sorted(chunk) for chunk in full_chunks]  
      medians = [chunk[2] for chunk in sorted_groups]  
      median_of_medians = quickselect_median(medians, pick_pivot)  
      return median_of_medians  
  
  def chunked(l, chunk_size):  
      return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]  
  

Resumo

• O algoritmo quickselect pode encontrar a mediana em tempo linear quando escolhe um pivô adequado
• O algoritmo median-of-medians é um método de escolha de pivô que garante tempo linear mesmo no pior caso
• Na prática, escolher um pivô aleatório costuma ser eficaz o suficiente

Resumo do GN⁺

• Este texto explica vários algoritmos para encontrar a mediana, com foco especial em como fazer isso em tempo linear
• O algoritmo quickselect é rápido em média, mas o algoritmo median-of-medians pode ser usado para lidar com o pior caso
• Em aplicações reais, escolher um pivô aleatório costuma ser suficiente na maioria dos casos
• Um algoritmo com função semelhante é o introselect, usado na biblioteca padrão de C++

[GN⁺]

Comentários do Hacker News

• Há 4 anos, escrevi um texto longo comparando vários algoritmos de mediana
• Há 10–15 anos, usei MapReduce para encontrar a mediana em entradas de log com dezenas de bilhões de valores
  • Se você souber a precisão e o intervalo dos dados, dá para usar bucket sort
  • Era possível representar os tempos em milissegundos inteiros e gerar um histograma para encontrar a mediana com facilidade
• Em 2017, foi publicado um artigo que tornou a abordagem median-of-medians competitiva com outros algoritmos de seleção
  • Andrei Alexandrescu deu uma palestra sobre esse algoritmo em 2016
• A lista de autores do algoritmo median-of-medians é muito famosa
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt etc.
• O algoritmo de Floyd-Rivest também é eficiente, mas difícil de entender
• Usando algoritmos de streaming, é possível calcular aproximações sem armazenar todos os dados na memória
• Existe uma forma de modificar o quicksort para selecionar a mediana
• Recebi, em uma entrevista, a pergunta sobre encontrar a mediana em uma lista com trilhões de números
  • Usei uma abordagem de definir limites superior e inferior para encontrar a mediana, mas não era o melhor método
  • Havia um método mais eficiente usando um heap de prioridade
  • Depois disso, assinei o LeetCode
• Foi compartilhado um exemplo simples implementado em Go
• Radix sort pode ser usado não só com inteiros, mas também com vários tipos de dados, como strings