Category Archives: C && C++

试用开源分词系统SCWS

在前一段时间,使用了贵所的ICTCLAS分词系统,总体下来有两点不太满意:

1、分词速度奇慢,分词速度勉强能达到600KB/s

2、词库拓展麻烦,不加词库则分词效果欠佳。

3、无可用的授权

其实ICTCLAS本身,在贵所内部就存在诸多争议,譬如版权之争……具体细节不方便描述了。

国内有很多人,特别是学术界很推崇ICTCLAS,大家都觉得隐马是高级算法,效果自然会很好,譬如这篇很偏激的争论帖子:

http://www.oschina.net/question/9[......]

继续阅读

算法技术手册 – 排序 – 如何选择排序算法

实际上,没有绝对优秀的、应该始终采用的排序算法。

书上给出了一些选择不同排序算法的理由,写的非常好,抄录一下。

  • 元素很少:插入排序
  • 几乎有序:插入排序
  • 关注最差情况:堆排序(牢记:堆排序的最差时间复杂度依然是O(nlogn))
  • 平均较好:快速排序
  • 元素从密集范围取出:桶排序
  • 代码量小:插入排序

书上也在不同应用环境:字符串、浮点、几乎有序等情况下进行了测试,有兴趣的可以去翻阅。[......]

继续阅读

算法技术手册 – 排序 – 桶排序/哈希排序/散列排序

在前面的计数排序中,我们已经领略到了如何用空间换时间的方法,找到一种线性时间复杂度O(N)的排序算法。

计数排序的缺点也是非常明显的:一旦数据范围[0,k),中的k]相对于数据量N非常稀疏,计数排序的空间会非常大、时间消耗也会增大非常大。当然主要还是空间问题。

个人认为:桶排序 = 哈希排序 = 散列排序,基本思想是一样的。

于是桶排序/哈希排序应运而生,假设值域范围还是k,我们不去创建k个buckets,而是创建m个木桶,让N个元素通过哈系函数映射到这k个桶即可。这里还有一个[......]

继续阅读

算法技术手册 – 排序 – 计数排序

如果已知被排序的n个元素,值范围固定在在 "[0,k)"内],那么计数排序是最好的选择,它具有线性复杂度。

这个约束有些过强,有些时候,可以将不满足这个条件的转化一下:
比如 [-k, k)映射]到[0, 2k)等]。
再比如1/p的小树映射到p k-p等等。

下面上算法,主要走两遍:
首先建立k个桶
(1)扫描n个元素,增加对应桶中的计数
(2)从小到大扫描k个桶,计数非零则减一,然后顺序、依次输出。

源代码:
#include <stdio.h>[......]

继续阅读

推荐开源的INI文件解析器SimpleINI(c++)

在Python中,INI解析这种问题交给ConfigParser就行了,非常简单,但是C++显然没有原生的类库解决问题。
Windows下的ini API不是可移植的,所以无视它。

推荐一个非常好用的,跨平台的INI解析器:SimpleINI,支持section,读、写、各种value,遍历等。

网址:http://code.jellycan.com/simpleini/

旧代码废弃了,已经托管到github上:https://github.com/brofield/simp[......]

继续阅读