Implementé recientemente un algoritmo QuickSort en C#. Clasificando en una matriz de enteros que contiene millones de elementos, el rendimiento del código es aproximadamente 10% detrás de la implementación de .NET.Costo de métodos de alineación en C#
private static void QS(int[] arr, int left, int right)
{
if (left >= right) return;
var pIndex = Partition(arr, left, right);
QS(arr, left, pIndex);
QS(arr, pIndex + 1, right);
}
en una serie de 5 millones de artículos, este código es de aproximadamente 60 ms lento que .NET de.
Posteriormente, he creado un otro método que tiene el método Partition() inline en QS() (eliminando la llamada al método y la declaración return). Sin embargo, esto dio como resultado un descenso en el rendimiento a aproximadamente 250 ms más lento que el método de ordenación de .NET.
¿Por qué sucede esto?
Editar: Este es el código del método Partition(). En la versión impresa de QS(), todo el contenido de este método con la excepción de la declaración return reemplaza la línea var pIndex = Partition(arr, left, right);.
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
int leftPoint = left - 1;
int pIndex = right + 1;
int temp = 0;
while (true)
{
do { pIndex--; } while (arr[pIndex] > pivot);
do { leftPoint++; } while (arr[leftPoint] < pivot);
if (leftPoint < pIndex)
{
temp = arr[leftPoint];
arr[leftPoint] = arr[pIndex];
arr[pIndex] = temp;
}
else { break; }
}
return pIndex;
}
Edición # 2: En caso de que alguien está interesado en la compilación, aquí está el código que llama a los algoritmos:
Edición # 3: nuevo código de prueba de la sugerencia de Haymo.
private static void Main(string[] args)
{
const int globalRuns = 10;
const int localRuns = 1000;
var source = Enumerable.Range(1, 200000).OrderBy(n => Guid.NewGuid()).ToArray();
var a = new int[source.Length];
int start, end, total;
for (int z = 0; z < globalRuns; z++)
{
Console.WriteLine("Run #{0}", z+1);
total = 0;
for (int i = 0; i < localRuns; i++)
{
Array.Copy(source, a, source.Length);
start = Environment.TickCount;
Array.Sort(a);
end = Environment.TickCount;
total += end - start;
}
Console.WriteLine("{0}\t\tTtl: {1}ms\tAvg: {2}ms", ".NET", total, total/localRuns);
total = 0;
for (int i = 0; i < localRuns; i++)
{
Array.Copy(source, a, source.Length);
start = Environment.TickCount;
Quicksort.SortInline(a);
end = Environment.TickCount;
total += end - start;
}
Console.WriteLine("{0}\t\tTtl: {1}ms\tAvg: {2}ms", "Inlined", total, total/localRuns);
total = 0;
for (int i = 0; i < localRuns; i++)
{
Array.Copy(source, a, source.Length);
start = Environment.TickCount;
Quicksort.SortNonInline(a);
end = Environment.TickCount;
total += end - start;
}
Console.WriteLine("{0}\tTtl: {1}ms\tAvg: {2}ms\n", "Not inlined", total, total/localRuns);
}
}
¿Puede proporcionar un ejemplo compilable? – CodesInChaos
¿Podría publicar el código completo que utiliza, incluido el código que usa para medir la hora? – svick
El optimizador just-in-time ya incluye métodos. Puede tomar mejores decisiones que usted, en realidad sabe cómo es el código de la máquina y puede juzgar si la alineación es realmente una optimización o simplemente lleva a la saturación del código. Una optimización real hace que el código sea más inteligente. La optimización de QS está bien documentada, basta con mirar el artículo de Wikipedia para empezar. –