xsl-list
[Top] [All Lists]

Re: [xsl] Efficient XPath 2.0 expression to return each <row> element for which there are other <row> elements having the same navaid?

2018-12-13 12:38:37
Hi Roger,
If using XSLT, use <xsl:key> and the key() function.

If not, the provided solution has time complexity O(N^2)

If XPath 3 is available one can use maps for probably the fatest
solution -- I believe it will be like O(N) -- depending on the values
distribution.

Without maps, one can write their own sorting function (sort() is a
standard function only in XPath 3.1) and then use a binary search-like
technique. This will be O(N*log(N))

Cheers,
Dimitre
On Thu, Dec 13, 2018 at 10:07 AM Costello, Roger L. 
costello(_at_)mitre(_dot_)org
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:

Hi Folks,

I have a large XML document containing data about airports around the world:

<airports>
    <row>
        <navaid>A</navaid>
    </row>
    <row>
        <navaid>B</navaid>
    </row>
    <row>
        <navaid>A</navaid>
    </row>
</airports>

Notice that there is only one <row> element having the B navaid, but two 
<row> elements having the A navaid.

I want an XPath 2.0 expression to return each <row> element for which there 
are other <row> elements having the same navaid. For the above example, I 
want the XPath expression to return the first and third <row> elements.

Here is one way to do it:

//row[navaid = (preceding-sibling::row/navaid, following-sibling::row/navaid)]

Eek! That is horribly inefficient. I ran that XPath expression on my XML 
document and it took a long time to finish.

Is there an efficient XPath 2.0 expression to solve this problem?

Note: I am running the XPath expression from Oxygen's XPath evaluator, not 
from an XSLT program.

/Roger




-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all
------------------------------------
Quality means doing it right when no one is looking.
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
To achieve the impossible dream, try going to sleep.
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
Typing monkeys will write all Shakespeare's works in 200yrs.Will they
write all patents, too? :)
-------------------------------------
Sanity is madness put to good use.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--

<Prev in Thread] Current Thread [Next in Thread>