一、 缘起
看到CSDN社区有篇《3秒搞定一亿数据的前K个最大值》, 想想堆排序不是可以用来做这事吗,于是就动手做做,看看堆排序能够达到怎样的效率。堆的原理就不多说了,网上有好多, 如果想参阅比较权威性的材料,可参见《算法导论》第六章堆排序。 本文的程序即是建立其上。
二、 程序
KthMax.c
/* * 使用堆排序求解前K个最大值问题 * */ #include "HeapUtil.c" /* 计算 list 中前 k 个最大值 */ Elem* findkthMax(Elem *list, int k, long num); void testkthMax(long NUM, int K); void measure(long NUM , int K); void testValid(); void testPerf(); int main() { srand(time(NULL)); //test(" Test Valid ", testValid); // test(" Measure Performace ", testPerf); measure(100000000, 100); getchar(); return 0; } void test(char *msg, void (*test)()) { printf("\n----------- %s ----------\n", msg); (*test)(); printf("\n\n"); } void testValid() { long num; int k; for (num = 0; num <= 8; num += 1) { for (k = 0; k <= num; k+=1) { testkthMax(num, k); } } } /* 测试找出前K个最大值 */ void testkthMax(long NUM, int K) { Elem *kthmax; Elem* list = myalloc(NUM+1); creatList(list, NUM); printf("\nThe original list:\n"); printList(list, NUM); kthmax = findkthMax(list, K, NUM); printListInternal(kthmax, 0, K, K); free(kthmax); free(list); printf("\n"); } void testPerf() { long num ; int k; for (num = 1; num <= 100000000; num*=10) { for (k = 1; k <= 1000 && k <= num ; k*=10) { measure(num, k); } } } void measure(long NUM , int K) { clock_t start, end; Elem *kthmax; Elem* list = myalloc(NUM+1); creatList(list, NUM); start = clock(); kthmax = findkthMax(list, K, NUM); end = clock(); free(kthmax); free(list); printf("\nNUM = %-10ld, K = %-10d, Eclipsed time: %6.3f\n", NUM, K, ((double)(end-start))/CLOCKS_PER_SEC); } /* 计算 list 中前 k 个最大值 */ Elem* findkthMax(Elem *list, int k, long n) { long i; long heapsize = n; Elem *kthmax = myalloc(k); Elem *p = kthmax; buildInitMaxHeap(list, n); for (i = n; i > n-k; i--) { (p++)->num = list[1].num; swap(&list[1], &list[i]); heapsize--; maxHeapify(list, 1, heapsize); } return kthmax; }
HeapUtil.c
/* HeapUtil.c
* 实现建堆过程的函数
*
* NOTE: 数组 list 的 0 号单位未用,元素应放置于[1:num]而不是[0:num-1]
* num 是应用中的数据数目, 因此必须给数组分配至少 num+1 个元素空间,
*/
#include "common.c"
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
/*
* maxHeapify: 使以结点i为根的子树为最大堆.
* 前置条件:结点i的左右子树都满足最大堆性质
*/
void maxHeapify(Elem list[], long i, long heapsize);
void buildInitMaxHeap(Elem list[], long num); /* BuildMaxHeap: 构造初始最大堆 */
void swap(Elem *e1, Elem *e2);
void maxHeapify(Elem list[], long i, long heapsize)
{
long largest = i; /* 结点i与其左右孩子节点中关键词最大的那个结点的下标 */
long lch = LEFT(i);
long rch = RIGHT(i);
if (lch <= heapsize && list[lch].num > list[largest].num) {
largest = lch;
}
if (rch <= heapsize && list[rch].num > list[largest].num) {
largest = rch;
}
if (largest != i) {
swap(&list[largest], &list[i]);
maxHeapify(list, largest, heapsize);
}
}
/*
* buildMaxHeap: 构造初始最大堆
*/
void buildInitMaxHeap(Elem list[], long num)
{
long i;
for (i = (num+1)/2; i >= 1; i--)
maxHeapify(list, i, num);
}
void swap(Elem *e1, Elem *e2)
{
Elem e;
e = *e1;
*e1 = *e2;
*e2 = e;
}
common.c
/*
* common.c 存放公共结构与例程
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
typedef struct {
long num; /* 设为关键词 */
} Elem;
void creatListInternal(Elem *list, long offset, long num, long len);
void printListInternal(Elem *list, long offset, long num, long len);
void creatList(Elem *list, long num);
void printList(Elem *list, long num);
Elem *myalloc(long size);
long randNum();
/*
* 随机生成列表元素,并存入从offset开始的 num 个元素, len 是为列表长度
* 若 len < offset + num 则只存入 len-offset个元素
*/
void creatListInternal(Elem *list, long offset, long num, long len)
{
long i, endIndex = offset+num;
srand(time(NULL));
if (offset < 0 || offset >= len) {
return ;
}
if (endIndex > len) {
endIndex = len ;
}
for (i = offset; i < endIndex; i++)
(*(list+i)).num = randNum();
}
/*
* 打印从offset开始的num个元素, len 是为列表长度
* 若 len < offset + num 则只打印 len-offset个元素
*/
void printListInternal(Elem *list, long offset, long num, long len)
{
long i, endIndex = offset+num;
if (offset < 0 || offset >= len) {
return ;
}
if (endIndex > len) {
endIndex = len ;
}
for (i = offset; i < endIndex; i++)
printf("%3d%c", (*(list+i)).num, ((i-offset+1)%10 == 0) ? '\n': ' ');
printf("\n");
}
void creatList(Elem *list, long num)
{
creatListInternal(list, 1, num, num+1);
}
void printList(Elem *list, long num)
{
printListInternal(list, 1, num, num+1);
}
Elem *myalloc(long size)
{
Elem* list = (Elem *)malloc(size*sizeof(Elem));
if (!list) {
fprintf(stderr, "fail to allocate memory.");
exit(1);
}
return list;
}
long randNum()
{
return ((1 + rand()) % INT_MAX) * ((1 + rand()) % INT_MAX);
}
HeapSort.c
/* * HeapSort.c 实现堆排序 */ #include "HeapUtil.c" #define NUM 10 void heapSort(Elem list[], long num); void testHeapSort(); int main() { printf("*********** test heap sort ********"); testHeapSort(); getchar(); return 0; } void heapSort(Elem list[], long num) { long i, heapsize = num; buildInitMaxHeap(list, num); for (i = num; i >= 1; i--) { swap(&list[1], &list[i]); heapsize--; maxHeapify(list, 1, heapsize); } } /* 测试堆排序 */ void testHeapSort() { Elem list[NUM+1]; creatList(list, NUM); printf("\nThe original list:\n"); printList(list, NUM); printf("\n"); heapSort(list, NUM); printf("\nThe sorted list:\n"); printList(list, NUM); printf("\n"); }
三、 时间测量
四、 效率分析
使用堆的方法在n个数值中查找前K个最大值的时间效率为 O(n + k*log2n) ,其中建立初始最大堆(即buildInitMaxHeap)的时间为O(n) ,而每次查找均需要约 O(log2n) , 合起来即是前述结果。 因此, 总时间是随总元素数目线性增长的, 而当K远小于 n 时, 查找前K个最大值所耗费的时间差别不大。
五、 程序优化的起点
从结果中可以看到,比别人的整整慢一倍! 还有的能达到0.1s级别,当然,这可能与机器硬件配置有关,不过,无论如何,也阻挡不住我进行程序优化的决心了。之前学过一些优化的方法手段,正好在这程序上练练手,巩固下。 请期待下文。
所有评论(0)