[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: A super-efficient way to compute the sum of A[i] *
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.
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|