Category Archives: C && C++

数据结构重读 - 冒泡排序

发现自己学的最水的一门就是本科的数据结构了,我现在连冒泡排序都写不出来,sign。。。从今天开始重读数据结构。

冒泡排序:

对于有N个数的数组:

(1) 第1趟从第1个开始,如果arr[j] >= arr[j+1],swap(arr[j], arr[j+1])。本趟的结果是将最“大”的放在最后的位置上。
(2)第2趟仍然从第1个开始,执行大则swap但只执行到n-1的位置上,即次大的放到n-1上。
以此类推……
注:可优化,如果某一轮没有任何swap,说明已经有序了[......]

继续阅读

大量数据取k个最大值并排序

需求是这样的,我们都知道,在信息检索中,经常要取top-k(一共k,而不是第k)个得分最大的文档,并且从大到小排序。

而且文档规模很大,最少也要上千万。

话说这是一道很可以拿来面试的题啊。

我们不考虑Hadoop神马的,就说说单机怎么搞。

最傻的做法就是把1000万个都存储下来,然后sort,然后取min(k, vec.size())。

这样有两个缺点:
1、内存占用非常大,其实我们只要保留最大的1000个,但这样就要保存N个。在1000万的测试中,它要占用68M[......]

继续阅读

Xapian实现Simple BM25F

SimpleBM25F是BM25F的基础拓展版本,主要用于多个域的拓展,感兴趣的可以看《Simple BM25 Extension to Multiple Weighted Fields》。

主要观点:按照权重将不同域重复相应次数,拼成无结构的混合文本桶,然后只计算一次BM25得分。

而之前很多人采用的各个域先计算不同的BM25,再线性组合的做法,则破坏了词项独立性而效果很差。

传统:bm25.cpp
#include <xapian.h>
#include &[......]

继续阅读