我们已使用 terark.com 进行商业化运营

多音字 搜索词纠错: 匹配简拼(汉字数≥5时才有效)  单字的拼音来自:这里(最全的多音字)...     

当搜索词中有错别字时,搜索引擎会尝试纠错

通过相似拼音纠错

搜索引擎把这些字还原成拼音,用一个拼音相同的已知的搜索词代替。

这是一种众所周知的纠错策略,但是,当输错的字是多音字,特别是有多个这样的错误输入时,所有的搜索引擎都尽量绕开这个问题,或者仅使用最常用的那些音去纠错。 因为要考虑所有可能的拼音组合,在极端情况下会导致指数爆炸! 例如美团的实现(枚举多音字全排列)

基于自动机的算法可以完美解决这个指数爆炸问题

  • 这是自动机应用的又一个绝佳范例,作为演示,这个页面只收录了 800万搜索词+词频,数据也不太干净
  • 该算法全部在内存中运行,使用了 293M 内存,这个数据量,如果用传统方法暴力实现,并且达到这个性能,需要 几十G 的内存
  • 暴力方法是 Query 越长越可怕,该算法则是 Query 越长,优势越大
  • 纠错耗时仅供参考(单核虚拟云主机: Xeon E5-2430 2.20GHz + RAM:1.5G),如果你看到搜索耗时过长,很可能是mmap数据被swap到了硬盘上,再搜索一次会得到客观的搜索耗时

这个算法也可以用来解决用户输入预测(智能提示)功能

用户只输入Query开头部分,就自动提示出整个Query,例如用户输入举头望,就提示出举头望明月。就像现在各种搜索引擎做的那样。

基于编辑距离的纠错

在已知的搜索词中寻找编辑距离与用户 Query 最小的词,使用我的算法也可以高效解决(还没做演示页面)

MapReduce Key Revert ——特定数据模式的负载均衡

阅读更多关于《MapReduce Key Revert ——特定数据模式的负载均衡》

符号、记法

其中{k,v}指一个Key,Value对,{..} 中第一个分量是Key,第二个是Value

[e]指一个集合,其中的元素为e。 [{k,v}]就指一个{k,v}的集合。

继续阅读

memory pool 的高效实现(代码)

阅读更多关于《memory pool 的高效实现(代码)》

mpool.h

 

 

mpool.c

 

  

memory pool 的高效实现

阅读更多关于《memory pool 的高效实现》

memory pool

malloc可以分配任意大小的内存,因此,在malloc内部,保存了一些簿记信息(至少有一个包含内存块尺寸的信息)。调用free时,可以正确释放。

为了减少这些簿记开销,可以使用memory pool

根据使用情境,可以分为两种:

1.         只分配固定大小的内存块,速度最快(normal path10条机器指令)。

2.         可分配不同大小的内存块,速度稍慢,但比malloc快得多,也无簿记开销。

以下将分别说明

mpool

mpool可分配不同尺寸的内存。大多数时刻,都在内部分配。

销毁mpool时,会自动释放在mpool中未释放的内存。

mpool内部有一个包含多个不同尺寸fixed_mpoolarray,根据请求分配的内存大小,直接索引到相应的fixed_mpool来分配一个单元(cell)。

通过定义宏FEBIRD_MPOOL_ALLOW_BIG_BLOCK,就允许大于max_cell_size的内存分配。在这种情况下,使用标准的malloc分配内存,分配出去的内存有额外簿记(用双向链表串起来),以便在销毁mpool时自动释放。 

mpool graph

 

 fixed_mpool

尺寸固定的内存池,一旦创建,该内存池只能分配固定尺寸的内存单元(cell)。这在很多情况下都适用,例如链表结点、树节点、图结点、自定义的结构、等等。

用于stlmap/set/list再适合不过了——但是不能用于vector/deque等需要分配可变尺寸的容器。

fixed_mpool内部的多个chunk使用数组,类似std::vectoriNextChunk相当于vector.sizenChunks相当于vector.capacity,每次空间不够时扩张一倍。使用数组,而不是链表,有以下好处:

1.         有助于对齐——如果chunk_allocator是对齐(对齐>=32时)分配的,而chunk使用链表组织,就会在chunk开始处预留一个chunk头部,这会导致不对齐。

2.         如果cell_size也刚好较大且整除chunk_size,使用链表就会浪费将近一个cellcell_size – chunk_header_size)。

3.         如果不把连接信息保存在chunk header,就需要另外分配chunk结点,而分配chunk结点又需要其它内存分配函数。

空闲表使用单链表,因此,理论上每个cell最小必须能容纳一个指针,32位系统式4字节,64位系统式8字节,实现中使用8字节作为最小值。 

世界上应用最广泛的虚拟机是啥?

阅读更多关于《世界上应用最广泛的虚拟机是啥?》

别说是JavaVM!

正确答案:x86vm

x86本身是一个硬件vm,它的指令系统是一个vm指令系统,通过翻译层后,才交给下面的risk内核。

 

malloc/free 的开销,如何去掉这种开销?

阅读更多关于《malloc/free 的开销,如何去掉这种开销?》

一般的malloc实现,对一块已分配的内存,都有两个机器字的簿记,甚至更多。如果不需要排错,理论上讲,只需要一个字长的额外开销,用来记录这块内存的尺寸(放在intptr[-1]处是个好主意)。

为什么需要这个开销呢?因为free传入的只是个指针,它不知道要释放多大的内存,因此free内部必须通过某种方式来获得这块内存的尺寸。

可以想象,如果用 malloc/free 来作为一个关联数组(map)的分配器,要浪费不少内存。不过好在实际数据的尺寸往往比额外消耗要大很多,相比起来,浪费的比例不算很大,况且现在内存还很便宜。

其实,打造一个高效的分配器并不难,难的是它的适用范围(多线程?cell尺寸,chunk尺寸,对齐,排错…),如果可以忍受这些缺陷,或者说是限制,还是比较值得的。下一步就是它的灵活性——让它可以更加容易集成进其它系统。

对于C标准库,如果能增加一个/一族这样的分配器,还是很有价值的。从理论上讲,只要free时多传一个size参数,就可以完全去掉额外的开销。这样两个函数就可以做到:

这样做还有一个额外的好处,就是可以更好地对齐,假定程序需要按32字节对齐,malloc/free 就至少需要32字节做簿记,如果再加上内存越界检测,就需要64字节。salloc/sfree则只需要将分配的内存对齐到32字节边界即可。

 

但是这对程序的正确性要求很高,malloc/free中,内存越界检测可以很容易实现,而salloc/sfree就完全做不到(除非增加额外簿记)。一个好主意是可以在debug版中加入这些差错功能,而在release版中去掉。

 

更好(确切地讲应该是更灵活)的方案是,实现一个

 

而让 salloc/sfree简单地作为 mpool 的包装。

 

gcc的std::allocator基本上是按这样的方式实现的,只不过,它的size参数,大多数时刻是自动传递的(知道具体的class/struct,也就知道它的尺寸)。实现方式上,使用 size_aligned/align 作为索引去访问特定尺寸的mempool,一个 mempool 是多个链表串起来的大chunk,每个chunk内部是链表穿起来的cell。这也许是最好的实现方式了,除了节省的额外空间开销,时间开销上,如果不考虑加锁,一次alloc平均可以在10时钟周期内完成,dealloc用的时间更短。相比之下malloc/free耗的时间也要多得多。

可变长度数据结构

阅读更多关于《可变长度数据结构》

固定长度的数据结构很简单,大家每天都在用。

可变长度数据结构,都可以通过内嵌对象的形式,转化成固定长度的数据结构,大家每天也都在用,例如:

 

每个 person 对象的长度是固定的,但是,其内嵌的 name 和 address 是变长的。从而,整个对象占据的总空间也是变长的。

 

但是,将这样的的对象平坦化,使之只占据一块连续空间,使用的人很少,因为在绝大多数情况下,很少有人思考这个问题,并且,大多数问题已经使用内嵌数据结构解决掉了。

 

然而,如果内存很紧张,或者需要处理得数据量非常大,这种方式浪费的内存就太多了。假定我们现在创建了一个 map<int, person> ,在gcc4.1 的 64位环境中,按8字节对齐,这个 map 总共会占用多少内存呢?

  1. sizeof(map) = 48
  2. sizeof(string) = 8
  3. sizeof(person) = 24
  4. sizeof(person_node) = alignto(24 + 32(rbtree node overhead), 8) = 56
  5. sizeof(string_node) = 8*3(refcount, size_endptr, capacity_endptr)
  6. memsizeof(string) = sizeof(string_node) + alignto(strlen + 1, 8)
  7. memsizeof(person_node) = sizeof(person_node) + memsizeof(name) + memsizeof(address)

如果 avg(name) = 10, avg(address) = 20

实际占用的空间,大约还要再加上4:avg(name) = 14, avg(address) = 24

那么 memsizeof(person_node) = 56 + 24*2 + 14 + 24 = 142

那么该map 实际占用空间(gcc 的每个 map 还有一个虚结点:32个字节):

48+32+n*142 = 80+n*142

 

如果使用一种理想的变长数据结构,再加上红黑树的优化(none virtual node, compressed color, no parentptr),需要多少内存呢?

  1. sizeof(map) = 16
  2. memsizeof(person_node) = alignto(16(treenode) + 4(id) + 2*1(strlen) + 10(name) + 20(address) = 52, 8) = 56

memsizeof(map) = 16 + 56*n

 

内存一下节省了 60% 还多,也就是说,如果内存大小已经固定,可以装入 2.5 倍的数据。

  1. 如果用来做集群缓存,可以节省50%的机器(系统也要占一些内存)。
  2. 如果有5.6G的内存可用,就可以装入1亿条数据。
  3. 并且,在节省了60%内存的同时,还有另外一种好处:提高cache命中率,如果3个字段访问的频率相同,cpu的 cache miss 会降低3倍。
  4. 可以预见,因为cache miss降低,map.find 速度会大幅提高。

 

这个可变数据结构可以这样设计:

 

 

更复杂的情况:

  1. 如果nName 和 nAddress 要大于 255 呢?——把 unsigned char 改成 unsigned short, 甚至 unsigned int
  2. 如果person的字段很多,例如有20个字段:

 

这就不光是写代码的复杂了,运行时字段访问的性能也成问题!性能问题可以用另外一种方式——使用直接定位——来解决。

 

 

如果需要变长数据的数组,怎么办?简单,offset array + data byte array,具体实现方式与 person4 类似,只不过 offset array 元素需要使用更宽的整数。

 

 

管道的境界

阅读更多关于《管道的境界》

一直在想:如何在 Hadoop.MapReduce 中,插入一个 C 写的 HashFunction,既要高效,又要接口简洁。通过命令行实现调用显然是不行的。刚刚终于想出了:使用管道!

一个非常简单的程序,从stdin读入,写到stdout。多简单!至于效率,管道嘛,本质上就是异步的,自然是buffered&asynchronous 模式。

 

hash 程序

 

 

框架可以一边不断往管道写key,一边从中读取结果,这两个工作完全可以是异步的。对hash程序来说,如果stdin/stdout是全缓冲的,就几乎没有io的开销,因为几百几千次 fgets/printf 才会导致一次系统调用。

对frame程序也是一样的。

 

在 hadoop.streaming 中,hash 函数目前还必须由 java 类指定,如果使用这种方式,那就更 unix 了。

 

fuck淘宝,fuck原叶绿茶

阅读更多关于《fuck淘宝,fuck原叶绿茶》

昨天,渴了,买了瓶原叶绿茶,准备扣上盖子扔瓶子时,发现上面说:

N2KOKC5ND9L 十元淘宝券 兑奖09/11/30止口

跑到淘宝上看,找不着哪兑奖,后来终于发现:

http://pro.taobao.com/yuanye/yuanye_index.htm

输入号码,点击“适用10元抵价券商品区”结果是一大堆给我都不要的东西。

    我不殚以最坏的恶意来揣摩这些fuckee,可是,这些fuckee却如此侮辱我的智商。而且还是如此公开、如此明目张胆的侮辱。

    侮辱了大家的智商,还要浪费大家的时间,浪费大家的精力。如果买了它的东西,在你被侮辱的同时,人家还说:傻逼真乖,把钱给爷!

很基本也很诡异的fread

阅读更多关于《很基本也很诡异的fread》

memory FILE in C

阅读更多关于《memory FILE in C》

一直希望有个可以像 FILE* 一样使用的 memory file,正好,今天,在linux的stdio.h中找到了这个东西。

 

#define _GNU_SOURCE
#include <
stdio.h>

FILE *fmemopen(void *buf, size_t size, const char *mode);

FILE *open_memstream(char ** ptr, size_t *sizeloc) ;

 

详细说明:http://linux.die.net/man/3/open_memstream

 

fmemopen 有用之处主要在于从内存中读取,使用 fscanf。当然也可以写,如果是为了写,并且随后再读,可以将 buf 和 size指定为 NULL,0,这样写时会自动增加内存。

 

open_memstream 就主要用于写了,比如生成sql语句: