这是一个创建于 4067 天前的主题，其中的信息可能已经有所发展或是发生改变。
在网上下到2000w的csv，基于文本的搜索最快的的方式就是grep了吧。
1.那么如果 grep 'foo|bar' finename.txt 是否相当于先做一遍grep foo，再做一遍grep bar?
对大文件搜索才体会到了性能问题。
2.google的秒搜是基于一种什么思想呢？
http://v2ex.com/t/65589 这里提到
===========
我提供一个思路给你，在索引里面，定长数据查询效率要远远高于不定长数据，url是不定长数据，但是可以转变成为定长，如果散列足够随机，冲突不大的话，那么可以考虑，比如：
把url转换成为long值，hash(url) -> id
long值的范围是 2^64，说实话，我不认为你能达到产生冲突的可能性
然后做非uniq索引，在每次查询结果列表里面做遍历，在冲突小的情况下，每次基本返回一条数据。
如果你的数据量很小，允许一定误差，那就根本不考虑冲突的情况。
这其实就是hash的基本思想。
===========
hash都定长的话，就不需要通过诸如Knuth–Morris–Pratt algorithm的算法来匹配吗？
已读了
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://en.wikipedia.org/wiki/String_searching_algorithm
1.那么如果 grep 'foo|bar' finename.txt 是否相当于先做一遍grep foo，再做一遍grep bar?
对大文件搜索才体会到了性能问题。
2.google的秒搜是基于一种什么思想呢？
http://v2ex.com/t/65589 这里提到
===========
我提供一个思路给你，在索引里面，定长数据查询效率要远远高于不定长数据，url是不定长数据，但是可以转变成为定长，如果散列足够随机，冲突不大的话，那么可以考虑，比如：
把url转换成为long值，hash(url) -> id
long值的范围是 2^64，说实话，我不认为你能达到产生冲突的可能性
然后做非uniq索引，在每次查询结果列表里面做遍历，在冲突小的情况下，每次基本返回一条数据。
如果你的数据量很小，允许一定误差，那就根本不考虑冲突的情况。
这其实就是hash的基本思想。
===========
hash都定长的话，就不需要通过诸如Knuth–Morris–Pratt algorithm的算法来匹配吗？
已读了
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://en.wikipedia.org/wiki/String_searching_algorithm
 |
1
miaoever 2013-10-16 21:32:27 +08:00
都 hash 了，得到的 key 是一个数字，所以可以用 O(1) 的时间复杂度找到对应的值，而不用再进行字符串查找。
|
 |
2
jason52 OP 哦，对~~相当于查字典，知道一个词在第几页，就不用从a到z顺序遍历，直接翻页码就好了。是这个比方吧。
|
|
3
jason52 OP 建hash相当于费一点空间给字典建一个目录，都是以空间换时间，但建好了在找速度就快了。
|
 |
4
senghoo 2013-10-16 23:51:56 +08:00 via iPad
Google 的搜索思想请参考hadoop的原理，差不多。大规模分布式计算。不是这种常规的hash查找。
|
 |
5
rrfeng 2013-10-17 08:58:50 +08:00
求 csv 下载 XD……
|
Select Language