Subject: Re: [xsl] A super-efficient way to compute the sum of A[i] * B[i] for i=1 to n? From: "Dimitre Novatchev dnovatchev@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Sun, 10 May 2020 18:53:34 -0000 |
For reference on fast sequential algorithms for computing the dot product, see this: https://lemire.me/blog/2018/07/05/how-quickly-can-you-compute-the-dot-product-between-two-large-vectors/ On Sat, May 9, 2020 at 10:52 AM Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote: > Hi Roger, > > > I need a super-efficient way to compute the sum of A[i] * B[i] for i=1 > to n. > > In case you have n cores / processors, and the compiler knows to optimize > functions like map(), zipWith() (for-each-pair() in XPath 3.0), then all > processors can each do a corresponding multiplication in parallel in a > single moment (computing cycle). > > Then what remains is the summing of the results of these multiplications. > This essentially is the map-reduce technique. > > Interestingly enough, while not all reduce operations can be parallelized, > in the case of sum() one can add together n numbers in Log2(n) summing > steps -- very similar to the DVC (DiVide and Conquer) technique, but doing > it parallel -- not sequentially. So, first there would be n/2 additions, > then n/4 additions (of the results of the first step), then n/8 additions, > and so on -- in a total of ceiling(Log2(n)) steps. If for each steps we > have sufficient number of processors (n/2 for the first step, less for the > following steps), then the summing could be performed in Log2(n) computing > cycles. > > So, it seems that the whole computation could be performed in something > like ~ ceiling(Log2(n)) + 1 computing cycles. > > Or maybe I am being wrong here? :) Please, correct me. > > Cheers, > Dimitre > > > On Sat, May 9, 2020 at 4:59 AM Costello, Roger L. costello@xxxxxxxxx < > 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 >> >> > > > -- > 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. > > -- 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.
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] A super-efficient way to , Dimitre Novatchev dn | Thread | Re: [xsl] A super-efficient way to , Dimitre Novatchev dn |
Re: [xsl] Joining list fragments, Michael Müller-Hille | Date | [xsl] Nested for-each-group and cur, Rick Quatro rick@xxx |
Month |