w********n
发帖数: 137 | 1 门外汉请教基本CS问题，非面试题，是实际需要解决的问题。
一个Server Side 的程序，需要抓取多个页面，只保留页面信息如果页面的文字满足以下
要求
1 包含至少一个设备类型字符串 [phone tablet pc ebook ..]（数组预先定义好的，
大小10）
2 包含至少一个地址信息字符串 [Arizona, California, Texas ...]（数组预先定
义好的，大小100）
3 包含至少一个品牌信息字符串 [apple asus samsung rim ...]（数组预先定义好的
，大小10）
举例， 如果页面含有 .... Texas .... Samsung .... smartphone ....
那么就就是满足条件的。大小写无所谓。
假如文件大小N， 三个数组大小分别为M1, M2, M3
for each string in file
————if string inside M1
————else return
————if string inside M2
————else return
————if string insdie M3
————else return
end for
复杂度 O (Nx (M1+M2+M3))
有无其他更好（CPU Times）算法?
可以不用先考虑语言，但是prefer Java 或者 Python, Perl，可以用（regex）
No Map-reduce available |
g*****g
发帖数: 34805 | 2 这个简单，你把所有的字符串放进一个哈希表，设3个标志位，bit或boolean都可以。
哈希表对应的值就是这些标志位。顺序扫描，当3个标志位都满足的时候即可退出。
这是个O(N)的操作。可以起多个线程并行。
以下
【在 w********n 的大作中提到】
: 门外汉请教基本CS问题，非面试题，是实际需要解决的问题。
: 一个Server Side 的程序，需要抓取多个页面，只保留页面信息如果页面的文字满足以下
: 要求
: 1 包含至少一个设备类型字符串 [phone tablet pc ebook ..]（数组预先定义好的，
: 大小10）
: 2 包含至少一个地址信息字符串 [Arizona, California, Texas ...]（数组预先定
: 义好的，大小100）
: 3 包含至少一个品牌信息字符串 [apple asus samsung rim ...]（数组预先定义好的
: ，大小10）
: 举例， 如果页面含有 .... Texas .... Samsung .... smartphone ....
|
w********n
发帖数: 137 | 3 但是忘了说
像 "New York" 这样的地名应该被作为一个字符串搜查，
以上的方法都会miss掉
(如果用空格把输入文件split成字符串时)
foreach addr in address_list
___if addr inside input_file //use string search function
______do somthing
___else
______do something
如果这样做会不会很慢 |
g*****g
发帖数: 34805 | 4 Instead of a simple hashmap, you can build a trie or suffix tree to do the
string match.
【在 w********n 的大作中提到】
: 但是忘了说
: 像 "New York" 这样的地名应该被作为一个字符串搜查，
: 以上的方法都会miss掉
: (如果用空格把输入文件split成字符串时)
: foreach addr in address_list
: ___if addr inside input_file //use string search function
: ______do somthing
: ___else
: ______do something
: 如果这样做会不会很慢
|
