robot
最新文章(10)
Mqskit 和其它相關工具
CPython 的 GC 二、三事
寫 Mecurial Extension 是件快樂的事!
Mozilla 台灣辨公室徵人啟事
關於 Apple 的兩項專利
core dump 之前的 frame
怎麼發出 beep 聲?
先承認你要找的是奴才吧!
程式碼要清的多乾淨?
FreeBSD 的 Thread-Local Storage 實作
首頁
新編
最新留言
Entries RSS
重要關鍵字(10)
coding (122)
Python (93)
FreeBSD (71)
WEB (61)
URL (48)
hardware (46)
javascript (36)
Linux (34)
blog (30)
C++ (16)
所有關鍵字
新增 URL
回應 O(log(n)) 的 regex associative array
by thinker
2 Columns
關鍵字:
coding
linkname:[William Yeh] http://william.cswiz.org/blog/ 寫了一篇「 linkname:[尋找 O(log(n)) 的 regex associative array] http://william.cswiz.org/blog/archives/2008-05-10/regex-associative-array/ 」討論如何在O(log(n)) 的時間複雜度下，從字串映射 (mapping) 至以 regex 定義的資料項目。(n 是 regex 的數量) 在一瞬間，腦袋只閃過一個觀念「regular expression 能透過建立 FSM/FSA (Finite State Machine/Automata) 的方式實作」，於是我們能將所有的 regular expression 對映的 FSM 組合成一個更大的 FSM ，再將 accept state 當作 associate key ，於是我們得到一個 O(log(n)) 的資料結構。如果再進一步安排 accept state ，使之成為連續的編號，或直接將資料 attach 在 accept state，那我們能更進一步得到 O(1) 的資料結構。 然而缺點是，我們可能得花 O(n) 的時間去做 insert 新 key 的動作。在 index 遠多於 insert 的情況下，我們能 leverage 這個資料結構的優勢。
最後更新時間: 2008-05-10 19:13:44 CST |
引用
查詢:
COMMENTS: