GO Darts

[Andy W. Song]

https://github.com/awsong/go-darts 

用于静态字典搜索和Common Prefix Search，key在10万左右的时候比go map快4倍，大了没测过，这个算法的复杂度是O(K)，K是检索key的长度，跟字典大小没关系。缺点是字典是静态生成的。 这里这个可以插入，不过比较罗嗦，所以没照这个做。 

下面准备用这个把mmseg中文分词做一下。

--

---------------------------------------------------------------

有志者，事竟成，破釜沉舟，百二秦关终属楚

苦心人，天不负，卧薪尝胆，三千越甲可吞吴

[junyi sun]

顶一个，" 比go map快4倍 "是指什么操作？

2012/3/30 Andy W. Song <wso...@gmail.com>

--
来自: Golang-China ~ 中文Go语言技术邮件列表
详情: http://groups.google.com/group/golang-china
官网: http://golang-china.org/
IRC: irc.freenode.net #golang-china
@golangchina

[Andy W. Song]

读操作，因为darts就不支持插入。
我一个10万单词的字典，在我的机器上遍历一遍所有key，map用46毫秒，darts unicode version用9.5.

等我把mmseg写好，看看这我原来用map的版本比快了多少吧，因为有了common prefix search，可以同时减少检索次数，肯定是会快很多的。

2012/3/31 junyi sun <ccn...@gmail.com>

[junyi sun]

性能很好啊。双数组Trie，学习一下。

我之前也写过一个类似的库，是python+c 的。  http://code.google.com/p/sdict/ 

2012/3/31 Andy W. Song <wso...@gmail.com>

[gix...@gmail.com]

在 2012-3-31 中午12:07，"Andy W. Song" <wso...@gmail.com>写道：
>
> 读操作，因为darts就不支持插入。
> 我一个10万单词的字典，在我的机器上遍历一遍所有key，map用46毫秒，darts unicode version用9.5.
> 等我把mmseg写好，看看这我原来用map的版本比快了多少吧，因为有了common prefix search，可以同时减少检索次数，肯定是会快很多的。

期待你的测试结果

[Wenqiang Song]

MMSEG完工，比map版本快2到3倍，但是还是没有C++版快，唉。当然C++版实现方式不一样。比较科学的是直接benchmark darts go/c++，懒得弄了，有兴趣的上吧。

2012/4/16 <gix...@gmail.com>

--