多路归并算法(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[......]

继续阅读

Linux sort的四个小技巧

像排序这种事情,用C/C++可以写,但很麻烦,交给sort就好了,功能很强大的。

1、按照多个列排序(列间空格分开):

测试数据:

先按照第1列排序,再第2列的命令:

2011-11-20补充:必须加-s选项,表示stable sort,即两列排序互相不打扰。
$ cat ./test
1       x
5       8
1       a

$ sort -s -k 1 -k 2 ./test
1       a
1       x
5      [......]

继续阅读

让程序崩溃后生成Core Dump

在Linux下,程序崩溃是很头疼的事情(其实Windows更是如此)。

我们可以生成core dump文件,并用gdb重现崩溃时的场景。

ulimit设置core dump开关和大小
ulimit -c unlimited
测试代码:
#include <stdio.h>

int main(int argc, char* argv[])
{
    char * p = NULL;

    *p = 123;

    return 0;[......]

继续阅读

Search Engines: Information Retrieval in Practice – 第4章

Topic:Processing Text...

本章主题:文本处理

1、本章的主题:文本变换(Text Transformation)和文本处理(Text Processing)

2、将单词(Words)转化为可建索引的词项(Terms)的形式。

3、最懒的方法是:什么都不处理,这样,所有词都可以且只能被精确匹配。这样,诸如大小写、词形变换等导致的单词,就无法被检索出来。

4、分词(Tokenization):将段落转化为Words的过程。

5、归一化(St[......]

继续阅读