最快的安全排序算法实现 [英] Fastest safe sorting algorithm implementation
问题描述
我花了一些时间在C#中实现快速排序算法。
完成后,我比较了实现和C#的Array.Sort-Method的速度。
I spend some time implementing a quicksort algorithm in C#. After finishing I compared the speed of my implementation and C#'s Array.Sort-Method.
我只是比较了处理随机int数组的速度。
I just compare speed working on random int arrays.
这是我的实现方式:
static void QuickSort(int[] data, int left, int right)
{
int i = left - 1,
j = right;
while (true)
{
int d = data[left];
do i++; while (data[i] < d);
do j--; while (data[j] > d);
if (i < j)
{
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
else
{
if (left < j) QuickSort(data, left, j);
if (++j < right) QuickSort(data, j, right);
return;
}
}
}
性能(随机排序时) int [],长度为100000000):
-我的算法:14.21秒
--.Net Array< int>。排序:14.84秒
Performance (when sorting an random int[] with length of 100000000):
- my algorithm: 14.21 seconds
- .Net Array<int>.Sort: 14.84 seconds
有人知道如何更快地实现我的算法吗?
还是有人可以提供更快的实现(不需要是快速排序!),我的运行速度会更快吗?
Does anyone know how to implement my algorithm even faster?
Or can anyone provide a faster implementation (need not be a quicksort!) which my run faster?
注意:
-请不要使用使用多个内核/处理器来提高性能的算法
-仅有效的C#源代码
Note:
- please no algorithms which use multiple cores/processors to improve perrformance
- only valid C# source code
如果在线,我将在几分钟内测试所提供算法的性能。
I will test the performance of the provided algorithms within a few minutes if I'm online.
编辑:
您认为对值小于8的零件使用理想的分拣网络会提高性能吗?
Do you think using a ideal sorting network for parts containing less than 8 value would improve performance?
推荐答案
有人知道如何更快地实现我的
算法吗?
Does anyone know how to implement my algorithm even faster?
通过将代码转换为使用指针,可以节省10%的执行时间。
I was able to shave 10% off the execution time by converting your code to use pointers.
public unsafe static void UnsafeQuickSort(int[] data)
{
fixed (int* pdata = data)
{
UnsafeQuickSortRecursive(pdata, 0, data.Length - 1);
}
}
private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right)
{
int i = left - 1;
int j = right;
while (true)
{
int d = data[left];
do i++; while (data[i] < d);
do j--; while (data[j] > d);
if (i < j)
{
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
else
{
if (left < j) UnsafeQuickSortRecursive(data, left, j);
if (++j < right) UnsafeQuickSortRecursive(data, j, right);
return;
}
}
}
这篇关于最快的安全排序算法实现的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!