xsl-list
[Top] [All Lists]

Re: [xsl] is there a way to hash an element?

2016-06-12 20:17:30
On Sat, Jun 11, 2016 at 05:21:09PM -0000, Dimitre Novatchev 
dnovatchev(_at_)gmail(_dot_)com scripsit:
Hi Dimitre --
Actually, I believe that calling deep-equal() can be more efficient
than comparing hashes.

The reason is simple: deep-equal() most probably returns false at the
first possible moment -- for example, noticing that an element has
different attributes than its counterpart.

On the other side, with hashing,  the hashes for the two whole
subtrees have to be calculated and only after that they can be
compared.

To summarize, with the exception of the case when the two subtrees are
equal, deep-equal may perform faster than generating and comparing
hashes on the subtrees.

I've got one input document with ~5000 trees that are mappable to XSD
schema definitions; about half are complexTypes.  Many are structurally
the same but have different names. (All ~5000 have unique names.)

The idea is to group them by structural sameness; deep-equal, even very
efficiently implemented deep-equal, gives me n^2 as I have to go through
the whole tree for each element and ask "are you like me?" pairwise.
Some of the equivalent structures will have a lot of matches -- hundreds
-- where I can't expect deep-equal to fail quickly and thus efficiently.

Going through and decorating every element with its hash value
(@hash="something") and then using for-each-group on the lot on the
basis of the hash gives me 2n.  Even if it's a very naive hash
implementation, I'd expect 2n to beat n^2 performance.

Am I missing something?

(I'll certainly keep deep-equal in mind if the hash approach has
unacceptable performance.)

-- Graydon
--~----------------------------------------------------------------
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>