From: Brian H. <bh...@sp...> - 2004-07-25 15:57:50
|
On 25 Jul 2004, skaller wrote: > Is it so rare? Consider backtracking parser for say, C++, I'd come up with more or less the same example. Note that there are two ways to push back tokens. One is to 'undo' the remove operations by going back to an older version of the data structure. The other way is to just use the prepend operation to push the previously popped elements back onto the front of the queue- this operation is O(1) strict. We could make this faster by offering a "concat" operation, which concatenates two queues into one: val concat: 'a t -> 'a t -> 'a t let concat (afront, aback) (bfront, bback) = (List.append afront (List.rev_append aback bfront)), bback Given this operation, you could "cache" the tokens you pull out of the main queue into a temporary queue. Then, instead of replaying the remove, you just mass-prepend the temporary queue. This sidesteps the O(N) problem. Also, in this case several other constraints don't apply. You're not going to have a lot of tokens on a single line, so N is going to be small. You generally don't back up and reparse the line repeatedly- once, maybe twice, yeah, but not 18 gazillion times. > The question is: is the dual list data structure a nice > data structure?? You're right. I like this question better. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |