xsl-list
[Top] [All Lists]

## Re: [xsl] HST's answers Re: [xsl] Efficient way to check sequence membership -

2011-03-02 18:06:56
```On 02/03/2011 22:00, Henry S. Thompson wrote:
```
```I've thought of five ways to do this:

1) tokenise and use "some ...", as in the previous message;
2) Add '|' at the beginning of both \$stopPat and the word to be
checked, and use contains;
3) Put a sequence of elements with a 'w' attribute whose value is a stop
in \$stops, then do boolean(\$stops/*[@w=\$w]);
4) As above, but then define an appropriate key and use
boolean(\$stops/key('stop',\$w));
5) Build a regexp and use match:
concat('^(',\$stopPat,')\$')

```
Your results don't surprise me. For all except (4), the naive implementation is O(n) whereas for (4) it is O(n log n). Now we don't know what n is, but if it's large enough then O(n log n) will always win. The fact that the different O(n) solutions have different multiplying factors is always worth remembering, of course.
```
```
I'd be interested to see what the results are using the more aggressive optimiser of Saxon-EE. I haven't got your data so I can't offer any measurements, but I did look at the -explain output for various ways of writing this expression, and the only one I found that constructed an index was the perhaps non-obvious
```
<xsl:sequence select="exists(\$stops[. = \$w])"/>

```
This suggests some opportunities for rewrites that I hadn't previously considered.
```
Michael Kay
Saxonica

```
```.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Version  raw time  time - baseline

0         5
4         7          2
2         8          3
2a        8          3
1a       14          9
1        15         10
3        28         23
5        30         25

where 0 is the baseline where the stop function does no actual work,
and the time is average over 100 iterations, in milliseconds.

I'm really interested if anyone has a better approach.  Of course, I'm
also interested to find out if other implementations show a similar
pattern.

I've put up a gzipped tar file [1] of all the files you need to
reproduce the experiment -- one .xsl for each version, and q.xml for
input.

The stopss.xsl file is there so you can test that you are getting the
check that the output is

243367200142031010020120103000130001022001513610014414440

ht

[1] http://www.ltg.ed.ac.uk/~ht/memberCheck.tar.gz
```
```

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

```
 Current Thread [xsl] Efficient way to check sequence membership, Henry S. Thompson Re: [xsl] Efficient way to check sequence membership, Dimitre Novatchev Re: [xsl] Efficient way to check sequence membership, Henry S. Thompson Re: [xsl] Efficient way to check sequence membership, Dimitre Novatchev Re: [xsl] Efficient way to check sequence membership, Imsieke, Gerrit, le-tex [xsl] HST's answers Re: [xsl] Efficient way to check sequence membership -, Henry S. Thompson Re: [xsl] HST's answers Re: [xsl] Efficient way to check sequence membership -, Michael Kay <= Re: [xsl] Efficient way to check sequence membership, David Carlisle