algorithm - iterative - insertionsort code

Cómo optimizar quicksort

Question

Estoy tratando de elaborar un quicksort eficiente. Funciona bien, pero tarda mucho tiempo en ejecutarse cuando la cantidad de elementos es enorme, y ciertas secciones de la matriz están pre-ordenadas. Estaba buscando el artículo de Wikipedia en quicksort , y allí encontré esto escrito:

Para asegurarse de que se use a lo sumo espacio O (log N), recuéstese primero en la mitad más pequeña de la matriz, y use una llamada de cola para recursionar en la otra.

Utilice la clasificación de inserción, que tiene un factor constante más pequeño y, por lo tanto, es más rápida en arreglos pequeños, para invocaciones en dichos arreglos pequeños (es decir, donde la longitud es menor que un umbral t determinado experimentalmente). Esto se puede implementar dejando tales matrices sin ordenar y ejecutando una sola pasada de clasificación al final, porque la ordenación por inserción maneja las matrices casi de manera eficiente. Un tipo de inserción por separado de cada segmento pequeño a medida que se identifican agrega la sobrecarga de iniciar y detener muchos tipos pequeños, pero evita perder el esfuerzo al comparar claves a través de los muchos límites del segmento, las cuales estarán en orden debido al funcionamiento del proceso de ordenación rápida. También mejora el uso del caché.

Actualmente estoy recurriendo para ambas particiones. ¿Alguna idea de cómo implementar el primer tip? ¿Qué se entiende por repuntar primero en la mitad más pequeña de la matriz, y usar una llamada de cola para amparar en la otra ? Y en segundo lugar, ¿cómo puedo implementar una insertion-sort dentro de quicksort? ¿Mejorará siempre la eficiencia, o solo cuando ciertas secciones de la matriz se clasifiquen previamente? Si es el segundo caso, entonces, por supuesto, no tengo forma de saber cuándo ocurrirá eso. Entonces, ¿cuándo debería incluir la insertion-sort ?

Answer 1

En Ordenación rápida, elige un pivote aleatorio que delimita la matriz a dos medias, la mayoría de las posibilidades de que una sea más pequeña,

por ejemplo, el tamaño de matriz 100, pivot delimita la matriz a 40/60, el 40 es el tamaño más pequeño.

Supongamos que usted decide que el tamaño de su umbral para usar la ordenación por inserción sea 10, necesita continuar dividiendo la matriz recursivamente por pivote, siempre que una de las mitades sea menor o igual a 10, puede usar la ordenación por inserción que se comporta como O (n) en matrices de pequeño tamaño.

Tenga en cuenta que el ordenamiento por inserción se comportará mal si su matriz está ordenada de manera inversa (en el peor de los casos).

Con respecto a las cosas de recursión, solo necesita modificar el caso de parada de la recursión de ordenación rápida -> tamaño de matriz <= 10 detener la recursión y ordenar toda la matriz (que es mucho más pequeña en este paso de recursión) usando la ordenación por inserción.

Por recursión de cola, significan hacer todo lo que necesita con la primera mitad, y luego invocar la ordenación de inserción para la mitad más pequeña como último método, se usa para ahorrar espacio.

 Quick-sort()
choose a pivot
move the smaller elements from left
move the bigger elements from right
quick-sort on the bigger half of the array
if half is less then X
only then do an insertion sort on the other half <- this is a tail recursion insertion sort
else
quick sort on this half also

Por lo que veo, la segunda optimización sugiere no usar la ordenación por inserción para cada paso de recursión, pero recuerde los índices para los cuales se hizo la restricción, luego invocar la ordenación por inserción en un lote concatenando los elementos de todas las porciones, esto asegurará mejorar el uso del caché, pero es un poco más difícil de implementar,

Answer 2

Hace algún tiempo escribí un algoritmo basado en quicksort que puedes encontrar allí (en realidad es un algoritmo de selección, pero también se puede usar un algoritmo de clasificación):

• http://processors.wiki.ti.com/index.php/Top_K_Elements_Sort_For_DSP_With_Index_Ordering

Las lecciones que aprendí de esta experiencia son las siguientes:

1. Sintonice cuidadosamente el bucle de partición de su algoritmo . A menudo, esto se subestima, pero se obtiene un aumento significativo en el rendimiento si se encarga de escribir bucles para que el compilador / CPU pueda canalizar el software. Esto solo ha llevado a una victoria de alrededor del 50% en los ciclos de CPU.
2. La codificación manual de las clases pequeñas le da una gran ganancia de rendimiento . Cuando el número de elementos a ordenar en una partición es inferior a 8 elementos, simplemente no se moleste en tratar de repetir, sino que implemente una clasificación codificada utilizando solo ifs y swaps (vea la función fast_small_sort en este código) . Esto puede llevar a una ganancia de alrededor del 50% en los ciclos de CPU, lo que otorga al quicksort el mismo rendimiento práctico que una "ordenación de fusión" bien escrita.
3. Pase tiempo para elegir un mejor valor de pivote cuando se detecte una selección de pivote "pobre" . Mi implementación comienza utilizando un algoritmo de "mediana de la mediana" para la selección de pivote cada vez que una selección de pivote conduce a que un lado esté por debajo del 16% de los elementos restantes a clasificar. Esta es una estrategia de mitigación para el desempeño en el peor de los casos de ordenación rápida , y ayuda a garantizar que en la práctica el límite superior sea también O (n * log (n)) en lugar de O (n ^ 2).
4. Optimizar para arreglos con muchos valores iguales (cuando sea necesario) . Si los arreglos que se van a ordenar tienen muchos valores iguales, vale la pena optimizarlos, ya que dará lugar a una mala selección de pivote. En mi código lo hago contando todas las entradas de la matriz que son iguales al valor pivote. Esto me permite tratar el pivote y todos los valores iguales en la matriz de una manera más rápida, y no degrada el rendimiento cuando no es aplicable. Esta es otra estrategia de mitigación para el desempeño en el peor de los casos, ya que ayuda a reducir el uso de la pila en el peor de los casos al reducir el nivel máximo de recursión de una manera drástica .

Espero que esto ayude, Laurent.

Answer 3

Hay varias formas en que uno puede hacer que el orden rápido estándar sea más eficiente. Para implementar el primer consejo de tu publicación debes escribir algo como:

void quicksort(int * tab, int l, int r)
{
int q;
while(l < r)
{
q = partition(tab, l, r);
if(q - l < r - q) //recurse into the smaller half
{
quicksort(tab, l, q - 1);
l = q + 1;
} else
{
quicksort(tab, q + 1, r);
r = q - 1;
}
}
}

Espero que eso sea lo suficientemente claro. El siguiente paso sería implementar su propia pila (o usar un componente incorporado del idioma que esté usando) en lugar de usar llamadas recursivas. Código de ejemplo (pseudo):

void quicksort2(int * tab, int l, int r)
{
int le, ri, q;
init stack;
push(l, r, stack);
while(!empty(stack))
{
//take the top pair of values from the stack and set them to le and ri
pop(le, ri, stack);
if(le >= ri)
continue;
q = partition(tab, le, ri);
if(q - le < ri - q) //smaller half goes first
{
push(le, q - 1, stack);
push(q + 1, ri, stack);
} else
{
push(q + 1, ri, stack);
push(le, q - 1, stack);
}
}
delete stack;
}

Luego puedes proceder a implementar el otro consejo de tu publicación. Para hacer esto, debe establecer una constante arbitraria, llamémosla CUT_OFF, a alrededor de 20. Esto le indicará a su algoritmo cuándo debe cambiar a la clasificación de inserción. Debería ser bastante fácil (una cuestión de agregar una sentencia if) alterar el ejemplo anterior para que cambie a la ordenación por inserción después de que haya alcanzado un punto CUT_OFF, por lo que lo dejaré.

En cuanto al método de partición, recomendaría usar la partición Lomuto en lugar de Hoare.

Sin embargo, si sus datos ya están pre-ordenados, entonces podría considerar usar un algoritmo diferente por completo. Desde mi experiencia, la ordenación por fusión de series naturales implementada en una lista vinculada es una muy buena opción, si sus datos están pre-ordenados.

Answer 4

La recursión de cola es cambiar una llamada recursiva en un bucle. Para QuickSort, sería algo como:

QuickSort(SortVar)
Granularity = 10
SortMax = Max(SortVar)
/* Put an element after the last with a higher key than all other elements
to avoid that the inner loop goes on forever */
SetMaxKey(SortVar, SortMax+1)
/* Push the whole interval to sort on stack */
Push 1 SortMax
while StackSize() > 0
/* Pop an interval to sort from stack */
Pop SortFrom SortTo
/* Tail recursion loop */
while SortTo - SortFrom >= Granularity
/* Find the pivot element using median of 3 */
Pivot = Median(SortVar, SortFrom, (SortFrom + SortTo) / 2, SortTo)
/* Put the pivot element in front */
if Pivot > SortFrom then Swap(SortVar, SortFrom, Pivot)
/* Place elements <=Key to the left and elements >Key to the right */
Key = GetKey(SortVar, SortFrom)
i = SortFrom + 1
j = SortTo
while i < j
while GetKey(SortVar, i) <= Key; i = i + 1; end
while GetKey(SortVar, j) > Key; j = j - 1; end
if i < j then Swap(SortVar, i, j)
end
/* Put the pivot element back */
if GetKey(SortVar, j) < Key then Swap(SortVar, SortFrom, j)
if j - SortFrom < SortTo - j then
/* The left part is smallest - put it on stack */
if j - SortFrom > Granularity then Push SortFrom j-1
/* and do tail recursion on the right part */
SortFrom = j + 1
end
else
/* The right part is smallest - put it on stack */
if SortTo - j > Granularity then Push j+1 SortTo
/* and do tail recursion on the left part */
SortTo = j - 1
end
end
end
/* Run insertionsort on the whole array to sort the small intervals */
InsertionSort(SortVar)
return

Además, no hay ninguna razón para llamar a InsertionSort en los intervalos pequeños, porque cuando QuickSort finaliza, la matriz está ordenada de manera aproximada, de modo que solo quedan pequeños intervalos por ordenar. Y este es el caso perfecto para InsertionSort.

Si no tienes una pila, puedes usar la recursión en su lugar, pero mantén la recursión de la cola:

QuickSort(SortVar, SortFrom, SortTo)
Granularity = 10
/* Tail recursion loop */
while SortTo - SortFrom >= Granularity
/* Find the pivot element using median of 3 */
Pivot = Median(SortVar, SortFrom, (SortFrom + SortTo) / 2, SortTo)
/* Put the pivot element in front */
if Pivot > SortFrom then Swap(SortVar, SortFrom, Pivot)
/* Place elements <=Key to the left and elements >Key to the right */
Key = GetKey(SortVar, SortFrom)
i = SortFrom + 1
j = SortTo
while i < j
while GetKey(SortVar, i) <= Key; i = i + 1; end
while GetKey(SortVar, j) > Key; j = j - 1; end
if i < j then Swap(SortVar, i, j)
end
/* Put the pivot element back */
if GetKey(j) < Key then Swap(SortVar, SortFrom, j)
if j - SortFrom < SortTo - j then
/* The left part is smallest - recursive call */
if j - SortFrom > Granularity then QuickSort(SortVar, SortFrom, j-1)
/* and do tail recursion on the right part */
SortFrom = j + 1
end
else
/* The right part is smallest - recursive call */
if SortTo - j > Granularity then QuickSort(SortVar, j+1, SortTo)
/* and do tail recursion on the left part */
SortTo = j - 1
end
end
/* Run insertionsort on the whole array to sort the small intervals */
InsertionSort(SortVar)
return

Answer 5

Puede echar un vistazo a TimSort, que para datos no completamente aleatorios funciona mejor que quicksort (tienen la misma complejidad asintótica pero TimSort tiene constantes más bajas)

Answer 6

Recientemente he encontrado esta optimización . Funciona más rápido que std :: sort. Utiliza la selección por selección en arreglos pequeños y la mediana de 3 como elemento de partición.

Esta es mi implementación de C ++:

const int CUTOFF = 8;
template<typename T>
bool less (T &v, T &w)
{
return (v < w);
}
template<typename T>
bool eq (T &v, T &w)
{
return w == v;
}
template <typename T>
void swap (T *a, T *b)
{
T t = *a;
*a = *b;
*b = t;
}
template<typename T>
void insertionSort (vector<T>& input, int lo, int hi)
{
for (int i = lo; i <= hi; ++i)
{
for (int j = i; j > lo && less(input[j], input[j-1]); --j)
{
swap(&input[j], &input[j-1]);
}
}
}
template<typename T>
int median3 (vector<T>& input, int indI, int indJ, int indK)
{
return (less(input[indI], input[indJ]) ?
(less(input[indJ], input[indK]) ? indJ : less(input[indI], input[indK]) ? indK : indI) :
(less(input[indK], input[indJ]) ? indJ : less(input[indK], input[indI]) ? indK : indI));
}
template <typename T>
void sort(vector<T>& input, int lo, int hi)
{
int lenN = hi - lo + 1;
// cutoff to insertion sort
if (lenN <= CUTOFF)
{
insertionSort(input, lo, hi);
return;
}
// use median-of-3 as partitioning element
else if (lenN <= 40)
{
int median = median3(input, lo, lo + lenN / 2, hi);
swap(&input[median], &input[lo]);
}
// use Tukey ninther as partitioning element
else
{
int eps = lenN / 8;
int mid = lo + lenN / 2;
int mFirst = median3(input, lo, lo + eps, lo + eps + eps);
int mMid = median3(input, mid - eps, mid, mid + eps);
int mLast = median3(input, hi - eps - eps, hi - eps, hi);
int ninther = median3(input, mFirst, mMid, mLast);
swap(&input[ninther], &input[lo]);
}
// Bentley-McIlroy 3-way partitioning
int iterI = lo, iterJ = hi + 1;
int iterP = lo, iterQ = hi + 1;
for (;; )
{
T v = input[lo];
while (less(input[++iterI], v))
{
if (iterI == hi)
break;
}
while (less(v, input[--iterJ]))
{
if (iterJ == lo)
break;
}
if (iterI >= iterJ)
break;
swap(&input[iterI], &input[iterJ]);
if (eq(input[iterI], v))
swap(&input[++iterP], &input[iterI]);
if (eq(input[iterJ], v))
swap(&input[--iterQ], &input[iterJ]);
}
swap(&input[lo], &input[iterJ]);
iterI = iterJ + 1;
iterJ = iterJ - 1;
for (int k = lo + 1; k <= iterP; ++k)
{
swap(&input[k], &input[iterJ--]);
}
for (int k = hi ; k >= iterQ; --k)
{
swap(&input[k], &input[iterI++]);
}
sort(input, lo, iterJ);
sort(input, iterI, hi);
}