From: Tim X Date: 2007-04-12T21:00:06+09:00 Subject: Re: Slow ruby regexes "Robert Dober" writes: > Subject: Re: Slow ruby regexes > > On 4/12/07, Tim X wrote: >> "Robert Dober" writes: >> > >> >> Guys, I think your possibly mixing up backtracking and backreferences. It is >> backreferences (referencing a earlier match, often to use as part of the >> definition of a latter match) that NFA is not able to do. > No Tim I was not mixing it up, I said that I was not interested in the > backreferencing history. > You see I am just forgetting the basic stuff but Ola and Mental kindly > gave me a refresher. >> both approaches use >> backtracking. > The DFA cannot use backtracking, surely I am missing something *again*! Doh! >>The NFA approach is able to parallelise the choices, reducing the >> overheads of backtracking. So, given n different possible paths to follow, >> instead of, in the worst case, trying n-1 paths and having to backtrack after >> each one, you can try all n paths at once. At least, I htink thats what the >> article was saying form a very quick read and from what I can remember from my >> computability course and finite automata (oh so many years ago now!). > For me it is 25 years and for you? Nearly the same - computability course was 82/83, but I did go back an do som postrad in early 90s, so my knowledge cache should have been fresher! Guess its >> that bloody LRU memory cache algorithm trying to make room again! > Yeah I understood that in the same way, actually it is quite simple :) >> Its funny, back in the 80..83, the courses I enjoyed the most were computability, parallel processing, compilers and assembly. Now, when I think about anything in those areas, I just have vague recollections and no real facts. Since those days, work has been about databases, dull user interface programming, 4GLs, web technology etc. Up until 4 months ago, it was an increaseing deluge of project management methodologies, bullshitp bingo management speak, HR, budgets and sales. Now I'm getting back to bare boned technology and its scary how much I've forgotten! Still, at least I'm now looking at Ruby (amongst many other things!). Tim -- tcross (at) rapttech dot com dot au