Re: More memory-efficient inner product for large last

*To*: mathgroup at smc.vnet.net*Subject*: [mg106947] Re: [mg106870] More memory-efficient inner product for large last*From*: Leonid Shifrin <lshifr at gmail.com>*Date*: Fri, 29 Jan 2010 07:46:30 -0500 (EST)*References*: <201001251009.FAA09421@smc.vnet.net>

Hi Vince, Wow, this looks really much more elegant than my original version, and also has a normal matrix multiplication functionality - really cool. Thanks for an update! Regards, Leonid On Thu, Jan 28, 2010 at 7:21 PM, Vincent N. Virgilio <virgilio at ieee.org>wrote: > Fixed version, gives results identical to the Ur-code. Note the Take and > Min. > > Vince > > dot[first_?ArrayQ, second_?ArrayQ, n1_:2, n2_:1] := > Module[{plus, a, b, fdims, sdims}, > fdims = Dimensions@first // Take[#, Min[Length@#, n1] ]&; > sdims = Dimensions@second // Take[#, Min[Length@#, n2] ]&; > > plus[x_, y_] := Total[{x, y} /. {z_a :> ( first[[##]]& @@ z), > z_b :> (second[[##]]& @@ z)}]; > plus[x__] := Fold[plus, First@{x}, Rest@{x}]; > > Array[a, fdims] . Array[b, sdims] /. Plus -> plus > ]; > > > > On Thu, Jan 28, 2010 at 10:57 AM, Vincent N. Virgilio <virgilio at ieee.org>wrote: > >> Whoops. My version has a bug. I haven't tested the fix yet, but I think >> "Most" should be replace by "Take" (n1 or n2). >> >> Vince >> >> >> On Thu, Jan 28, 2010 at 10:38 AM, Vincent N. Virgilio <virgilio at ieee.org>wrote: >> >>> Leonid, >>> >>> Here's what I settled on. It's your implementation, without the >>> withs, and a couple of final integral arguments, which mimic Outer's. I >>> don't think it sacrifices much if any efficiency. >>> >>> dot[first_?ArrayQ, second_?ArrayQ, n1_:2, n2_:1] := >>> Module[{plus, a, b, >>> fdims = Dimensions@first // If[ArrayDepth@first > n1, Most@#, >>> #]&, >>> sdims = Dimensions@second // If[ArrayDepth@second > n2, Most@#, >>> #]&}, >>> >>> plus[x_, y_] := Total[{x, y} /. {z_a :> ( first[[##]]& @@ z), >>> z_b :> (second[[##]]& @@ z)}]; >>> plus[x__] := Fold[plus, First@{x}, Rest@{x}]; >>> >>> Array[a, fdims] . Array[b, sdims] /. Plus -> plus >>> ]; >>> >>> Thanks again. >>> >>> Vince >>> >>> On Mon, Jan 25, 2010 at 11:54 AM, Leonid Shifrin <lshifr at gmail.com>wrote: >>> >>>> Vince, >>>> >>>> Actually I must apologize. The intended code was >>>> >>>> Clear[dotLazy]; >>>> dotLazy[first_?ArrayQ, second_?ArrayQ] := >>>> With[{fdims = Most@Dimensions@first, sdims = Most@Dimensions@second}, >>>> Module[{a, b, plus}, >>>> With[{firstSymbolic = Array[a, fdims], >>>> secondSymbolic = Array[b, sdims]}, >>>> plus[x_] := x; >>>> plus[x__] /; Length[{x}] =!= 2 := Fold[plus, First@{x}, Rest@{x}]; >>>> plus[x_, y_] /; Head[x] =!= plus := >>>> Total[{x, y} /. {a[i_, j_] :> first[[i, j]], >>>> a[i_] :> first[[i]], b[i_] :> second[[i]], >>>> b[i_, j_] :> second[[i, j]]}]; >>>> firstSymbolic.secondSymbolic /. Plus -> plus]]]; >>>> >>>> which is different from the one I posted by plus[x_, y_] /; Head[x] =!= >>>> plus instead of >>>> plus[x_, y_] /; Head[x] =!= Plus (plus vs Plus). This was intended to >>>> avoid infinite recursion >>>> for cases like plus[plus[1,2],3], but actually, due to the way Fold >>>> wroks, this is unnecessary >>>> alltogether. Likewise, the rule plus[x_]:=x is an unnecessary garbage. >>>> Some intermediate variables >>>> can also be skipped. The following will work just as well, while being >>>> a bit more concise: >>>> >>>> >>>> Clear[dotLazy]; >>>> dotLazy[first_?ArrayQ, second_?ArrayQ] := >>>> Module[{fdims, sdims, firstSymbolic, secondSymbolic, a, b, plus}, >>>> plus[x_, y_] := Total[{x, y} /. {z_a :> (first[[##]] & @@ z), >>>> z_b :> (second[[##]] & @@ z)}]; >>>> plus[x__] := Fold[plus, First@{x}, Rest@{x}]; >>>> Dot @@ MapThread[ >>>> Array, {{a, b}, Most@Dimensions@# & /@ {first, second}}] /. >>>> Plus :> plus] >>>> >>>> >>>> >>>> Regards, >>>> Leonid >>>> >>>> >>>> >>>> >>>> >>>> On Mon, Jan 25, 2010 at 5:53 PM, Vincent N. Virgilio <virgilio at ieee.org >>>> > wrote: >>>> >>>>> >>>>> >>>>> On Mon, Jan 25, 2010 at 9:16 AM, Leonid Shifrin <lshifr at gmail.com>wrote: >>>>> >>>>>> Hi Vince, >>>>>> >>>>>> I suggest that you use lazy matrix multiplication, which can be >>>>>> implemented for example as follows: >>>>>> >>>>>> >>>>>> >>>>> SNIP >>>>> >>>>> >>>>>> As can be seen, my version is less memory-efficient for list-to-list >>>>>> dot product, but vastly >>>>>> more efficient for other operations. I did not test on such huge lists >>>>>> as your original ones since >>>>>> I don't have so much memory at my disposal at the moment (running >>>>>> Eclipse and SQLDeveloper), >>>>>> but I would expect similar effect. >>>>>> >>>>>> Hope this helps. >>>>>> >>>>>> Regards, >>>>>> Leonid >>>>>> >>>>>> >>>>> Leonid, >>>>> >>>>> Phenomenal work! Yours saved ~ 1.5GB RAM over mine (for 1.2M elements). >>>>> >>>>> Thank you very much. >>>>> >>>>> Vince Virgilio >>>>> >>>>> >>>>> >>>> >>> >> >

**References**:**More memory-efficient inner product for large last dimension?***From:*Vince Virgilio <blueschi@gmail.com>