Re: More memory-efficient inner product for large last
- To: mathgroup at smc.vnet.net
- Subject: [mg106945] Re: [mg106870] More memory-efficient inner product for large last
- From: "Vincent N. Virgilio" <virgilio at ieee.org>
- Date: Fri, 29 Jan 2010 07:46:08 -0500 (EST)
- References: <201001251009.FAA09421@smc.vnet.net>
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>
- More memory-efficient inner product for large last dimension?