[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Re: Issue: restrict <interleave>
Given words w, and w1, w2, ..., wn, is w in the interleaving of w1, w2, ..., wn? This problem is NP-complete ("Warmuth and Haussler, Onthe Compexity of Iterated Shuffle, Journal of Computer and Syste m Sciences, 1984" ) . Jing is usually very fast, but I have some malic ious schemas/insta n ces. 0) Elaps e d 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 interle a ving6.xml Elapsed time 60031 m illiseconds c:\inter l eave>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 i nterleaving6.xm l Elapsed time 1 00688 milliseconds c : \interleave>jing.bat c:\interleave>java -Xms50m -Xmx200m -cp jing.jar;c:\l ib\jaxp.jar;c:\xerces-1 _3_0\xerces.jar com.thaiopensource.relaxng.util.Driver interleavin g6 2.rng interleaving6.xm l Elapse d time 149391 millisecon d s c:\interleave>jing.bat c:\interleave>java -Xms50m -Xmx200m -cp jing.j ar;c:\lib\jaxp.jar;c:\xerces-1 _3_0\xerces.jar com.thaiopensource.relaxng.util.Driver inte rl eaving63.rng interleaving6.xm l Elapsed time 198359 mil l iseconds 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.Driv e r interleaving7.rng interleaving7 . xml Elapsed time 4 8 5375 milliseconds 1) interleaving6.rng interleaving61.rng, interleaving62.r ng, and interleaving63.rng has one, two, and three more <group>s, respectively. <element name="fo o" xmlns="http: //relaxng.or g/ns/structure/0.9"> <interleave> <group> <option al><element name="a"><empty/></element></optional> <optio nal><element name="b"><empty/></element></optional> <opti onal><element name="c"><empty/></element></optional> <opt ional><element name="d"><empty/></element></optional> <op tional><element name="e"><empty/></element></optional> <o ptional><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></optiona l> <optional><element name="e"><empty/></element></option al> <optional><element name="f"><empty/></element></optio nal> <optional><element name="g"><empty/></element></opti onal> <optional><element name="h"><empty/></element></opt ional> <optional><element name="i"><empty/></element></op tional> <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/></elemen t></optional> <optional><element name="d"><empty/></eleme nt></optional> <optional><element name="e"><empty/></elem ent></optional> <optional><element name="f"><empty/></ele ment></optional> <optional><element name="g"><empty/></el ement></optional> <optional><element name="h"><empty/></e lement></optional> <optional><element name="i"><empty/></ element></opt ional> <optional><element name="j"><empty/></element></optional> </group> <group> <optional><element name="a"><empty /></element></optional> <optional><element name="b"><empt y/></element></optional> <optional><element name="c"><emp ty/></element></optional> <optional><element name="d"><em pty/></element></optional> <optional><element name="e"><e mpty/></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/></e lement></opt ional> <optional><element name="j"><empty/></element></op tional> </group> <group> <optional><element nam e="a"><empty/></element></optional> <optional><element na me="b"><empty/></element></optional> <optional><element n ame="c"><empty/></element></optional> <optional><element name="d"><empty/></element></optional> <optional><element name="e"><empty/></element></optional> <optional><elemen t name="f"><empty/></element></optional> <optional><eleme nt name="g"><empty/></element></optional> <optional><elem ent name="h"><empty/></element></optional> <optional><ele ment name="i" ><empty/></elem ent></optio n a l> <optional><e l ement name= "j">< empty /></e lemen t></o ption al> < /grou p> </ i nterleave> </element > 2) interleaving6.xml <foo> <a/> <b/> <c/> <d/> <e/> <f/> <g/> < h/> <i/> < j/> </foo> 3) interleaving7.rng <element name="foo" xmln s="http://relaxng.org/ns/structure/0.9"> <interleave> < group> <optional><element name="a"><empty/></element></op tional> <optional><element name="b"><empty/></element></o ptional> <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/></elemen t></optional> <optional><element name="h"><empty/></eleme nt></optional> <optional><element name="i"><empty/></elem ent></optiona l> <op tional><element name="j"><empty/></element></optional> <o ptional><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"><empt y/></element></optional> <optional><element name="f"><emp ty/></element></optional> <optional><element name="g"><em pty/></element></optional> <optional><element name="h"><e mpty/></element></optional> <optional><element name="i">< empty/></elem ent></option al> <optional><element name="j"><empty/></element></optio nal> <optional><element name="k"><empty/></element></opti onal> </group> <group> <optional><element name= "a"><empty/></element></optional> <optional><element name ="b"><empty/></element></optional> <optional><element nam e="c"><empty/></element></optional> <optional><element na me="d"><empty/></element></optional> <optional><element n ame="e"><empty/></element></optional> <optional><element name="f"><empty/></element></optional> <optional><element name="g"><empty/></element></optional> <optional><elemen t name="h"><empty/></element></optional> <optional><eleme nt name="i">< empty/></ele ment></optional> <optional><element name="j"><empty/></el ement></optional> <optional><element name="k"><empty/></e lement></optional> </group> <group> <optional>< element name="a"><empty/></element></optional> <optional> <element name="b"><empty/></element></optional> <optional ><element name="c"><empty/></element></optional> <optiona l><element name="d"><empty/></element></optional> <option al><element name="e"><empty/></element></optional> <optio nal><element name="f"><empty/></element></optional> <opti onal><element name="g"><empty/></element></optional> <opt ional><element name="h"><empty/></element></optional> <op tional><eleme nt 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></optiona l> <optional><element name="h"><empty/></element></option al> <op tional><element name="i">< e m pty/></element></opti o nal> <opti onal> <elem ent n ame=" j"><e mpty/ ></el ement ></op tional> <optio na l><elem ent 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