News for hackers. Stuff that matters.

A comment on A Massively Parallel Computing Solution. Parent comment

Re:A Massively Parallel Computing Solution by thesz on Thursday October 09, 2014 @10:41AM (#8432615)
The problem with DFA is that they explode exponentially for number of choices containing ".*". Then you fail to get a locality of reference, etc. DFA also very sequential.

This is why NDAs are better - you can run several NDAs in parallel with their states and inputs. It basically becomes vectorized problem.

[ Parent | on HN ]
Re:A Massively Parallel Computing Solution by jeffreyrogers on Thursday October 09, 2014 @12:34PM (#8433444)
Yeah, so it becomes a space/time tradeoff. I think whether which is better depends on the problem you're solving. Many DFAs don't blow up space exponentially, so you'd rather have the DFA in that case. You're right though that for DFAs with an exponential increase in space requirements you are better off just doing the NDA in parallel.
[ Parent | on HN ]