Re: [xsl] A super-efficient way to compute the sum of A[i] * B[i]for i=1 to n?

["Costello, Roger L. costello@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>]

Thank you Michael, Michael, and Martin.

I measured the performance of this:

sum(for $i in 1 to count($A/col) return number($A/col[$i]) *
number($B/col[$i]))

and this:

sum(for $i in 1 to count($A) return number($A [$i]) * number($B [$i]))

in the latter, $A and $B holds the sequence of values in the <col> elements.

I ran the two versions 16.6 million times.

The first version (which involves finding the Nth child element) took: 0.670
seconds

The second version (which involves finding the Nth item in a sequence) took:
0.852 seconds

It is faster to find the Nth child element than to find the Nth item in a
sequence - surprising!

I used SAXON EE 9.1.4

/Roger

From: Michael Kay mike@xxxxxxxxxxxx <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Sent: Saturday, May 9, 2020 9:55 AM
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Subject: [EXT] Re: [xsl] A super-efficient way to compute the sum of A[i] *
B[i]for i=1 to n?

I doubt you'll find much improvement on this.

You could cut out the call on number() and rely on implicit conversion, but I
doubt it makes any difference.

You could factor out the expressions ($A/col) and ($B/col) into variables
declared outside the loop, which might make a difference: finding the Nth
child of an element might well take time proportional to N, whereas finding
the Nth item in a sequence held in a variable is likely to be constant time.
But it depends on the processor, of course. Measgre it and let us know the
results.

A significant part of the cost is likely to be string-to-double conversion,
and there's no way of avoiding that. 

Michael Kay
Saxonica



On 9 May 2020, at 12:59, Costello, Roger L. mailto:costello@xxxxxxxxx
<mailto:xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:

Hi Folks,

I need a super-efficient way to compute the sum of A[i] * B[i] for i=1 to n.

For example, suppose A is this:

<row>
   <col>0.9</col>
   <col>0.3</col>
</row>

and B is this:

<row>
   <col>0.2</col>
   <col>0.8</col>
</row>

I want to compute:

(0.9 * 0.2) + (0.3 * 0.8)

Here's one way to do it:

sum(for $i in 1 to count($A/col) return number($A/col[$i]) *
number($B/col[$i]))

I suspect that is not the most efficient approach.

What is the most efficient approach? I will be doing hundreds of thousands of
these computations, so I want to use the most efficient approach.

/Roger

http://www.mulberrytech.com/xsl/xsl-list
http://lists.mulberrytech.com/unsub/xsl-list/673357 ()