要从一个文件中查出以唯一字符串 a 开头的那一行,怎么能提高查询效率。 我现在的方法很笨:
这样感觉效率很低,因为文件有17万行,所以最低也要循环17万次... 初学者希望得到大家的帮助,谢谢。
认证0级讲师
把这个文件处理成一个用字典树(trie)或者B树存储的结构,然后就可以快速查询了。
前面说得可能太抽象,给你一个容易实现的算法吧。效率虽然比trie/b-tree略低,但是也很够用。
1. 遍历这个文件,记录每行的offset记录下来,作为int的数组。 2. 对这个数组进行间接排序。注意,所谓间接,指的是排序时比较的是这个数组元素指向的行。 3. 将这个数组保存起来(17w个int,也就不到700KB,随便什么地方保存)。
1. 读取这个数组。 2. 使用"间接"二分查找。注意,查找时比较的是对应行的前n个字符,n == strlen(a)。
如果看不懂这个算法的话,那就洗洗睡吧。
以唯一字符串a开头,意思是说,第一个是a,第二个不是a么?
<?php $file = "./test.txt"; $lines = file($file); foreach($lines as $line_num => $line) { $line = trim($line); $len = strlen($line); if ($len > 0 and $line[0] == "a" and ($len == 1 or $line[1] != "a") ) { echo $line . "\n"; } } ?>
没必要用正则吧,不知道PHP里面正则会不会提前compile,效率如何。
额。。。。直接把符合的行给匹配出来好了。整个文件一次读取作为一个字符串。。。 然后用正则,匹配首字母是a的行。。既然你都说是行了,哪必然有换行符的嘛。。。
把这个文件处理成一个用字典树(trie)或者B树存储的结构,然后就可以快速查询了。
前面说得可能太抽象,给你一个容易实现的算法吧。效率虽然比trie/b-tree略低,但是也很够用。
预处理
1. 遍历这个文件,记录每行的offset记录下来,作为int的数组。
2. 对这个数组进行间接排序。注意,所谓间接,指的是排序时比较的是这个数组元素指向的行。
3. 将这个数组保存起来(17w个int,也就不到700KB,随便什么地方保存)。
查询
1. 读取这个数组。
2. 使用"间接"二分查找。注意,查找时比较的是对应行的前n个字符,n == strlen(a)。
如果看不懂这个算法的话,那就洗洗睡吧。
以唯一字符串a开头,意思是说,第一个是a,第二个不是a么?
没必要用正则吧,不知道PHP里面正则会不会提前compile,效率如何。
额。。。。直接把符合的行给匹配出来好了。整个文件一次读取作为一个字符串。。。
然后用正则,匹配首字母是a的行。。既然你都说是行了,哪必然有换行符的嘛。。。