Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2003
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2003

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

Search the Archive

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



  • Prev by Date: RE: Re: Symbols and Lists
  • Next by Date: This should evaluate to zero
  • Previous by thread: Re: nth differences
  • Next by thread: presentation layout