k均值算法,程序员面试题狂想曲：第三章续、Top K算法问题的实现

                     程序员面试题狂想曲：第三章续、Top K算法问题的实现
作者：July
致谢：
时间：2011年05月08日
微博：http://weibo.com/julyweibo 。
出处：http://blog.csdn.net/v_JULY_v
-----------------------------------------------
前奏
    在上一章，第三章寻找最小的k个数中，由于后来为了论证类似快速排序中partition的方法在最坏情况下，能在O（N）的时间复杂度内找到最小的k个数，而前前后后updated了10余次。所谓功夫不负苦心人，终于得到了一个想要的结果。
    简单总结如下（详情，请参考原文第三章）：
    1、RANDOMIZED-SELECT，以序列中随机选取一个元素作为主元，可达到线性期望时间O（N）的复杂度。
    2、SELECT，快速选择算法，以序列中“五分化中项的中项”，或“中位数的中位数”作为主元（枢纽元），则不容置疑的可保证在最坏情况下亦为O（N）的复杂度。
    本章，咱们来阐述寻找最小的k个数的反面，即寻找最大的k个数，但此刻可能就有读者质疑了，寻找最大的k个数和寻找最小的k个数，原理不是一样的么?
    是的，的确是一样，但这个寻找最大的k个数的问题的实用范围更广，因为它牵扯到了一个Top K算法问题，以及有关搜索引擎，海量数据处理等广泛的问题，所以本章有必要对这个Top K算法问题，进行阐述。
第一节、寻找最大的k个数
把之前第三章的问题，改一个字，即成为寻找最大的k个数的问题了，如下所述：
查找最大的k个元素
题目描述：输入n个整数，输出其中最大的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最大的4个数字为1，2，3和4。
    分析：由于寻找最大的k个数的问题与之前的寻找最小的k个数的问题，本质是一样的，所以，这里就简单阐述下思路，ok，考验你举一反三的能力到了：

    1、排序，快速排序。我们知道，快速排序平均所费时间为n*logn，从小到大排序这n个数，然后再遍历序列中后k个元素输出，即可，总的时间复杂度为O（n*logn+k）=O（n*logn）。
    2、排序，选择排序。用选择或交换排序，即遍历n个数，先把最先遍历到得k个数存入大小为k的数组之中，对这k个数，利用选择或交换排序，找到k个数中的最小数kmin（kmin设为k个元素的数组中最小元素），用时O（k）（你应该知道，插入或选择排序查找操作需要O（k）的时间），后再继续遍历后n-k个数，x与kmin比较：如果x>kmin，则x代替kmax，并再次重新找出k个元素的数组中最大元素kmin‘（多谢kk791159796 提醒修正）；如果x<kmin，则不更新数组。这样，每次更新或不更新数组的所用的时间为O（k）或O（0），整趟下来，总的时间复杂度平均下来为：n*O（k）=O（n*k）。
    3、维护k个元素的最小堆，原理与上述第2个方案一致，即用容量为k的最小堆存储最先遍历到的k个数，并假设它们即是最大的k个数，建堆费时O（k），并调整堆（费时O（logk））后，有k1>k2>...kmin（kmin设为大顶堆中最大元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，x>kmin，更新堆（用时logk），否则不更新堆。这样下来，总费时O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然，就如上述思路2所述：直接用数组也可以找出最大的k个元素，用时O（n*k））。
    4、按编程之美第141页上解法二的所述，类似快速排序的划分方法，N个数存储在数组S中，再从数组中随机选取一个数X，把数组划分为Sa和Sb俩部分，Sa>=X>=Sb，如果要查找的k个元素小于Sa的元素个数，则返回Sa中较大的k个元素，否则返回Sa中所有的元素+Sb中最大的k-|Sa|个元素。不断递归下去，把问题分解成更小的问题，平均时间复杂度为O（N）（严格证明，请参考第三章）。
   .........

   其它的方法，在此不再重复了，同时，借助堆寻找最小的k个数，在第三章已有实现，更多，可参考第三章，只要把最大堆改成最小堆，即可。
第二节、Top K 算法问题
2.1、搜索引擎热门搜索
题目描述：
    搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
    假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
    分析：这个问题在之前的这篇文章里，已经有所解答，十一、从头到尾彻底解析Hash表算法。方法是，第一步、先对这批海量数据预处理，在O（N）的时间内用Hash表完成统计（之前写成了排序，特此订正。July、2011.04.27）；
    第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。
        即，借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N'*O（logK），（N为1000万，N’为300万）。ok，更多，详情，请参考原文。
    或者：采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。
    ok，本章里，咱们来实现这个问题，为了降低实现上的难度，假设这些记录全部是一些英文单词，即用户在搜索框里敲入一个英文单词，然后查询搜索结果，最后，要你统计输入单词中频率最大的前K个单词。ok，复杂问题简单化了之后，编写代码实现也相对轻松多了，如下：
//copyright@yansha &&July //July、updated，2011.05.08 //题目描述： //搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的 //长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果 //除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门）， //请你统计最热门的10个查询串，要求使用的内存不能超过1G。 #include <iostream> #include <string> #include <assert.h> using namespace std; #define HASHLEN 2807303 #define WORDLEN 30 // 结点指针 typedef struct node_no_space *ptr_no_space; typedef struct node_has_space *ptr_has_space; ptr_no_space head[HASHLEN]; struct node_no_space { char *word; int count; ptr_no_space next; }; struct node_has_space { char word[WORDLEN]; int count; ptr_has_space next; }; // 最简单hash函数 int hash_function(char const *p) { int value = 0; while (*p != '\0') { value = value * 31 + *p++; if (value > HASHLEN) value = value % HASHLEN; } return value; } // 添加单词到hash表 void append_word(char const *str) { int index = hash_function(str); ptr_no_space p = head[index]; while (p != NULL) { if (strcmp(str, p->word) == 0) { (p->count)++; return; } p = p->next; } // 新建一个结点 ptr_no_space q = new node_no_space; q->count = 1; q->word = new char [strlen(str)+1]; strcpy(q->word, str); q->next = head[index]; head[index] = q; } // 将单词处理结果写入文件 void write_to_file() { FILE *fp = fopen("result.txt", "w"); assert(fp); int i = 0; while (i < HASHLEN) { for (ptr_no_space p = head[i]; p != NULL; p = p->next) fprintf(fp, "%s %d\n", p->word, p->count); i++; } fclose(fp); } // 从上往下筛选，保持小根堆 void sift_down(node_has_space heap[], int i, int len) { int min_index = -1; int left = 2 * i; int right = 2 * i + 1; if (left <= len && heap[left].count < heap[i].count) min_index = left; else min_index = i; if (right <= len && heap[right].count < heap[min_index].count) min_index = right; if (min_index != i) { // 交换结点元素 swap(heap[i].count, heap[min_index].count); char buffer[WORDLEN]; strcpy(buffer, heap[i].word); strcpy(heap[i].word, heap[min_index].word); strcpy(heap[min_index].word, buffer); sift_down(heap, min_index, len); } } // 建立小根堆 void build_min_heap(node_has_space heap[], int len) { if (heap == NULL) return; int index = len / 2; for (int i = index; i >= 1; i--) sift_down(heap, i, len); } // 去除字符串前后符号 void handle_symbol(char *str, int n) { while (str[n] < '0' || (str[n] > '9' && str[n] < 'A') || (str[n] > 'Z' && str[n] < 'a') || str[n] > 'z') { str[n] = '\0'; n--; } while (str[0] < '0' || (str[0] > '9' && str[0] < 'A') || (str[0] > 'Z' && str[0] < 'a') || str[0] > 'z') { int i = 0; while (i < n) { str[i] = str[i+1]; i++; } str[i] = '\0'; n--; } } int main() { char str[WORDLEN]; for (int i = 0; i < HASHLEN; i++) head[i] = NULL; // 将字符串用hash函数转换成一个整数并统计出现频率 FILE *fp_passage = fopen("string.txt", "r"); assert(fp_passage); while (fscanf(fp_passage, "%s", str) != EOF) { int n = strlen(str) - 1; if (n > 0) handle_symbol(str, n); append_word(str); } fclose(fp_passage); // 将统计结果输入文件 write_to_file(); int n = 10; ptr_has_space heap = new node_has_space [n+1]; int c; FILE *fp_word = fopen("result.txt", "r"); assert(fp_word); for (int j = 1; j <= n; j++) { fscanf(fp_word, "%s %d", &str, &c); heap[j].count = c; strcpy(heap[j].word, str); } // 建立小根堆 build_min_heap(heap, n); // 查找出现频率最大的10个单词 while (fscanf(fp_word, "%s %d", &str, &c) != EOF) { if (c > heap[1].count) { heap[1].count = c; strcpy(heap[1].word, str); sift_down(heap, 1, n); } } fclose(fp_word); // 输出出现频率最大的单词 for (int k = 1; k <= n; k++) cout << heap[k].count << " " << heap[k].word << endl; return 0; }
2.2、统计出现次数最多的数据
题目描述：
给你上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。
    分析：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了。当然，也可以堆实现。
    ok，此题相当于上面的统计最热门的搜索，不过，咱们用红黑树取代之前的用hash表，来完成最初的统计，然后用堆更新，找出出现次数最多的前N个数据。
    完整代码如下：
//copyright@ zhouzhenren &&July //July、updated，2011.05.08. //题目描述： //上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据 //解决方案： //1、采用红黑树(本程序红黑树实现代码来源@July)等来进行统计次数。 //2、然后遍历整棵树，同时采用最小堆更新前N个出现次数最多的数据。 //同时，在遍历树的时候提供递归和非递归两种方式。 //本题目来源@July' blog：http://blog.csdn.net/v_JULY_v/archive/2011/03/26/6279498.aspx //声明：版权所有，引用请注明出处。 #define PARENT(i) (i)/2 #define LEFT(i) 2*(i) #define RIGHT(i) 2*(i)+1 #include <stdio.h> #include <stdlib.h> #include <string.h> typedef enum rb_color{ RED, BLACK }RB_COLOR; typedef struct rb_node { int key; int data; RB_COLOR color; struct rb_node* left; struct rb_node* right; struct rb_node* parent; }RB_NODE; RB_NODE* RB_CreatNode(int key, int data) { RB_NODE* node = (RB_NODE*)malloc(sizeof(RB_NODE)); if (NULL == node) { printf("malloc error!"); exit(-1); } node->key = key; node->data = data; node->color = RED; node->left = NULL; node->right = NULL; node->parent = NULL; return node; } /** * 左旋 * * node right * / \ ==> / \ * a right node y * / \ / \ * b y a b */ RB_NODE* RB_RotateLeft(RB_NODE* node, RB_NODE* root) { RB_NODE* right = node->right; // 指定指针指向 right<--node->right if ((node->right = right->left)) right->left->parent = node; // 好比上面的注释图，node成为b的父母 right->left = node; // node成为right的左孩子 if ((right->parent = node->parent)) { if (node == node->parent->right) node->parent->right = right; else node->parent->left = right; } else root = right; node->parent = right; //right成为node的父母 return root; } /** * 右旋 * * node left * / \ / \ * left y ==> a node * / \ / \ * a b b y */ RB_NODE* RB_RotateRight(RB_NODE* node, RB_NODE* root) { RB_NODE* left = node->left; if ((node->left = left->right)) left->right->parent = node; left->right = node; if ((left->parent = node->parent)) { if (node == node->parent->right) node->parent->right = left; else node->parent->left = left; } else root = left; node->parent = left; return root; } /** * 红黑树的3种插入情况 * 用z表示当前结点, p[z]表示父母、p[p[z]]表示祖父, y表示叔叔. */ RB_NODE* RB_Insert_Rebalance(RB_NODE* node, RB_NODE* root) { RB_NODE *parent, *gparent, *uncle, *tmp; //父母p[z]、祖父p[p[z]]、叔叔y、临时结点*tmp while ((parent = node->parent) && parent->color == RED) { // parent 为node的父母，且当父母的颜色为红时 gparent = parent->parent; // gparent为祖父 if (parent == gparent->left) // 当祖父的左孩子即为父母时,其实上述几行语句，无非就是理顺孩子、父母、祖父的关系。 { uncle = gparent->right; // 定义叔叔的概念，叔叔y就是父母的右孩子。 if (uncle && uncle->color == RED) // 情况1：z的叔叔y是红色的 { uncle->color = BLACK; // 将叔叔结点y着为黑色 parent->color = BLACK; // z的父母p[z]也着为黑色。解决z，p[z]都是红色的问题。 gparent->color = RED; node = gparent; // 将祖父当做新增结点z，指针z上移俩层，且着为红色。 // 上述情况1中，只考虑了z作为父母的右孩子的情况。 } else // 情况2：z的叔叔y是黑色的， { if (parent->right == node) // 且z为右孩子 { root = RB_RotateLeft(parent, root); // 左旋[结点z，与父母结点] tmp = parent; parent = node; node = tmp; // parent与node 互换角色 } // 情况3：z的叔叔y是黑色的，此时z成为了左孩子。 // 注意，1：情况3是由上述情况2变化而来的。 // ......2：z的叔叔总是黑色的，否则就是情况1了。 parent->color = BLACK; // z的父母p[z]着为黑色 gparent->color = RED; // 原祖父结点着为红色 root = RB_RotateRight(gparent, root); // 右旋[结点z，与祖父结点] } } else { // 这部分是特别为情况1中，z作为左孩子情况，而写的。 uncle = gparent->left; // 祖父的左孩子作为叔叔结点。[原理还是与上部分一样的] if (uncle && uncle->color == RED) // 情况1：z的叔叔y是红色的 { uncle->color = BLACK; parent->color = BLACK; gparent->color = RED; node = gparent; // 同上 } else // 情况2：z的叔叔y是黑色的， { if (parent->left == node) // 且z为左孩子 { root = RB_RotateRight(parent, root); // 以结点parent、root右旋 tmp = parent; parent = node; node = tmp; // parent与node 互换角色 } // 经过情况2的变化，成为了情况3. parent->color = BLACK; gparent->color = RED; root = RB_RotateLeft(gparent, root); // 以结点gparent和root左旋 } } } root->color = BLACK; // 根结点，不论怎样，都得置为黑色。 return root; // 返回根结点。 } /** * 红黑树查找结点 * rb_search_auxiliary：查找 * rb_node_t* rb_search：返回找到的结点 */ RB_NODE* RB_SearchAuxiliary(int key, RB_NODE* root, RB_NODE** save) { RB_NODE* node = root; RB_NODE* parent = NULL; int ret; while (node) { parent = node; ret = node->key - key; if (0 < ret) node = node->left; else if (0 > ret) node = node->right; else return node; } if (save) *save = parent; return NULL; } /** * 返回上述rb_search_auxiliary查找结果 */ RB_NODE* RB_Search(int key, RB_NODE* root) { return RB_SearchAuxiliary(key, root, NULL); } /** * 红黑树的插入 */ RB_NODE* RB_Insert(int key, int data, RB_NODE* root) { RB_NODE* parent = NULL; RB_NODE* node = NULL; parent = NULL; if ((node = RB_SearchAuxiliary(key, root, &parent))) // 调用RB_SearchAuxiliary找到插入结点的地方 { node->data++; // 节点已经存在data值加1 return root; } node = RB_CreatNode(key, data); // 分配结点 node->parent = parent; if (parent) { if (parent->key > key) parent->left = node; else parent->right = node; } else { root = node; } return RB_Insert_Rebalance(node, root); // 插入结点后，调用RB_Insert_Rebalance修复红黑树的性质 } typedef struct rb_heap { int key; int data; }RB_HEAP; const int heapSize = 10; RB_HEAP heap[heapSize+1]; /** * MAX_HEAPIFY函数对堆进行更新，使以i为根的子树成最大堆 */ void MIN_HEAPIFY(RB_HEAP* A, const int& size, int i) { int l = LEFT(i); int r = RIGHT(i); int smallest = i; if (l <= size && A[l].data < A[i].data) smallest = l; if (r <= size && A[r].data < A[smallest].data) smallest = r; if (smallest != i) { RB_HEAP tmp = A[i]; A[i] = A[smallest]; A[smallest] = tmp; MIN_HEAPIFY(A, size, smallest); } } /** * BUILD_MINHEAP函数对数组A中的数据建立最小堆 */ void BUILD_MINHEAP(RB_HEAP* A, const int& size) { for (int i = size/2; i >= 1; --i) MIN_HEAPIFY(A, size, i); } /* 3、维护k个元素的最小堆，原理与上述第2个方案一致， 即用容量为k的最小堆存储最先在红黑树中遍历到的k个数，并假设它们即是最大的k个数，建堆费时O（k）， 然后调整堆（费时O（logk））后，有k1>k2>...kmin（kmin设为大顶堆中最大元素）。 继续中序遍历红黑树，每次遍历一个元素x，与堆顶元素比较，x>kmin，更新堆（用时logk），否则不更新堆。 这样下来，总费时O（k*logk+（n-k）*logk）=O（n*logk）。 此方法得益于在堆中，查找等各项操作时间复杂度均为logk）。 */ //中序遍历RBTree void InOrderTraverse(RB_NODE* node) { if (node == NULL) { return; } else { InOrderTraverse(node->left); if (node->data > heap[1].data) // 当前节点data大于最小堆的最小元素时，更新堆数据 { heap[1].data = node->data; heap[1].key = node->key; MIN_HEAPIFY(heap, heapSize, 1); } InOrderTraverse(node->right); } } void RB_Destroy(RB_NODE* node) { if (NULL == node) { return; } else { RB_Destroy(node->left); RB_Destroy(node->right); free(node); node = NULL; } } int main() { RB_NODE* root = NULL; RB_NODE* node = NULL; // 初始化最小堆 for (int i = 1; i <= 10; ++i) { heap[i].key = i; heap[i].data = -i; } BUILD_MINHEAP(heap, heapSize); FILE* fp = fopen("data.txt", "r"); int num; while (!feof(fp)) { fscanf(fp, "%d", &num); root = RB_Insert(num, 1, root); } fclose(fp); InOrderTraverse(root); //递归遍历红黑树 RB_Destroy(root); for (i = 1; i <= 10; ++i) { printf("%d\t%d\n", heap[i].key, heap[i].data); } return 0; }

延伸阅读

• 2010-12-3-- 均值不等式,调查显示10月份全球芯片销售额均值稳定
• 2009-10-10-- 寻找中项算法:寻找第k大或第k小的算法 -- 内存足够(C++实现)
• 2009-2-12-- k均值算法:得到第K个大的数算法实现方法