Re: How to explain these variations in execution speeds?
- To: mathgroup at smc.vnet.net
- Subject: [mg113174] Re: How to explain these variations in execution speeds?
- From: Vincent <sheeplane at gmail.com>
- Date: Sat, 16 Oct 2010 13:12:52 -0400 (EDT)
- References: <i95tjn$65j$1@smc.vnet.net>
On 14 Okt., 05:32, James Stein <mathgr... at stein.org> wrote:
> Stop your kernel; paste the following 14 lines in a notebook cell; then
> evaluate the cell.
>
> (*1*)n=10^6;
> (*2*)Timing[Sum[k,{k,n}]]
> (*3*)Timing[Sum[k,{k,Evaluate[n]}]]
> (*4*)Timing[Sum[k,{k,n+1}]]
> (*5*)Timing[Sum[k,{k,n-1}]]
> (*6*)Timing[Sum[k,{k,n+2}]]
> (*7*)Timing[Sum[k,{k,n-2}]]
> (*8*)Timing[Sum[k,{k,n+3}]]
> (*9*)Timing[Sum[k,{k,n-3}]]
> (*10*)Timing[Sum[k,{k,m}]/.m->n-4]
> (*11*)Timing[Sum[k,{k,m}]/.m->Evaluate[n-5]]
> (*12*)Timing[Sum[k,{k,m}]/.m->10^6+6]
> (*13*)Timing[Sum[k,{k,m}]/.m->10^6-6]
>
> Each sum represents approximately the same amount of "work",
> but some sums are computed significantly faster than others.
> What results of previous computations are being used? when? where are the=
y
> stored? how are they accessed?
> Why does the use of 'Rule' (in lines 10-13) speed things up?
> Do these examples suggest good ways to speed code in general?
> Or are they merely exceptional because 'Sum' is a built-in function?
> (If documentation answers these questions, just point me there. I searche=
d
> w/o success.)
>
> On my computer, the execution times are approximately:
> 0.3500 second: Out lines 2,3,5,7,9
> 0.1000 second: Out lines 4,10
> 0.0044 second: Out lines 6,8
> 0.0003 second: Out lines 11,12,13
>
> Some of the puzzle is either explained or compounded (but I'm not sure
> which!) by comparing lines 1 and 2 with lines 10 and 11. Why does 'Evalua=
te'
> speed 11 wrt 10, but not 2 wrt 1?
>
> My head began to whirl when I compared these two pairs of lines:
>
> Pair 1: (as above, lines 10 and 11)
> Timing[Sum[k, {k, m}] /. m -> n - 4]
> Timing[Sum[k, {k, m}] /. m -> Evaluate[n - 4]]
>
> Pair 2: (same as Pair 1, except "dummy" variable 'm' replaced by 'z' in
> second line only)
> Timing[Sum[k, {k, m}] /. m -> n - 4]
> Timing[Sum[k, {k, z}] /. z -> Evaluate[n - 4]]
>
> In each pair (assuming a fresh Kernel for each pair), the second line is
> much faster than the first; but in the first pair, the speed increase is
> much greater that the speed increase in the second pair. It seems like=
the
> symbol chosen for the "dummy variable" is somewhere retained, and affects
> further evaluations. (If so, how?)
>
> Two ancillary questions:
> 1. Is there a programmatic way (from a notebook) to stop then restart the
> Kernel?
> 2. Is there a set of commands that effectively return the Kernel to its
> initial state?
> (i.e., clear all user-defined symbols and history and reclaim memory)
The important difference here I belive is that you can show
analytically that
Sum[k, {k, g}]=1/2 g (1 + g)
And sometimes mathematica makes this substitution, leading to
effectively 0 computation time, and other times it doesn't. My test of
the expressions show that the computation time is effectively zero for
all expression on the form where g =>n+ 1 or n+2 ect. and that it
takes about 0.2 sec when it's on the form g=>n-1 n-2
This could have something to do with the requirement for the above to
be true that g>k, and some slight error in the way Mathematica resons
when doing the computation.
If you call
Trace[Sum[k, {k, n + 1}]]
Trace[Sum[k, {k, n - 1}]]
You see that the first one returns very quickly, while the second one
generate alot of intermediate calculations, non using the algebraic
solution at all. Why It does this I cannot say.