Mi algoritmo favorito: encontrar la mediana en tiempo lineal (2018)

Encontrar la mediana en O(n log n)

• La forma más simple es ordenar la lista y luego elegir la mediana
• La complejidad temporal de un ordenamiento basado en comparaciones es O(n log n)
• Ejemplo 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])  
  

Encontrar la mediana en O(n) en promedio

• Se puede encontrar la mediana en tiempo lineal promedio usando el algoritmo "quickselect"

• Es un algoritmo recursivo desarrollado por Tony Hoare

• Proceso:

  1. Elegir un índice aleatorio de la lista y usarlo como pivote
  2. Dividir la lista en dos grupos con base en el pivote:
     • elementos menores o iguales al pivote
     • elementos mayores que el pivote
  3. Buscar recursivamente en el grupo que contiene la mediana

• Ejemplo 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)  
  

Demostración del O(n) promedio

• Si el pivote divide la lista aproximadamente por la mitad, cada llamada recursiva trabaja sobre la mitad de los datos de la etapa anterior
• Demostración matemática:

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

O(n) determinista

• Garantiza tiempo lineal incluso en el peor caso

• Usa el algoritmo "median-of-medians" para elegir el pivote

• Proceso:

  1. Dividir la lista en grupos de 5
  2. Ordenar cada grupo y elegir su mediana
  3. Elegir como pivote la mediana de las medianas

• Ejemplo 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)]  
  

Resumen

• El algoritmo quickselect puede encontrar la mediana en tiempo lineal si elige un pivote adecuado
• El algoritmo median-of-medians es un método de selección de pivote que garantiza tiempo lineal incluso en el peor caso
• En la práctica, elegir un pivote aleatorio suele ser suficientemente efectivo

Resumen de GN⁺

• Este artículo explica varios algoritmos para encontrar la mediana, en especial métodos para hacerlo en tiempo lineal
• El algoritmo quickselect es rápido en promedio, pero para cubrir el peor caso se puede usar el algoritmo median-of-medians
• En aplicaciones reales, elegir un pivote aleatorio suele ser suficiente en la mayoría de los casos
• Un algoritmo con funcionalidad similar es introselect, que se usa en la biblioteca estándar de C++

[GN⁺]

Opiniones de Hacker News

• Hace 4 años escribió un artículo largo comparando varios algoritmos de mediana
• Hace 10-15 años, usó MapReduce para encontrar la mediana en entradas de logs con miles de millones de valores
  • Si se conocían la precisión y el rango de los datos, se podía usar ordenamiento por buckets
  • Al expresar los tiempos en milisegundos enteros y generar un histograma, se podía encontrar la mediana fácilmente
• En 2017 se publicó un artículo que hizo competitivo el enfoque de mediana de medianas frente a otros algoritmos de selección
  • Andrei Alexandrescu dio una charla sobre este algoritmo en 2016
• La lista de autores del algoritmo de mediana de medianas es muy reconocida
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt, entre otros
• El algoritmo de Floyd-Rivest también es eficiente, pero difícil de entender
• Con algoritmos de streaming se pueden calcular aproximaciones sin guardar todos los datos en memoria
• Existe una forma de modificar quicksort para seleccionar la mediana
• Recibió como pregunta de entrevista el problema de encontrar la mediana en una lista con billones de números
  • Usó un método de fijar cotas superior e inferior para encontrar la mediana, pero no era la mejor forma
  • Había un método más eficiente usando un heap de prioridad
  • Después empezó una suscripción a LeetCode
• Compartió un ejemplo simple implementado en Go
• Radix sort puede usarse en varios tipos de datos además de enteros, como strings