84669 person learning
152542 person learning
20005 person learning
5487 person learning
7821 person learning
359900 person learning
3350 person learning
180660 person learning
48569 person learning
18603 person learning
40936 person learning
1549 person learning
1183 person learning
32909 person learning
项目需要添加一个关键字过滤的功能,基本思路如下:
1.从服务器获取关键字数据,根据首字母保存到关键字字典中(key->关键字首字母,value->相同首字母的关键字的数组)2.获取用户输入字符串,从左侧截取字符,取得字符首字母,并在关键字字典中匹配对应的数组3.从右侧截取字符,于2中取得的数组进行折半查询4.如查询到关键字,替换关键字为等长*
但实际应用中对于过长的字符串效率太低想问问大家有没有什么好的方法正则表达式是现在已知的比较好的方法,可是实在是写不出来。。。
光阴似箭催人老,日月如移越少年。
我感觉你描述的是不完全的字典树。数据组织的结构:
(key->关键字首字母,value->相同首字母的关键字的数组)
以及这一步:
从右侧截取字符,于2中取得的数组进行折半查询
让我觉得比较奇怪,不明白为什么要这样。
我觉得有两种做法可以改进:
要在原有的基础上改进,可以实现字典树。从服务器取到的关键字数据,根据首字母分成各个分支,每个分支根据第二个字母再分成各个分支,每个分支根据第三个字母再分成各个分支……
也就把你描述的数据结构改成了
(key->关键字首字母,value->(key->第二个字母,value->(key->第三个字母,value->()),……))
查询的时候先按第一个字母查,进入某个分支,然后按第二个字母进入某个分支,然后第三个字母…… 直到查到/查不到为止。
这样建立树需要一些时间,但是查询是非常快的。最长的字符串有多少个字母,就最多需要多少次查询,也就是查询的速度与关键词的个数没关系了。
我觉得上面的做法还是挺麻烦的,为何不 Hash 一下呢?把服务器取到的每个关键词(完整的,不分字母了)保存在 Hash 数组里(在 iOS 里的NSDictionary里即可),然后把用户输入直接查一下就行了呗?难道这样不是最方便、最快的吗?
NSDictionary
我感觉你描述的是不完全的字典树。数据组织的结构:
以及这一步:
让我觉得比较奇怪,不明白为什么要这样。
我觉得有两种做法可以改进:
第一种做法:字典树
要在原有的基础上改进,可以实现字典树。从服务器取到的关键字数据,根据首字母分成各个分支,每个分支根据第二个字母再分成各个分支,每个分支根据第三个字母再分成各个分支……
也就把你描述的数据结构改成了
查询的时候先按第一个字母查,进入某个分支,然后按第二个字母进入某个分支,然后第三个字母…… 直到查到/查不到为止。
这样建立树需要一些时间,但是查询是非常快的。最长的字符串有多少个字母,就最多需要多少次查询,也就是查询的速度与关键词的个数没关系了。
第二种做法:Hash
我觉得上面的做法还是挺麻烦的,为何不 Hash 一下呢?把服务器取到的每个关键词(完整的,不分字母了)保存在 Hash 数组里(在 iOS 里的
NSDictionary
里即可),然后把用户输入直接查一下就行了呗?难道这样不是最方便、最快的吗?