algorithm - meta tags seo 2018

¿La ordenación rápida con mediana de tres al azar es sensiblemente mejor que la ordenación aleatoria? (5)

Simplemente estaba respondiendo una pregunta sobre diferentes enfoques para elegir la partición en una implementación de orden rápida y se me ocurrió una pregunta que, sinceramente, no sé cómo responder. Es un poco pesado en matemáticas, y este puede ser el sitio incorrecto para preguntar esto, así que si esto necesita moverse, hágamelo saber y con mucho gusto lo migraré a otra parte.

Es bien sabido que una implementación de orden rápida que selecciona sus pivotes de manera uniforme al azar terminará ejecutándose en el tiempo O (n lg n) esperado (hay una buena prueba de esto en Wikipedia ). Sin embargo, debido al costo de generar números aleatorios, muchas implementaciones de orden rápido no seleccionan pivotes al azar, sino que se basan en un enfoque de "mediana de tres" en el que tres elementos se eligen de manera determinista y la mediana se elige como la pivote. Se sabe que esto degenerará a O (n ² ) en el peor de los casos (por ejemplo, vea este gran artículo sobre cómo generar esas entradas del peor de los casos).

Ahora, supongamos que combinamos estos dos enfoques seleccionando tres elementos aleatorios de la secuencia y utilizando su mediana como la opción de pivote. Sé que esto también garantiza el tiempo de ejecución promedio de O (n lg n) usando una prueba ligeramente diferente a la del ordinario aleatorio aleatorio. Sin embargo, no tengo ni idea de cuál es el factor constante frente al término n lg n en esta implementación en particular de orden rápida. Para la ordenación rápida aleatoria regular, Wikipedia enumera el tiempo de ejecución real de la ordenación aleatoria que requiere como máximo 1.39 n lg n comparaciones (utilizando lg como el logaritmo binario).

Mi pregunta es la siguiente: ¿Alguien sabe de una manera de derivar el factor constante para el número de comparaciones realizadas utilizando una ordenación aleatoria aleatoria "mediana de tres" ? Si vamos más generalmente, ¿existe una expresión para el factor constante en el ordenamiento rápido utilizando un enfoque aleatorio de la mediana de k? Tengo curiosidad porque creo que sería fascinante ver si hay algún "punto dulce" en este enfoque que haga menos comparaciones que otras implementaciones aleatorias de orden rápido. Quiero decir, ¿no sería genial poder decir que el ordenamiento aleatorio aleatorio con una selección aleatoria de pivote de media de seis hace la menor cantidad de comparaciones? ¿O ser capaz de decir de manera concluyente que debería elegir un elemento pivote al azar?

Aquí hay una derivación heurística de la constante. Creo que puede hacerse riguroso, con mucho más esfuerzo.

Sea P una variable aleatoria continua con valores en [0, 1]. Intuitivamente, P es la fracción de valores menor que el pivote. Estamos buscando encontrar la constante c tal que

cn lg n = E [n + c P n lg (P n) + c (1 - P) n lg ((1 - P) n)].

Un poco de álgebra después, tenemos

c = 1 / E [-P lg P - (1 - P) lg (1 - P))].

En otras palabras, c es el recíproco de la entropía esperada de la distribución de Bernoulli con la media P. Intuitivamente, para cada elemento, debemos compararla con los pivotes de una manera que produzca lg n bits de información.

Cuando P es uniforme, el pdf de P es 1. La constante es

In[1]:= -1/NIntegrate[x Log[2, x] + (1 - x) Log[2, 1 - x], {x, 0, 1}] Out[1]= 1.38629

Cuando el pivote es una mediana de 3, el pdf de P es 6 x (1 - x). La constante es

In[2]:= -1/NIntegrate[6 x (1 - x) (x Log[2, x] + (1 - x) Log[2, 1 - x]), {x, 0, 1}] Out[2]= 1.18825

La constante para la ordenación aleatoria aleatoria usual es fácil de calcular porque la probabilidad de que se comparen dos elementos k en ubicaciones separadas es exactamente 2 / (k + 1): la probabilidad de que uno de los dos elementos se elija como un pivote antes de cualquiera de los K-1 elementos entre ellos. Desafortunadamente, nada tan inteligente se aplica a su algoritmo.

Dudo en intentar tu pregunta en negrita porque puedo responder a tu pregunta "subyacente": hablando asintóticamente, no hay un "punto dulce". El costo total agregado de computar las medianas de k elementos, incluso los elementos O (n ^{1 - ε} ), es lineal, y la constante para el término n log n disminuye con la matriz dividida de manera más equitativa. La captura es, por supuesto, constantes en el término lineal que son espectacularmente poco prácticas, destacando uno de los inconvenientes del análisis asintótico.

Según mis comentarios a continuación, supongo que k = O (n ^α ) para 0 <α <1 es el "punto dulce".

Si el estado inicial del conjunto se ordena aleatoriamente, obtendrá exactamente el mismo factor constante para seleccionar aleatoriamente tres elementos para calcular la mediana como cuando se seleccionan tres elementos de manera determinista.

El motivo para elegir el ítem al azar sería que el método determinista daría un resultado peor que el promedio. Si el método determinista proporciona una buena mediana, no se puede mejorar seleccionando elementos al azar.

Por lo tanto, cualquier método que dé el mejor resultado depende de los datos de entrada, no se puede determinar para cada conjunto posible.

La única forma segura de reducir el factor constante es aumentar el número de elementos que utiliza para calcular la mediana, pero en algún momento el cálculo de la mediana será más costoso de lo que obtiene al obtener un mejor valor de la mediana.

Si lo hace Bentley y McIlroy, autores de la función qsort la biblioteca estándar de C , escribieron en su artículo, Ingeniería de una función de clasificación los siguientes números:

1.386 n lg n comparaciones promedio utilizando el primer pivote, medio o aleatorio
1.188 n lg n comparaciones promedio usando una mediana de 3 pivotes
1.094 n lg n comparaciones promedio usando una mediana de pivote de 3 medianas

Según el documento anterior:

Por lo tanto, nuestro código final elige el elemento central de las matrices más pequeñas, la mediana de los elementos primero, medio y último de una matriz de tamaño medio, y la pseudo-mediana de nueve elementos espaciados uniformemente de una matriz grande.

Solo un pensamiento: si usa el enfoque de la mediana de tres y encuentra que es mejor, ¿por qué no usa el enfoque de la mediana de cinco o la mediana de once ? Y mientras estás en ello, quizás puedas pensar en una optimización de la mediana de n ... hmmm ... Ok, obviamente es una mala idea (ya que tendrías que ordenar tu secuencia para eso ...).

Básicamente, para elegir tu elemento de pivote como los elementos de la mediana de m , ordenas esos m elementos, ¿verdad? Por lo tanto, simplemente supongo que una de las constantes que está buscando es "2": Al clasificar primero 3 elementos para elegir su pivote, ¿cuántas comparaciones adicionales ejecutará? Digamos que es 2. Haces esto dentro del quicksort una y otra vez. Una conclusión básica sería que la mediana de 3 es, por lo tanto, 2 veces más lenta que la ordenación aleatoria simple.

Pero, ¿qué está funcionando para ti aquí? Que obtienes una mejor distribución de dispositivos y conquistas, y estás mejor protegido contra el caso degenerado (un poco).

Entonces, volvamos a mi infame pregunta al principio: ¿por qué no elegir el elemento de pivote de una mediana de m , siendo 5, 7, n / 3, o algo así? Debe haber un punto dulce donde la clasificación de los elementos m sea peor que la ganancia del mejor comportamiento de dividir y conquistar y de ordenación rápida. Supongo que este punto dulce está allí muy temprano: primero debes luchar contra el factor constante de 2 comparaciones si eliges la mediana de 3 . Vale la pena un experimento, lo admito, pero no estaría demasiado expectante del resultado :-) Pero si me equivoco, y la ganancia es enorme: ¡no te detengas en 3!