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

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

通过相似拼音纠错

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

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

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

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

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

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

基于编辑距离的纠错

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

枚举变量扩展

阅读更多关于《枚举变量扩展》

在很多配置文件中,都会牵涉到变量扩展,一个变量会有多少种可能的扩展结果,这在静态分析中非常重要。这里给出一个算法,使用 perl 来表达(expand.pl),变量引用使用统一的形式:${varname}。 继续阅读

gcc C++0x unique_ptr 实现太龌龊了

阅读更多关于《gcc C++0x unique_ptr 实现太龌龊了》

版本:g++ 4.6.0

龌龊之处: 继续阅读

C++0x 几个很败的修改

阅读更多关于《C++0x 几个很败的修改》

Until November 2009, std::future was named std::unique_future

Until November 2010, std::launch::deferred was named std::launch::sync.


 

 

非对称类型的 Comparator

阅读更多关于《非对称类型的 Comparator》

 

结构体数组,按字段查找

我有一个按字段 name 排好序的结构体数组,怎样使用 stl 来查找?

 

 

 

怎样定义 CompareName ?

 

 

一般的 Compare 这样定义:

 

这样的 Compare 只能用于排序,如果要用于查找,我们必须先构造一个 User 对象,再把想查找的name assign 这个 User::name, ….

 

terminal 的显示编码为 utf8 时用 vim 打开 gb2312/gbk/gb18030 编码的文件

阅读更多关于《terminal 的显示编码为 utf8 时用 vim 打开 gb2312/gbk/gb18030 编码的文件》

vim "+e ++enc=gbk filename"

vim "+e ++enc=cp936 filename"

 

 

怎样区分 const char* 和字符串文字量

阅读更多关于《怎样区分 const char* 和字符串文字量》

在一个面试中,猛然间一闪念,问到了 candidate 这个问题。无解……

 

stl 中使用到了很多 traits 技术,只要懂得 traits ,这个问题就太简单了!以下是代码示例:

软件工程中很多地方,如果采用直接的办法不能解决问题,增加一个间接层,问题即迎刃而解,type_traits 就是这样一种技术,这个代码示例是自包含的,除了 printf ,没有任何其它外部依赖。

 

 

 

为什么下面这样的代码不能work?

 

答案:C++的重载匹配规则:如果在非模板的候选中能找到一个”精确”匹配,就不会去找模板。”精确”的精确定义包含3大类,5种具体情况,按顺序如下:

Identity Conversion —- 不需要任何转化,最精确,级别 1

Lvalue to Rvalue Conversion — 左值到右值转化,  级别 2

Array to Pointer Conversion — 数组到指针转化,  级别 3

Function to Pointer             — 函数名到函数指针, 级别 4,这就是为什么很多时候我们不需要使用 &func_name 而直接使用 func_name

 

Quolification Conversion      — cv qualify 少的可以转化到 cv qualify 多的,级别 5

 

这也就是为什么下面的代码可以 work:

 

char -> int 不是 exact match, 是 integeral promotion.

 

long -> int 不是 exact match, 是 integeral conversion.

 

 

 

将递归转化成迭代的通用技术

阅读更多关于《将递归转化成迭代的通用技术》

从理论上讲,只要允许使用栈,所有的递归程序都可以转化成迭代。

但是并非所有递归都必须用栈,不用堆栈也可以转化成迭代的,大致有两类

  1. 尾递归:可以通过简单的变换,让递归作为最后一条语句,并且仅此一个递归调用。

 

  1. 自顶向下->自底向上:对程序的结构有深刻理解后,自底向上计算,比如 fibnacci 数列的递归->迭代转化。

 

 

对于非尾递归,就必须使用堆栈。可以简单生硬地使用堆栈进行转化:把函数调用和返回的地方翻译成汇编代码,然后把对硬件 stack 的  push, pop 操作转化成对私有 stack 的 push, pop ,这其中需要特别注意的是对返回地址的 push/pop,对应的硬件指令一般是 call/ret。使用私有 stack 有两个好处:

  1. 可以省去公用局部变量,也就是在任何一次递归调用中都完全相同的函数参数,再加上从这些参数计算出来的局部变量。
  2. 如果需要得到当前的递归深度,可以从私有 stack 直接拿到,而用递归一般需要一个单独的 depth 变量,然后每次递归调用加 1。

我们把私有 stack 元素称为 Frame,那么 Frame 中必须包含以下信息:

  1. 返回地址(对应于每个递归调用的下一条语句的地址)
  2. 对每次递归调用都不同的参数

通过实际操作,我发现,有一类递归的 Frame 可以省去返回地址!所以,这里又分为两种情况:

  • Frame 中可以省去返回地址的递归:仅有两个递归调用,并且其中有一个是尾递归。

 

  • Frame 中必须包含返回地址的递归,这个比较复杂,所以我写了个完整的示例:
    • 以MergeSort为例,因为 MergeSort 是个后序过程,两个递归调用中没有任何一个是尾递归
    • MergeSort3 使用了 GCC 的 Label As Value 特性,只能在 GCC 兼容的编译器中使用
    • 单纯对于这个实例来说,返回地址其实只有两种,返回地址为 0 的情况可以通过判断私有栈(varname=stk)是否为空,stk为空时等效于 retaddr == 0。如果要精益求精,一般情况下指针的最低位总是0,可以把这个标志保存在指针的最低位,当然,如此的话就无法对 sizeof(T)==1 的对象如 char 进行排序了。

    •  

怎么减少错误的发生

阅读更多关于《怎么减少错误的发生》

错误,我们暂且仅对软件开发而言。

 

错误的类别,暂且仅考虑接口错误实现错误

 

  • 接口错误
    • 一般可以分为误解失配
    • 误解

比如在一段公路入口有巨大的标识牌,上面写着:前方道路,靠左行,红灯行,绿灯停。这个大家可能觉得很荒谬,然而类似的事情在软件开发里面却层出不穷,生产方认为自己已经在文档中清楚地说明了用法和用途,然而他却没有意识到这与使用方的常识和惯例背道而驰。举个简单的例子,C 标准库里面的两个函数:

我不知道有多少人用过这两个函数,但是,大体上,应该是用 fwrite 的人多,而用 qsort 的人少。而用 fwrite 的人,大多数情况下,传递的 size 都等于 1,并且,一般情况下,size 和 count 搞反了也不会有啥大问题,除非判断了返回值。然而,一旦用多了 fwrite,并且吧 ObjectSize, ObjectCount 这个顺序当成了一个常识,再使用 qsort 的时候,就悲剧了!

还有一个例子:stl 的 range,一般表示为前闭后开的 [begin, end) 区间,如果你要搞一个前开后闭的 (begin, end] 区间,大家都会疯掉不可。我确实曾经被这样的 (begin, end] 疯掉过。

  •  
    • 失配

一般情况下,发生在版本兼容问题上。我仅举一个简单例子:在Bash3.x中,[[]] 中的正则表达式会按Bash的quoting removal 规则进行处理,也就是说对于一般的正则表达式,加单引号,双引号,和不加引号,都没有区别,然而到了Bash4.x,如果加了引号,就悲剧了!Bash4.x会把引号当成正则表达式的一部分!

 

  •  
    • 另一种接口错误

最近我在挤地铁时发现了另一类错误,看上去似乎不属于这两种:人很挤的时候,在地铁楼梯上,经常发现,人们走的是左边,而不是右边,稍微用心一下,就会发现这是什么原因——人们总是按贪心算法走最短路径,刚下地铁的人,会走挨地铁(车厢)的楼梯一侧,而这一侧正好是左边,上面往下走的人,却是走右边。在人流量不大的时候,这不是什么问题,然而,当人流汹涌时,造成的拥堵让大家都很郁闷。

怎么解决这个问题呢?——那就是在设计地铁站时,让贪心算法的最短路径是右边,而不是左边。再General一点,就是:设计要遵守人们的思维习惯。

在程序设计上,如果我们设计的接口符合人的思维习惯,可以大大减少错误的发生。在 C 里面,至少有两处设计违反人的直觉,不过还好,这两处早被 deprecate 了:

  1.  
    1.  
      1.  函数的默认返回值为 int,而非 void  
      2.  f() 表示可接受任意个参数,返回值为 int 的函数。 
  • 实现错误

一般情况下,就是指我们程序的逻辑错误

C++ 如何动态库实现接口兼容

阅读更多关于《C++ 如何动态库实现接口兼容》

看了一篇文章:避免使用虚函数作为库的接口

 

其中提到C++虚表的僵硬,导致版本更新时二进制兼容性的问题。

 

其实这个问题不是C++的问题,而是C++实现的问题。如果接口的二进制兼容性是一个强制需求,在不影响运行效率的情况下,C++是完全可以实现的,不过需要多一点的空间开销和初始化开销。

 

 

具体的方法可以参考 PE 文件中的 Import Table 和 Export Table。

简单地讲,就是 App 和 DLL 各自维护一个 name->func_address 的映射数组,当然,这个 name 应该是名字碾碎后的 name 。 加载 DLL 时,将 DLL 中 Export Table 中相应项填到 App 中相应的 Import Table 中,App 中的虚函数调用仍然到那个地方去取函数指针,但是对不同版本的 DLL,甚至是不同实现的 DLL,那个值是不同的,这没有任何问题。

 

具体的算法,在 PE 文件中,Import Table 中的项一般比相应 DLL 的 Export Table 项少得多,所以,它使用二分查找(当然,它还有很多优化,如 hint, by ordinal,bound import 等等)。对于虚函数的情形,因为 Import 和 Export 的项数差不多,使用 Merge 算法会更快一点。

 

以前在做嵌入式系统的时候,会把绝大部分函数都放到查找表中,也是类似的道理,因为 ROM 最便宜,然而 ROM 是 Read Only Memory,release 之后,客户买到产品,要修改怎么办?还好,系统中不是光有ROM,还要少量 EEPROM,于是,事情就好办了,查找表和 Fix 的新代码,都可以放到 EEPROM 中,只需要在更新系统时将 Fix 的新函数地址填入查找表中相应的位置。

 

如果C++哪天要统一abi,这样的东西应该是必不可少的。

 

 

靠谱的程序员太少了

阅读更多关于《靠谱的程序员太少了》

 

最近几个月,面试了不少的程序员,更好听的名字叫做软件工程师,甚至高级软件工程师。

我一般会针对面试者的特长,问一些相关的问题。有说擅长算法的,图像处理的,图形学的,数学的,C++的,Java,Perl 的,Shell 的,Linux内核的……

到目前为止,面试的人不算太多,但少说也过100了,基本上,语言方面和其它特长兼有的,一个也还没碰到过。

靠谱的C++程序员,所谓的靠谱,其实也就是:

  1. 了解 STL 的常用组件,能正确使用 STL
  2. 知道 type_traits ,以及如何使用 type_traits
  3. 对虚函数、重载、虚表有一定了解
  4. 能正确认识C++的异常
  5. 了解 Pure C 和 C++ 的 C 子集中比较常见的、明显的区别

基本上,就这 5 点,能有两点比较突出的,也就那么两三个人,而这两三个人里面,C++差不多就是他们唯一的特长了。

 

Java 上,我问的问题比较少,远不如 C++ 多,并且更简单,也就是:

  1. int/long 的二进制位数,jvm 是否在不同平台 int/long 的二进制位数是否相同
  2. 对于 StringBuilder,每次追加一个字符,当其长度长到 n 时,时间复杂度是多少
  3. 能否把一个 String 对象,添加到一个 List<Integer> 中
  4. Comparable 和 Comparator 有何区别,如何把非 Comparable 的对象作为 TreeMap 的 Key
  5. GC 的基本原理(大部分人的回答是调节 gc 参数)

目前还没碰到一个人能回答第 4 个问题!呜呼!

 

算法+Coding:

  1. 90%以上的人不知道 make_heap 的时间复杂度,知道的人,也都是背的答案。
  2. 完全无 bug 的 binary_search ,只有 3% 。
  3. std::lower_bound 类似功能的函数,目前还没一个人写得出来。
  4. 从一组 IP range –> value 的数据中查找单个 IP,允许使用 C++ stl 或 java 基础类,还没一个能给出解决办法。
  5. QuickSort 的最好情况,和 MergeSort 的最好情况,哪个的 KeyCompare 次数更少,目前只有一个人答出。

如果在这些之外,还熟悉 perl, bash, python 等脚本语言的,更是凤毛麟角。

 

要知道,这些职位可都是年薪20w以上的!

欢迎同道之士加盟,可以站内联系我,有内部推荐机会。