Written by 需求是这样的，我们都知道，在信息检索中，经常要取top-k(一共k，而不是第k)个得分最大的文档，并且从大到小排序。
而且文档规模很大，最少也要上千万。
话说这是一道很可以拿来面试的题啊。
我们不考虑Hadoop神马的，就说说单机怎么搞。
最傻的做法就是把1000万个都存储下来，然后sort，然后取min(k, vec.size())。
这样有两个缺点：
1、内存占用非常大，其实我们只要保留最大的1000个，但这样就要保存N个。在1000万的测试中，它要占用68M[......]
Posts in category 算法&数据结构
大量数据取k个最大值并排序
多路归并算法(K-Way Merge Algorithm)
多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k。
(1)假设有K路数据流，流内部是有序的，且流间同为升序或降序
(2)首先读取每个流的第一个数，如果已经EOF，pass
(3)将有效的k(k可能小于K)个数比较，选出最小的那路mink，输出，读取mink的下一个
(4)直到所有K路都EOF
代码如下：
/*
* main.c
*
* Created on: 20[......]
算法技术手册 – 查找 – 散列查找(Hash查找)
对于含有n个元素的集合C，我们先构造一个Hash函数，让n映射到b个桶内，当选择合理时，速度会很快，时间复杂度O(1)。
完美哈希函数：不会产生冲突，是存在的。
对于>=1个值映射到同一个桶的情况下，就会发生碰撞。处理方法：
- 链表：每个桶拉一个链表，第一遍散列后，在链表中查找是否存在元素。
- 开放定址：构造双变量散列函数h(u, j)。h(u, 0) = h(u)，此时退化为原始散列函数。
开放定址，分两类：
- 线性探测h(u, j)=(h(u)+j) m[......]
算法技术手册 – 查找 – 顺序查找
顺序查找也叫线性查找，是最简单的查找算法。穷举法遍历每个元素，查找是否包含元素t。
平均、最坏性能O(N)
#include <stdio.h>
typedef int TYPE;
int search(TYPE* arr, int n, TYPE t)
{
int i=0;
for(i=0; i<n; i++)
{
if(arr[i]==t)
{
re[......]
算法技术手册 – 排序 – 如何选择排序算法
实际上，没有绝对优秀的、应该始终采用的排序算法。
书上给出了一些选择不同排序算法的理由，写的非常好，抄录一下。
- 元素很少：插入排序
- 几乎有序：插入排序
- 关注最差情况：堆排序（牢记：堆排序的最差时间复杂度依然是O(nlogn)）
- 平均较好：快速排序
- 元素从密集范围取出：桶排序
- 代码量小：插入排序
书上也在不同应用环境：字符串、浮点、几乎有序等情况下进行了测试，有兴趣的可以去翻阅。
最近评论