python - Why does this take so long to match? Is it a bug? -


i need match urls in web application, i.e. /123,456,789, , wrote regex match pattern:

r'(\d+(,)?)+/$'

i noticed not seem evaluate, after several minutes when testing pattern:

re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523')

the expected result there no matches.

this expression, however, executes (note trailing slash):

re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523/')

is bug?

there catastrophic backtracking going on cause exponential amount of processing depending on how long non-match string is. has nested repetitions , optional comma (even though regex engines can determine wouldn't match attempting of extraneous repetition). solved optimizing expression.

the easiest way accomplish 1+ digits or commas followed slash , end of string: [\d,]+/$. however, not perfect since allow ,123,,4,5/.

for can use optimized version of initial try: (?:\d,?)+/$. first, made repeating group non-capturing ((?:...)) isn't necessary provides "cleaner match". next, , crucial step, stopped repeating \d inside of group since group repeating. finally, removed unnecessary group around optional , since ? affects last character. pretty 1 digit, maybe comma, repeat, , followed trailing /.

this can still match odd string 1,2,3,/, heck of improved original regex negative lookbehind: (?:\d,?)+(?<!,)/$. assert there no comma directly before trailing /.


Comments

Post a Comment

Popular posts from this blog

Python Kivy ListView: How to delete selected ListItemButton? -

Image
i'm trying learn kivy building simple todo-list app suggested dusty phillips, author of book "creating apps in kivy". this code far: from kivy.app import app kivy.uix.boxlayout import boxlayout kivy.properties import objectproperty kivy.uix.listview import listitembutton class taskbutton(listitembutton): pass class todoroot(boxlayout): task_input = objectproperty() task_list = objectproperty() def add_task(self): self.task_list.adapter.data.extend([self.task_input.text]) self.task_list._trigger_reset_populate() def del_task(self): pass class todoapp(app): def build(self): return todoroot() if __name__ == '__main__': todoapp().run() and kv file: #: import main todo #: import listadapter kivy.adapters.listadapter.listadapter #: import listitembutton kivy.uix.listview.listitembutton todoroot: <todoroot>: orientation: "vertical" task_input: task_input_view t...
Read more

ruby - How do I merge two hashes into a hash of arrays? -

http://codepad.org/wmyzqlis i'd merge these 2 arrays: a = { :a => 'a', :b => 'b', :d => 'd' } b = { :a => '1', :b => 'b', :c => 'c' } into hash looks this: {:a => ["a", "1"], :b => ["b", "b"], :c => [nil, "c"], :d => ["d", nil] } this doesn't work: p a.merge(b) { |k, v1, v2| [v1, v2] } # {:c=>"c", :a=>["a", "1"], :b=>["b", "b"], :d=>"d"} it's because hash#merge call block duplicate keys. a = { :a => 'a', :b => 'b', :d => 'd' } b = { :a => '1', :b => 'b', :c => 'c' } hash[(a.keys|b.keys).map { |key| [key, [a.fetch(key, nil), b.fetch(key, nil)]] }] # => {:a=>["a", "1"], :b=>["b", "b"], :d=>["d", nil], :c=>...
Read more