Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
>>>>>
>>>>>
>>>>>
>>>>
>>>
>>
>


  • Prev by Date: Re: Re: Re: Re: More /.{I->-1}
  • Next by Date: position of sequence of numbers in list
  • Previous by thread: Re: More memory-efficient inner product for large last
  • Next by thread: Redshift Calcs in Mathematica 7+