heapsort - 实现的复杂性
heapsort - implementation's complexity
我写了heapsort (Cormen)。算法排序正确,但复杂性高于预期。
void heap_sort(int tab[], int length)
{
build_max_heap(tab, length);
int heap_size = length;
for (int i = length-1; i > 1; i--)
{
int tmp = tab[1];
tab[1] = tab[i];
tab[i] = tmp;
heap_size--;
max_heapify(tab, 1, heap_size);
}
}
void max_heapify (int tab[], int i, int length)
{
int largest;
int l = i * 2;
int r = i * 2 + 1;
if (l < length and tab[l] > tab[i])
largest = l;
else
largest = i;
if (r < length and tab[r] > tab[largest])
largest = r;
if (largest != i)
{
int tmp = tab[i];
tab[i] = tab[largest];
tab[largest] = tmp;
max_heapify(tab, largest, length);
}
}
void build_max_heap(int tab[], int length)
{
for (int i = length/2; i >= 1; i--)
max_heapify(tab, i, length);
}
对于 rand() 生成的 15000000 个数字,它比使用 Shell 排序的排序持续时间更长:
void shell_sort (int tab[], int length)
{
int x = 2;
int q;
do
{
x*=2;
q=2*(length/x) + 1;
for(int i = q, val, j; i < length; i++)
{
val = tab[i];
for(j = i - q ; j >= 0 and tab[j] > val; j-=q)
{
tab[j + q] = tab[j];
}
tab[j + q] = val;
}
}while (q > 1);
}
测试:
HEAPSORT
Time for 1000000 elements: 0.336 s
Time for 2000000 elements: 0.732 s
Time for 3000000 elements: 1.142 s
Time for 4000000 elements: 1.595 s
Time for 5000000 elements: 2.034 s
Time for 6000000 elements: 2.513 s
Time for 7000000 elements: 3.023 s
Time for 8000000 elements: 3.51 s
Time for 9000000 elements: 4.02 s
Time for 10000000 elements: 4.558 s
Time for 11000000 elements: 5.095 s
Time for 12000000 elements: 5.595 s
Time for 13000000 elements: 6.183 s
Time for 14000000 elements: 6.7 s
Time for 15000000 elements: 7.367 s
SHELLSORT
Time for 1000000 elements: 0.343 s
Time for 2000000 elements: 0.779 s
Time for 3000000 elements: 1.182 s
Time for 4000000 elements: 1.654 s
Time for 5000000 elements: 2.218 s
Time for 6000000 elements: 2.672 s
Time for 7000000 elements: 3.34 s
Time for 8000000 elements: 3.778 s
Time for 9000000 elements: 4.297 s
Time for 10000000 elements: 4.903 s
Time for 11000000 elements: 4.872 s
Time for 12000000 elements: 5.514 s
Time for 13000000 elements: 6.29 s
Time for 14000000 elements: 6.994 s
Time for 15000000 elements: 7.121 s
我重复了很多次测试。算法有什么问题?
首先请注意,big-O 和原始性能有着复杂的关系。在堆排序的情况下,较差的内存局部性将导致它在计算机上的扩展性比 big-O 所建议的更差。相比之下,shell 排序只比 O(n log(n))
稍微差一点,而且它的大多数传递具有不错的内存局部性。
因此,我对它们具有可比性并不感到惊讶。
就是说,您可以尝试将 max_heapify
从递归函数转换为循环。这可能会避免一定数量的堆栈操作。
我写了heapsort (Cormen)。算法排序正确,但复杂性高于预期。
void heap_sort(int tab[], int length)
{
build_max_heap(tab, length);
int heap_size = length;
for (int i = length-1; i > 1; i--)
{
int tmp = tab[1];
tab[1] = tab[i];
tab[i] = tmp;
heap_size--;
max_heapify(tab, 1, heap_size);
}
}
void max_heapify (int tab[], int i, int length)
{
int largest;
int l = i * 2;
int r = i * 2 + 1;
if (l < length and tab[l] > tab[i])
largest = l;
else
largest = i;
if (r < length and tab[r] > tab[largest])
largest = r;
if (largest != i)
{
int tmp = tab[i];
tab[i] = tab[largest];
tab[largest] = tmp;
max_heapify(tab, largest, length);
}
}
void build_max_heap(int tab[], int length)
{
for (int i = length/2; i >= 1; i--)
max_heapify(tab, i, length);
}
对于 rand() 生成的 15000000 个数字,它比使用 Shell 排序的排序持续时间更长:
void shell_sort (int tab[], int length)
{
int x = 2;
int q;
do
{
x*=2;
q=2*(length/x) + 1;
for(int i = q, val, j; i < length; i++)
{
val = tab[i];
for(j = i - q ; j >= 0 and tab[j] > val; j-=q)
{
tab[j + q] = tab[j];
}
tab[j + q] = val;
}
}while (q > 1);
}
测试:
HEAPSORT
Time for 1000000 elements: 0.336 s
Time for 2000000 elements: 0.732 s
Time for 3000000 elements: 1.142 s
Time for 4000000 elements: 1.595 s
Time for 5000000 elements: 2.034 s
Time for 6000000 elements: 2.513 s
Time for 7000000 elements: 3.023 s
Time for 8000000 elements: 3.51 s
Time for 9000000 elements: 4.02 s
Time for 10000000 elements: 4.558 s
Time for 11000000 elements: 5.095 s
Time for 12000000 elements: 5.595 s
Time for 13000000 elements: 6.183 s
Time for 14000000 elements: 6.7 s
Time for 15000000 elements: 7.367 s
SHELLSORT
Time for 1000000 elements: 0.343 s
Time for 2000000 elements: 0.779 s
Time for 3000000 elements: 1.182 s
Time for 4000000 elements: 1.654 s
Time for 5000000 elements: 2.218 s
Time for 6000000 elements: 2.672 s
Time for 7000000 elements: 3.34 s
Time for 8000000 elements: 3.778 s
Time for 9000000 elements: 4.297 s
Time for 10000000 elements: 4.903 s
Time for 11000000 elements: 4.872 s
Time for 12000000 elements: 5.514 s
Time for 13000000 elements: 6.29 s
Time for 14000000 elements: 6.994 s
Time for 15000000 elements: 7.121 s
我重复了很多次测试。算法有什么问题?
首先请注意,big-O 和原始性能有着复杂的关系。在堆排序的情况下,较差的内存局部性将导致它在计算机上的扩展性比 big-O 所建议的更差。相比之下,shell 排序只比 O(n log(n))
稍微差一点,而且它的大多数传递具有不错的内存局部性。
因此,我对它们具有可比性并不感到惊讶。
就是说,您可以尝试将 max_heapify
从递归函数转换为循环。这可能会避免一定数量的堆栈操作。