Autocompete with Trie

像微薄里面用户输入一个@会从服务器取出匹配的用户login name什么的。这种场景用前缀树比较节省空间并且效率高。fast trie——A super fast, efficiently stored Trie for Ruby。据作者说速度是灰常的快。。
地址：https://github.com/tyler/trie

gem install fast_trie

require 'trie'

TRIE = Trie.new

#初始化数据
User.all.each do |user|
  TRIE.add(user.login_name, 0)
end

#js调用autocomplete
def autocomplete
    children = sort_by_weight(TRIE.children(params[:prefix]))

    respond_to do |format|
      format.js { render(:string => JSON.dump(children)) }
    end
  end

根据用户的输入行为给某个key增加权重(用于搜索排序)：
def incr_weight(login_name, n = 1)
  weight = TRIE.get(login_name) || 0
  TRIE.add(login_name, weight + n)
end

#根据权重给结果排序
def sort_by_weight(login_name_list)
  login_name_list.sort_by{|login_name|  TRIE.get(login_name)}
end

这东西的性能不错啊 这是测试数据，看样子比那个redis的autocomplete要简单高效呀：

引用

Performance Characteristics

Here are some quick benchmarks on my 2.4ghz Intel Core 2 Duo MacBook Pro:

For keys that are 5 characters long:
31,344 adds/second
1,827,408 searches/second
38,453 prefixes searches/second

For keys that are 10 characters long:
30,653 adds/second
1,802,649 searches/second
13,553 prefix searches/second

For keys that are 20 characters long:
30,488 adds/second
1,851,461 searches/second
5,855 prefix searches/second

For keys that are 40 characters long:
30,710 adds/second
1,838,380 searches/second
2,762 prefix searches/second

不过好像不能被序列化。这样在多进程部署的时候有点麻烦呀。再研究一下。。

评论

1 楼 Hooopo 2011-04-20  

Why-is-the-autocomplete-for-Quora-so-fasthttp://www.quora.com/Why-is-the-autocomplete-for-Quora-so-fast