[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Re: Issue: restrict <interleave>
Kohsuke KAWAGUCHI wrote: > > It seems to me that there are lot of unnecessary line breaks in your > post and therefore it's hard to read. Sorry. Hopes this works. Cheers, Makoto ----------------------------------------------------------------------------------------------- Given words w, and w1, w2, ..., wn, is w in the interleaving of w1, w2, ..., wn? This problem is NP-complete ("Warmuth and Haussler, On the Compexity of Iterated Shuffle, Journal of Computer and System Sciences, 1984" ) . Jing is usually very fast, but I have some malicious schemas/instances which causes explosion. 0) Elapsed time c:\interleave>java -Xms50m -Xmx200m -cp jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar com.thaiopensource.relaxng.util.Driver interleaving6.rng interleaving6.xml Elapsed time 60031 milliseconds c:\interleave>jing.bat c:\interleave>java -Xms50m -Xmx200m -cp jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar com.thaiopensource.relaxng.util.Driver interleaving61.rng interleaving6.xml Elapsed time 100688 milliseconds c:\interleave>jing.bat c:\interleave>java -Xms50m -Xmx200m -cp jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar com.thaiopensource.relaxng.util.Driver interleaving62.rng interleaving6.xml Elapsed time 149391 milliseconds c:\interleave>jing.bat c:\interleave>java -Xms50m -Xmx200m -cp jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar com.thaiopensource.relaxng.util.Driver interleaving63.rng interleaving6.xml Elapsed time 198359 milliseconds c:\interleave>jing.bat c:\interleave>java -Xms50m -Xmx200m -cp jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar com.thaiopensource.relaxng.util.Driver interleaving7.rng interleaving7.xml Elapsed time 485375 milliseconds 1) interleaving6.rng interleaving61.rng, interleaving62.rng, and interleaving63.rng has one, two, and three more <group>s, respectively. <element name="foo" xmlns="http://relaxng.org/ns/structure/0.9"> <interleave> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> </group> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> </group> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> </group> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> </group> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> </group> </interleave> </element> 2) interleaving6.xml <foo> <a/> <b/> <c/> <d/> <e/> <f/> <g/> <h/> <i/> <j/> </foo> 3) interleaving7.rng <element name="foo" xmlns="http://relaxng.org/ns/structure/0.9"> <interleave> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> <optional><element name="k"><empty/></element></optional> </group> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> <optional><element name="k"><empty/></element></optional> </group> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> <optional><element name="k"><empty/></element></optional> </group> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> <optional><element name="k"><empty/></element></optional> </group> <group> <optional><element name="a"><empty/></element></optional> <optional><element name="b"><empty/></element></optional> <optional><element name="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><element name="h"><empty/></element></optional> <optional><element name="i"><empty/></element></optional> <optional><element name="j"><empty/></element></optional> <optional><element name="k"><empty/></element></optional> </group> </interleave> </element> 4) interleaving7.xml <foo> <a/> <b/> <c/> <d/> <e/> <f/> <g/> <h/> <i/> <j/> <k/> </foo> Cheers, Makoto
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC