[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Re: Explosion
James Clark wrote: > Incidentally, this has nothing to do with attribute wildcards. You could > equally well cause blow-up in the current JTREX implementation with a > sufficiently large choice of attributes. In my understanding, JTREX explodes when: 1) <oneOrMore> directly or indiretly contain <group> or <interleave> patterns. 2) at least one of them directly or indirectly contains multiple subpatterns with which many attributes of a single element match. That subpattern may be an attribute wildcard or large choice of attributes. For each of the many attributes of the element, we can consume one of the multiple subpatterns. If we have many attributes, combinatory explosion will usually happen. > This is just a limitation of JTREX. It doesn't memoize the construction of > derivatives for attributes. Just to prove to myself that this really was > the problem, I implemented a simple caching scheme for attribute > derivitives; with this fix, it could handle your cases with any exponential > increase in computation time. By memorizing derivatives, different branches will merge and thus combinatory explosion can be avoided. Cool, but too cool. I do not see any advantages in allowing patterns I described above. Cheers, Makoto
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC