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

 (rcoh.me)
2 puntos por GN⁺ 2024-07-26 | 1 comentarios | Compartir por WhatsApp
  • La mediana puede obtenerse fácilmente si se ordena la lista, pero el costo de ordenar la deja atada al límite de O(n log n) incluso para el problema de seleccionar un solo elemento
  • quickselect explora recursivamente solo el lado necesario, por lo que puede encontrar el elemento k-ésimo o la mediana en O(n) en promedio
  • Un pivote aleatorio funciona bien en la práctica, pero si se siguen eligiendo pivotes malos, solo se elimina un elemento por vez y el rendimiento puede degradarse hasta O(n²)
  • median-of-medians vuelve a elegir una mediana a partir de las medianas de grupos de 5 elementos, lo que permite eliminar al menos 30% de los elementos incluso en el peor caso
  • En implementaciones reales, el costo de calcular el pivote puede ser alto, por lo que introselect, que combina quickselect y heapselect como en la biblioteca estándar de C++, puede ser una opción más práctica

Límites de encontrar la mediana ordenando

  • La forma más simple de calcular la mediana es ordenar la lista y luego tomar el valor del índice central
  • En una lista de longitud impar se devuelve el elemento del medio, y en una de longitud par se devuelve el promedio de los dos elementos centrales
  • Como la complejidad temporal más rápida de los algoritmos de ordenamiento basados en comparación es O(n log n), el tiempo de ejecución de este método queda dominado por el ordenamiento
  • Tiene la ventaja de que el código es simple, pero hace más trabajo del necesario si solo se quiere encontrar una única mediana

quickselect y cómo logra O(n) en promedio

  • quickselect es un algoritmo recursivo creado por Tony Hoare, y puede encontrar no solo la mediana sino cualquier elemento k-ésimo de una lista
  • El flujo básico consiste en dividir la lista con respecto a un pivote y seguir explorando solo el lado que contiene el elemento k-ésimo
    • Se elige un pivote de la lista
    • La lista se divide en elementos menores o iguales al pivote y elementos mayores que el pivote
    • Se determina en qué lado está el elemento k-ésimo buscado y se hace la llamada recursiva solo sobre esa sublista
    • Al bajar a la sublista derecha, el valor de k se ajusta según la cantidad de elementos de la izquierda que ya fueron descartados
  • En la lista de ejemplo [9,1,0,2,3,4,6,8,7,10,5], como la longitud es 11, se busca el 6.º elemento más pequeño y, reduciendo el rango según el pivote, finalmente se devuelve 5
  • quickselect_median busca con quickselect un único índice central si la longitud de la lista es impar, y si es par busca los dos índices centrales y calcula su promedio
  • Si el pivote divide la lista casi por la mitad en cada paso, el trabajo total es n + n/2 + n/4 + ... = 2n, por lo que resulta en O(n)

Para evitar el peor caso hace falta un buen pivote

  • El O(n) promedio de quickselect depende de la condición de que la elección del pivote sea suficientemente buena
  • Si se tiene mala suerte y en cada paso se elige, por ejemplo, el valor máximo como pivote, solo se elimina un elemento por etapa y el tiempo se vuelve O(n²)
  • Para garantizar tiempo lineal incluso en el peor caso, quickselect necesita recibir un pivote suficientemente bueno en tiempo lineal
  • Este algoritmo de selección de pivote fue desarrollado en 1973 por Blum, Floyd, Pratt, Rivest y Tarjan, y el artículo correspondiente está enlazado como 1973 paper

Selección de pivote con median-of-medians

  • median-of-medians es el procedimiento para elegir un buen pivote que quickselect pueda usar
  • El flujo de implementación es el siguiente
    • Si hay menos de 5 elementos, se usa la función existente de mediana basada en ordenamiento
    • La lista se divide en grupos de 5 elementos
    • Los grupos incompletos con menos de 5 elementos se descartan para simplificar
    • Se ordena cada grupo y se recolecta la mediana del índice 2
    • Luego se vuelve a buscar la mediana de la lista de medianas recolectadas y se devuelve como pivote
  • Como el tamaño de cada grupo está fijado en 5, el ordenamiento por grupo se considera tiempo constante y en total es una tarea de O(n)
  • La llamada recursiva para encontrar la mediana de las medianas se incluye en el análisis como un subproblema de tamaño n/5

Por qué se puede eliminar al menos 30%

  • Si se ordenan los grupos de 5 y se colocan como columnas, luego se ordenan de nuevo sus medianas y se elige la mediana de esas medianas, se puede analizar la calidad del pivote
  • Incluso en el peor caso, cuando el pivote está sesgado lo más posible hacia un extremo, se garantiza que los elementos de cierto cuadrante serán menores o mayores que el pivote
  • Tomando 3 elementos de cada columna y considerando la mitad de las columnas, se pueden eliminar al menos 3/5 * 1/2 * n = 3/10 n elementos
  • Proporción garantizada de eliminación: {p:30}
  • El tiempo total de ejecución se expresa con la siguiente recurrencia
T(n) = n + T(n/5) + T(7n/10)
  • Aquí, n corresponde al trabajo de partición, T(n/5) al cálculo de median-of-medians y T(7n/10) a la exploración recursiva de quickselect
  • Como esta recurrencia tiene dos términos recursivos, no se puede aplicar directamente el teorema maestro simple, y una prueba por inducción es la forma más intuitiva de demostrarlo

Resultado de la combinación: mediana en tiempo lineal

  • quickselect puede encontrar la mediana en tiempo lineal si recibe un pivote suficientemente bueno
  • median-of-medians puede elegir en O(n) el buen pivote que quickselect necesita
  • Al combinar ambos algoritmos se obtiene un algoritmo que encuentra la mediana o el elemento n-ésimo de una lista en tiempo lineal

La elección en implementaciones reales

  • En la práctica, elegir un pivote aleatorio casi siempre es suficiente
  • Aunque median-of-medians también es lineal, en la realidad puede ser lento porque el costo de calcular el pivote es alto
  • La biblioteca estándar de C++ usa introselect, que combina heapselect y quickselect y tiene una cota superior de O(n log n)
  • introselect por lo general es rápido, pero comienza con un algoritmo veloz cuya cota superior es peor y cambia a otro más lento pero con mejor cota cuando no logra elegir pivotes efectivos
  • En la comparación por cantidad de elementos examinados por la función quickselect, el pivote determinista casi siempre consideró menos elementos que el pivote aleatorio, pero esa comparación no incluye el costo de calcular median-of-medians
  • Un new paper publicado en 2017 presenta un enfoque que hace que median-of-medians pueda competir con otros algoritmos de selección

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-07-26
Comentarios en Hacker News

  • Hace unos 4 años comparé varios algoritmos de mediana, y el texto terminó siendo mucho más largo de lo esperado :)
    https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/

    • Entre ellos, ¿hay alguno que se pueda adaptar fácilmente para devolver el arg-median, es decir, el índice que contiene la mediana?

  • Hace unos 10~15 años, tenía que encontrar regularmente la mediana de miles de millones de valores extraídos de entradas de log de varios kilobytes. En ese entonces, para procesamiento a gran escala usábamos MapReduce, y con ese volumen de datos no solo se necesitaba tiempo lineal, sino también, si era posible, un método distribuible en varias máquinas en una sola pasada
    Ayudaba conocer la precisión y el rango de los datos. Los valores eran tiempos en milisegundos enteros, así que no eran negativos, y también sabíamos que el percentil 90 estaba muy por debajo de 1 segundo
    Normalmente encontrar la mediana requiere un trabajo parecido a ordenar, pero en estas condiciones se podía usar bucket sort. Bastaba con construir un diccionario donde la clave fuera el tiempo entero en milisegundos y el valor fuera la cantidad de apariciones, es decir, un histograma
    Como no conocíamos el tiempo máximo, para evitar que el diccionario creciera de forma explosiva, todos los valores mayores a 999ms se colocaban en el bucket de 999ms, y así quedaba limitado a unas 2000 enteros en total entre claves 0~999 y sus valores. Esa parte era distinta del bucket sort usual, y hasta distribuido con MapReduce se podía procesar muy fácilmente en una sola pasada; después solo quedaba extraer la mediana del histograma

    • ¿De verdad necesitaban la mediana exacta de miles de millones de valores? ¿O bastaba con cualquier valor entre 49.9% y 50.1%? Si era lo segundo, era mucho más fácil. Bastaba con tomar una muestra aleatoria uniforme de 10,000 y usar la mediana de esa muestra
      El número 10,000 es solo un ejemplo arbitrario, pero la cantidad de muestras necesaria para el nivel de confianza deseado se puede calcular estadísticamente, y no creo que tenga que ser tan grande
    • No estoy seguro, pero visto desde fuera, se parece a lo que Prometheus hace internamente
      En algunos de los sistemas que manejé, Prometheus parecía comportarse como si impusiera un límite de latencia de unos 10 segundos. Entonces, cualquier solicitud que superara ese límite entraba como 10 segundos, aunque en realidad pudiera tardar más. Interesante
    • ¿Casualmente estabas construyendo una métrica de disponibilidad y eras becario en ese momento? Ese sistema me suena, eh, muy familiar
    • No entiendo por qué usaste un diccionario con claves 0…999. ¿No habría sido mejor usar un arreglo indexado de 0…999?

  • En 2017 salió un nuevo artículo que volvió competitivo el enfoque de median-of-medians frente a otros algoritmos de selección, y hay una posdata diciendo que el propio autor del artículo, Andrei Alexandrescu, se lo hizo saber
    También dio una charla sobre su algoritmo en 2016. Es un expositor muy entretenido, la recomiendo mucho
    There's Treasure Everywhere - Andrei Alexandrescu
    https://www.youtube.com/watch?v=fd1_Miy1Clg

    • Andrei Alexandrescu es increíble. Alrededor del 2000 presentó algoritmos lock-free y wait-free, y los apliqué de inmediato en un enorme proyecto de redes de control industrial en C++
      Si trabajas con software, te recomiendo escuchar y leer todo lo de Andrei que puedas encontrar. Esta charla también es una verdadera joya
    • Me sorprende que sea una persona tan erudita, incluso para los estándares de la informática. Lo conocía por la metaprogramación con templates, pero aquí se está moviendo de los lenguajes de programación hacia los algoritmos

  • En la licenciatura aprendí el algoritmo median-of-medians quickselect y me impresionó muchísimo. Lo implementé por mi cuenta, pero era terriblemente lento. El tiempo de ejecución sí crecía de forma lineal, pero para que eso importara la lista tenía que tener al menos miles de millones de elementos
    Hablando de esto con un amigo de posgrado, me dijo algo como: “Sí, es lento, pero lo importante es que demuestra que se puede seleccionar en tiempo O(n) sobre una lista no ordenada. Hubo un tiempo en que ni siquiera sabíamos si eso era posible; ahora que sabemos que sí lo es, también podría haber algoritmos lineales más rápidos”
    Era una lección tan simple y a la vez tan profunda que casi me hace postular a posgrado. No sé si ese amigo recordará esa conversación, pero para mí fue como un punto de inflexión en mi formación

    • ¿El hecho de que exista un algoritmo de tiempo lineal sugiere la existencia de un algoritmo de tiempo lineal más rápido? Si no es así, ¿qué ganancia aporta ese conocimiento?
      También podría pensarse: “Como ya sabemos que existe algún algoritmo, entonces podría haber otros más rápidos”. ¿Por qué la existencia de un algoritmo O(n) sería una señal más fuerte que la existencia de uno O(n log n)?
    • Creo que aprendí este algoritmo en cuarto año de informática. Como dices, también se veía su lado teórico, pero además se usaba como ejemplo de que, en la mayoría de los casos reales, un algoritmo lineal lento no supera a un algoritmo rápido de n log n
      Creo que el factor constante de este algoritmo era algo así como 22, aunque quizá era otro algoritmo relacionado

  • Uno de los aspectos divertidos del algoritmo median-of-medians es que la lista de autores está completamente llena de estrellas
    Manuel Blum - ganador del Premio Turing en 1995
    Robert Floyd - ganador del Premio Turing en 1978
    Ron Rivest - ganador del Premio Turing en 2002
    Bob Tarjan - ganador del Premio Turing en 1986 y del primer Premio Nevanlinna en 1982
    Vaughan Pratt - el único de la lista que no ganó el Premio Turing, pero es profesor emérito de Stanford y dirigió el proyecto SUN antes de que se convirtiera en Sun Microsystems; además tuvo un papel importante al inicio de Sun como director de investigación y diseñador del logo de Sun, y también dejó varias cosas geniales como los certificados de primalidad de Pratt
    Cuatro Premios Turing independientes y hasta una SPARCstation, este paper lo tiene todo

    • Pregunta de entrevista para desarrollador frontend junior: “En los próximos 30 minutos, reproduzca el trabajo de cuatro ganadores del Premio Turing. Hay una pizarra sucia y un marcador seco. Su tiempo empieza ahora”
    • Enlace directo para quien quiera leer el paper original: https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
      La lista de autores definitivamente impresiona
    • Otro trabajo genial de Pratt es Pratt parsing. Discusión en HN: https://news.ycombinator.com/item?id=39066465
      La “P” del algoritmo KMP también es Pratt

  • return l[len(l) / 2]
    No soy experto en Python, pero ¿el operador / en Python no devuelve un número de punto flotante? ¿Por qué no usar //, que es división entera, en lugar de usar un flotante como índice de arreglo?
    Tal vez no sea un problema salvo con arreglos muy grandes, pero aun así deja bastante olor a código. Si fuera un principiante en Python y no supiera que existen ambos operadores, podría dejarlo pasar, pero en el artículo también hay código todavía más raro donde en una rama usa división entera y en la otra usa división de punto flotante
    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))
    Ya hay 50 comentarios y parece que nadie se dio cuenta, así que eso solo refuerza mis prejuicios previos sobre la calidad promedio del código Python

    • Buena observación. En Python 2 había un solo operador, pero en Python 3 ya están diferenciados
      Yo esperaría que indexar un arreglo con un flotante provoque una excepción
    • Estoy de acuerdo en que huele a código raro. Aun así, como es un artículo sobre algoritmos, no creo que sea del todo justo juzgarlo por la calidad del código
      Eligieron un lenguaje de programación real que parece pseudocódigo en lugar de pseudocódigo, y para fines explicativos supongo que lo consideran código que probablemente funciona

  • El texto original fue muy entretenido, pero me hizo ruido la parte de “si en cada paso eliges el elemento más grande como pivote, puede volverse O(n²) en lugar de O(n)”
    Si te preocupan entradas adversariales, puedes primero barajar los datos en O(n) para evitar que eso pueda forzarse. Si los datos son demasiado grandes como para barajarlos fácilmente, basta con mezclarlos una sola vez cuando los buckets se hayan reducido a un tamaño que sí permita barajarlos
    Si ya los barajaste, la probabilidad de que ocurra el peor caso queda garantizada como prácticamente inexistente. Si alguien dice que “técnicamente” sigue siendo posible, yo respondería que “técnicamente” un atacante también podría adivinar todos los bits de una clave privada de 256 bits
    Nuestro mundo está construido sobre probabilidades. Todas las claves privadas están protegidas por la imposibilidad matemática de que alguien las adivine exactamente
    Por lo que he leído, quickselect después de barajar es O(n) en la práctica

    • Ya está usando su propia aleatoriedad para elegir el pivote al azar, así que no veo por qué barajar ayudaría más
      Aun así, si puedes confiar en el generador aleatorio, la probabilidad de que el tiempo de ejecución supere O(n) es muy baja
    • Decir “si te preocupan entradas adversariales, primero baraja los datos en O(n) y eso lo garantiza” no garantiza evitar el peor caso, sino eliminar la posibilidad de forzar el peor caso

  • Floyd-Rivest también logra eso. Si no recuerdo mal, es un poco más eficiente
    Pero nunca terminé de entender cómo funciona
    https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

  • Al seleccionar el n-ésimo elemento, si n es muy pequeño o muy grande, median-of-medians puede no ser lo mejor
    En su lugar puedes usar pivotes sesgados, como en [1], o algo que yo llamo “j-ésimo de k-ésimo”. Floyd-Rivest también puede acelerarse
    Hay un proyecto hobby que da entre 1.2x y 2.0x el rendimiento frente a un quickselect bien implementado: https://github.com/koskinev/turboselect
    Me interesaría cualquier material sobre algoritmos rápidos de selección in-place de propósito general
    [1] https://doi.org/10.4230/LIPIcs.SEA.2017.24

  • También podrías usar un algoritmo de streaming que calcule una aproximación de cualquier cuantil sin guardar todos los datos en memoria

    • Si puedes tolerar una aproximación, es una forma genial de hacerlo. Pero enseguida aparecen preguntas incómodas
      ¿Puedes permitirte un cálculo aproximado? ¿Qué supuestos sobre los datos hacen falta para fijar un margen de error? ¿Cómo vas a verificar que esos supuestos sigan siendo válidos?
      Personalmente, creo que me inclinaría por el algoritmo quickselect del texto original hasta que realmente llegara a una situación donde fuera necesario considerar una aproximación de mediana por streaming
    • Definitivamente ha habido casos en los que un algoritmo de cuantiles por streaming habría sido útil. ¿Hay algún material recomendable para consultar?