Hi, Bob.
If the wording of my previous message offended you, I apologize. That
certainly wasn't my intent. I think this is more a case of
miss-interpretation rather than actual disagreement.
Bob Foster wrote:
Orlando wrote:
What are you talking about when you say exponential heap? With the
most naive
implementation possible, the largest your memoization heap could be
is (n * m).
That's linear!
Not O(n log n), not O(n^2), not O(n^3), not O(n^m) and certainly not
O(m^n).
Ok, I was going to let this go, seeing that it was useful to Terence,
but my first reaction was, what on earth are they teaching these days?
Then the lecturing "Not..." line... Gee. Is this a list of all the
non-linear complexities you could think of? Here's a couple you forgot:
O(n!), not linear. O(n*m), not linear.
As it happens, I didn't list all the non-linear complexities I could
think of. Being the lazy hacker I am, I didn't bother to think and just
went here.
http://en.wikipedia.org/wiki/Big_O_notation#Common_orders_of_functions
I then listed, in ascending complexity, the orders of the functions
between linear and exponential. At the end of my list I asserted
"certainly not O(m^n)."
The point of my list was to illustrate that there are quite a number of
jumps in complexity from linear to exponential. (3-5 depending on
whether you count O(n^2) and O(n^3) as just being types of O(n^m).)
Hopefully, that explains why I didn't include factorial.
It could be you were thinking of O(n+m), the complexity of depth-first
search, or you might have been recalling reports that the n*m table in
the original packrat algorithm is very sparse when parsing e.g., Java
or C. In fact the number of m actually cached seems to be bounded by a
small constant. Therefore, for these grammars and input the storage
overhead is for all practical purposes O(n).
As for O(n*m), I assumed we were using 'm' to represent the constant
factor that counts the number of expressions that one might memoize? If
that isn't the common interpretation on this list then, again, I apologize.
Assuming 'm' is constant, O(n*m) is linear. We all know that.
As you point out, what value 'm' has will depend on the grammar.
Further, actual runtime depends on the input string and, of course, the
implementation.
Orlando.
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
