[Date Index]
[Thread Index]
[Author Index]
Re: More memory-efficient inner product for large last
*To*: mathgroup at smc.vnet.net
*Subject*: [mg106946] 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:19 -0500 (EST)
*References*: <201001251009.FAA09421@smc.vnet.net>
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
>>>>
>>>>
>>>>
>>>
>>
>
Prev by Date:
**Re: More memory-efficient inner product for large last**
Next by Date:
**Re: Can Mathematica interpolate non-uniform scatter data?**
Previous by thread:
**Re: More memory-efficient inner product for large last**
Next by thread:
**Re: More memory-efficient inner product for large last**
| |