At 2010-02-19 15:42 +0000, Andrew Welch wrote:
> Concerning performance: I am afraid that the solutions Ken came
up with were not very optimized for large sequences. They have a
logarithmic complexity. Let me provide a solution that has a linear complexity:
Shouldn't that be exponential... logarithmic is better than linear
isn't it? :)
I was copying the gist of the example from the specification for node
uniqueness. And from what I can figure out, for n input items
deep-equal will be called (n*(n-1))/2 times, not n**2 times, to find
the m unique values.
Then to filter those m items for the result will take at most m*(m-1)
times for deep-equal to find p result values, and only when there are
no distinguishing testVal values. As long as there are testVal
values the number of calls to deep-equal will be less.
While I like Geert's suggestion of keying a hash of the node tree in
XSLT so as to reduce the number of accesses to the source node tree,
there really may not be as many as might appear on the surface. And
anyway optimization in the processor might be able to implement
deep-equal quickly with internal sub-tree hashes and occupying
heavy-lifting cycles only to establish bona-fide uniqueness when the
hashes are equal.
I hope this helps. Some empirical evidence will support going to the
effort of making the algorithm faster.
. . . . . . . . . Ken
--
XSLT/XQuery training: after http://XMLPrague.cz 2010-03-15/19
XSLT/XQuery training: San Carlos, California 2010-04-26/30
Principles of XSLT for XQuery Writers: San Francisco,CA 2010-05-03
XSLT/XQuery/UBL/Code List training: Trondheim,Norway 2010-06-02/11
Vote for your XML training: http://www.CraneSoftwrights.com/q/i/
Crane Softwrights Ltd. http://www.CraneSoftwrights.com/q/
G. Ken Holman mailto:[email protected]
Male Cancer Awareness Nov'07 http://www.CraneSoftwrights.com/q/bc
Legal business disclaimers: http://www.CraneSoftwrights.com/legal
_______________________________________________
General mailing list
[email protected]
http://xqzone.com/mailman/listinfo/general
