RE: Re: nth differences
- To: mathgroup at smc.vnet.net
- Subject: [mg39908] RE: [mg39878] Re: [mg39852] nth differences
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Tue, 11 Mar 2003 02:36:51 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Bob,
the timing advantage seems to depend on the data type of (packed) arrays,
see:
Integers:
In[1]:= t = Table[Random[Integer, {1, #}], {#}] &[1000];
In[2]:=
NestList[ListConvolve[{1, -1}, #] &, #, Length[#]] &[t]; // Timing
Out[2]= {10.575 Second, Null}
In[3]:=
NestList[Rest[# - RotateRight[#]] &, #, Length[#]] &[t]; // Timing
Out[3]= {5.828 Second, Null}
In[13]:=
t2 = Table[Random[Integer, {1, #}], {#}] &[1000000];
In[14]:= ListConvolve[{1, -1}, #] &[t2]; // Timing
Out[14]= {0.641 Second, Null}
In[15]:= Rest[# - RotateRight[#]] &[t2]; // Timing
Out[15]= {0.45 Second, Null}
Reals:
In[7]:= r = Table[Random[], {#}] &[1000];
In[8]:=
NestList[ListConvolve[{1, -1}, #] &, #, Length[#]] &[r]; // Timing
Out[8]= {0.541 Second, Null}
In[9]:= NestList[Rest[# - RotateRight[#]] &, #, Length[#]] &[r]; // Timing
Out[9]= {0.921 Second, Null}
In[10]:= r2 = Table[Random[], {#}] &[1000000];
In[11]:= ListConvolve[{1, -1}, #] &[r2]; // Timing
Out[11]= {0.521 Second, Null}
In[12]:= Rest[# - RotateRight[#]] &[r2]; // Timing
Out[12]= {0.671 Second, Null}
For unpacked arrays ListConvolve seems always to be in favor:
In[20]:= Developer`PackedArrayQ /@ {t, t2, r, r2}
Out[20]= {True, True, True, True}
In[21]:=
{ut, ut2, ur, ur2} = Developer`FromPackedArray /@ {t, t2, r, r2};
In[22]:= ListConvolve[{1, -1}, #] &[ut2]; // Timing
Out[22]= {1.082 Second, Null}
In[23]:= Rest[# - RotateRight[#]] &[ut2]; // Timing
Out[23]= {2.884 Second, Null}
In[25]:= ListConvolve[{1, -1}, #] &[ur2]; // Timing
Out[25]= {1.262 Second, Null}
In[26]:= Rest[# - RotateRight[#]] &[ur2]; // Timing
Out[26]= {2.344 Second, Null}
--
Hartmut Wolf
>-----Original Message-----
>From: BobHanlon at aol.com [mailto:BobHanlon at aol.com]
To: mathgroup at smc.vnet.net
>Sent: Sunday, March 09, 2003 11:31 AM
>To: mathgroup at smc.vnet.net
>Subject: [mg39908] [mg39878] Re: [mg39852] nth differences
>
>
>
>In a message dated 3/8/03 10:44:12 AM, writes:
>
>>
>> In a message dated 3/8/03 3:35:44 AM,
>_NOzturnerSPAM_ at cyberonic.com writes:
>>
>>
>> Say I have a list of k integers and I want to produce a list
>containing the
>> first differences? For example, given {1, 2, 5, 7, 8, 9} the first
>> differences are {1, 3, 2, 1, 1}, and the second differences
>are {2, -1, -1,
>> 0}, the third are {-3, 0, 1}, etc
>>
>> v = {1, 2, 5, 7, 8, 9};
>>
>>
>> Rest[v-RotateRight[v]]
>>
>>
>> {1,3,2,1,1}
>>
>>
>> nthDifference[v_List, n_Integer] :=
>>
>> Nest[Rest[#-RotateRight[#]]&,v,n] /;
>>
>> 0 <= n <= Length[v];
>>
>>
>>
>> nthDifferenceList[v_List, n_:Length[v]] :=
>>
>> NestList[Rest[#-RotateRight[#]]&,v,n] /;
>>
>> 0 <= n <= Length[v] && IntegerQ[n];
>>
>> nthDifference[v,3]
>>
>>
>> {-3,0,1}
>>
>>
>> nthDifferenceList[v,3]
>>
>>
>> {{1,2,5,7,8,9},{1,3,2,1,1},{2,-1,-1,0},{-3,0,1}}
>>
>>
>> nthDifferenceList[v]
>>
>>
>> {{1,2,5,7,8,9},{1,3,2,1,1},{2,-1,-1,0},{-3,0,1},{3,1},{-2},{}}
>>
>>
>> Bob Hanlon
>>
>>
>
>This shows a slightly faster method using listCorrelate
>
>nthDifference1[v_List, n_Integer] :=
>
> Nest[Rest[#-RotateRight[#]]&,v,n] /;
>
> 0 <= n <= Length[v];
>
>
>
>nthDifferenceList1[v_List, n_:Length[v]] :=
>
> NestList[Rest[#-RotateRight[#]]&,v,n] /;
>
> 0 <= n <= Length[v] && IntegerQ[n];
>
>
>nthDifference2[v_List, n_Integer] :=
>
> Nest[ListCorrelate[{-1,1},#]&,v,n] /;
>
> 0 <= n <= Length[v];
>
>
>nthDifferenceList2[v_List, n_:Length[v]] :=
>
> NestList[ListCorrelate[{-1,1},#]&,v,n] /;
>
> 0 <= n <= Length[v] && IntegerQ[n];
>
>
>
>v = Table[Random[], {100000}];
>
>
>
>d1 = nthDifferenceList1[v];//Timing
>
>
>
>{0.38 Second,Null}
>
>
>
>d2 = nthDifferenceList2[v];//Timing
>
>
>
>{0.28 Second,Null}
>
>
>
>d1==d2
>
>
>
>True
>
>
>
>Bob Hanlon
>
>
>