FLASHC

從24 hr 到 24秒的優化 multi pattern string match

把問題定義成這樣，
我有 9G的URL list 跟 一份 接近 500個 URL pattern brand list
因為amazon的URL有做SEO的優化，所以說 ，他的URL有包含 廠牌名字 我用brand list去過濾出我要的URL
再去爬取資料。

URL 內有100萬 的

1.
剛開始想說資料量不到用 python 的 in 去做然後 for 去 讓每一行做 in 500次的動作
結果出乎我意料的將近 24 hr的執行時間。

2.
後來改用 python 內的dict去把 Brand name 存起來
dict 是使用hash table 實作的，
時間複雜度 O(1)
核心的作法是
我 把每個 URL line 先用 filter的方式判斷
如果是 有 網址的line 再去判斷，這樣就減少了 1/2的量了。
我們相信 python stringlib的作者 告訴我們的 in 比其他東做快 6倍 Zzz就會得到 1的結果，
所以稍做修改。

變成 brand name都去做hash
然後把 URL line 出來 也拿去做hash
如果 URL line 的part在hash table裏面
那這一行就match 了

由於hash 的特性 所以現在只做單一節的 URL做拆解做hash
約做10分鐘左右

3.後來早上起來使用了 Sun Wu 大神的 agrep
秒殺 23.x秒 解決了同樣的 data

結論

1.sequence search 在量大時跟multi pattern 時 還是別想了....
2. agrep 很快
3. 演算法跟方式很重要。
4.簡單的一小步將是一大步
5.難怪老師都把問題reduce到最簡單的 sort 跟 search 問題上 因為這兩項 他幾乎無敵...!