Extending Plus very slow
- To: mathgroup at smc.vnet.net
- Subject: [mg66761] Extending Plus very slow
- From: Giuseppe Bilotta <bilotta78 at hotpop.com>
- Date: Mon, 29 May 2006 06:06:03 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Still working with extending the internals of Mathematica to deal with
AffineExpression objects, I found an interesting bottleneck in the way
Plus is handled. If I have:
Unprotect[Plus];
PlusNS[a__AffineExpression /; Length[{a}] > 1] :=
Sanitize@AffineExpression[Plus @@ Center /@ {a},
Join @@ Deviations /@ {a}];
Plus[a__AffineExpression /; Length[{a}] > 1] :=
Sanitize@AffineExpression[Plus @@ Center /@ {a},
Join @@ Deviations /@ {a}];
a_AffineExpression + b_Interval := a + AffineExpression[b]
a_Interval + b_AffineExpression := AffineExpression[a] + b
AffineExpression[c_, dev_] + other_?NumberQ :=
AffineExpression[c + other, dev]
Protect[Plus];
and then run an intensive test
LastNoiseSymbol = 0;
rndaff :=
AffineExpression[Random[Real, {-1, 1}], Table[{Random[Integer, {2,
20}], Random[Real, {-1, 1}]}, {Random[Integer, {2, 8}]}]];
Timing@(pretest = Table[rndaff, {10000}];)
Timing@(test = Sanitize /@ pretest;)
Timing@(sns = PlusNS @@ test;)
Timing@(sp = Plus @@ test;)
I get that sp calculates in about 10 times as much time as sns (about
5 seconds vs about .5 seconds).
This is quite bothersome, since the algorithms I need this for has dot
products at its core. Is there a way to speed this up?
A related remark, although not strictly part of my quesiton, is the
following: the idea at the core of Sanitize is the same as the
pairPlus function defined as an example in the Mathematica help (MH)
for Plus (Sanitize additionally Select[]s the pairs where the second
element is not null). MH defines pairPlus as
{#[[1, 1]], Plus @@ Last /@ #} & /@ Split[Sort@alist,
First[#1] === First[#2] &]
whereas on my own I had defined it as
Reap[Sow[#2, #1] & @@ # & /@ alist, _, {#1, Plus @@ #2} &][[2]]
By running the tests above it turns out that
1. sanitizing many short lists (e.g. calculating test from pretest) is
faster with MH code (1.8 seconds vs 2.2)
2. sanitizing a single long list (e.g. calculating sns) is faster with
my code (0.6 vs 0.8)
so it seems that MH code is faster for many runs with short lists,
whereas my code is faster for few runs with long lists (this probably
depends on the fact that MH needs to Sort[] the list)
Interestingly, sp takes about the same time regardless of the pairPlus
code used, so it somehow hits the sweet spot between length of lists
and number of runs.
--
Giuseppe "Oblomov" Bilotta
"E la storia dell'umanità, babbo?"
"Ma niente: prima si fanno delle cazzate,
poi si studia che cazzate si sono fatte"
(Altan)
("And what about the history of the human race, dad?"
"Oh, nothing special: first they make some foolish things,
then you study what foolish things have been made")