On Thu, 06 May 2010 17:07:12 -0400, Walter Bright
<newshou...@digitalmars.com> wrote:
Steven Schveighoffer wrote:
That can't be it. The identifier shown by Alex is only 33 characters.
O(n^2) is not that slow, especially for smaller variables. There must
be other factors you're not considering...
I recompiled dmd with the profiler (-gt switch) which confirmed it.
So a single unknown symbol (from Alex's example) which can be checked
against each existing symbol in O(n^2) time, takes 40 seconds on a decent
CPU? How many other symbols are there? 33^2 == 1089, if there are 10000
symbols, that's 10 million iterations, that shouldn't take 40 seconds to
run, should it? Are there more symbols to compare against? Do you use
heuristics to prune the search? For example, if the max distance is 2,
and the difference in length between two strings is >2, you should be able
to return immediately.
-Steve
