Re: Swiftest code to turn list of ordered pairs into Markov matrix

*To*: mathgroup at smc.vnet.net*Subject*: [mg29719] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix*From*: Andrzej Kozlowski <andrzej at tuins.ac.jp>*Date*: Wed, 4 Jul 2001 03:08:48 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Chandler, It seems that the code I sent can be very slow when the size of the matrices is large (i.e. the maximum allowable value z is large). So I have written another function which seems to do much better in such cases. Here is a comparison of the two cases. my old one: Markov1[ls_]:= Block[{a=Array[0&,{z,z}]}, Plus@@(ReplacePart[a,Length[#],First[#]]&/@Split[Sort[ls]])] and new one: Markov2[ls_]:=Module[{a=Array[0&,{z,z}],matrixSet}, matrixSet[{i_,j_},k_]:=a[[i,j]]=k; matrixSet@@@({First[#],Length[#]}&/@Split[Sort[ls]]);a] For small z , e.g z=10, they are about equally fast. But when we try a larger value this is what happens: z = 100; ls = Table[{Random[Integer, {1, z}], Random[Integer, {1, z}]}, {20000}]; In[5]:= Markov2[ls];//Timing Out[5]= {0.883333 Second,Null} while In[6]:= Markov1[ls];//Timing Out[6]= {35.65 Second,Null} is dreadfully slow. Try testing my Markov2 against your (corrected) function. Andrzej -- Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ http://sigma.tuins.ac.jp/~andrzej/ on 7/3/01 11:51 PM, Chandler, Seth at SChandler at Central.UH.edu wrote: > Andrezj, > > Thanks so much for taking a look at this problem and spotting the bug. I am > not sure whether this is my bug or an oddity with ReplacePart, but, in any > event, it is easily fixed. Interestingly, when I use your random data, I get > the same sort of speed improvement you notice. When I use my actual data, > however, I find my (fixed) original method to be faster. I am trying to > figure out why this is. > > Seth > > -----Original Message----- > From: Andrzej Kozlowski [mailto:andrzej at tuins.ac.jp] To: mathgroup at smc.vnet.net > Sent: Tuesday, July 03, 2001 9:09 AM > To: Seth Chandler; mathgroup at smc.vnet.net > Subject: [mg29719] Re: [mg29683] Swiftest code to turn list of ordered pairs into > Markov matrix > > > Unfortunately the code you sent is incorrect (which makes it rather easy or > difficult to beat). It works fine for short lists but something goes wrong > once they become long. Here is a case when your code works: > > In[5]:= > ls=Table[{Random[Integer,{1,z}],Random[Integer,{1,z}]},{200}]; > > In[6]:= > Fold[ReplacePart[#,Extract[#,#2]+1,{#2}]&,Table[0,{z},{z}],ls]//Timing > > Out[6]= > {0.05 > Second,{{2,1,0,4,2,0,5,3,3,1},{0,3,3,6,0,2,1,2,0,1},{2,1,3,0,4,1,2,0,3, > > 2},{1,3,2,2,2,3,1,0,0,1},{2,0,4,3,0,1,5,6,6,3},{2,0,1,3,3,0,0,0,3,3},{4, > > 1,1,4,1,2,5,1,2,2},{3,1,1,1,2,3,2,2,3,4},{0,2,0,6,0,2,3,2,4,1},{1,3,1,3, > 0,2,4,2,1,1}}} > > Even so it seems to be beaten by the following one: > > In[7]:= > Markov[ls_]:= > Block[{a=Array[0&,{z,z}]}, > Plus@@(ReplacePart[a,Length[#],First[#]]&/@Split[Sort[ls]])] > > In[8]:= > Markov[ls]//Timing > Out[8]= > {0.0166667 > Second,{{2,1,0,4,2,0,5,3,3,1},{0,3,3,6,0,2,1,2,0,1},{2,1,3,0,4,1,2, > 0,3,2},{1,3,2,2,2,3,1,0,0,1},{2,0,4,3,0,1,5,6,6,3},{2,0,1,3,3,0,0,0,3, > > 3},{4,1,1,4,1,2,5,1,2,2},{3,1,1,1,2,3,2,2,3,4},{0,2,0,6,0,2,3,2,4,1},{1, > 3,1,3,0,2,4,2,1,1}}} > > But now let's take a much longer list: > > In[9]:= > ls=Table[{Random[Integer,{1,z}],Random[Integer,{1,z}]},{2000}]; > > the Markov function above works fine: > > In[10]:= > Markov[ls]//Timing > Out[10]= > {0.0166667 Second,{{15,16,23,22,18,20,18,20,15,20},{21,14,20,29,22,23,12,23, > 24,22},{21,11,18,28,15,19,24,19,19,8},{20,26,17,20,21,22,19,19,24, > > 20},{16,9,21,28,25,26,21,23,21,24},{28,20,24,24,21,20,13,17,16,25},{22, > 24,23,33,23,16,17,22,18,12},{23,18,15,14,22,22,18,15,25,15},{23,20,19, > 22,24,23,13,24,17,14},{20,20,14,22,20,13,14,25,21,26}}} > > > But yours does not: > > In[11]:= > Fold[ReplacePart[#,Extract[#,#2]+1,{#2}]&,Table[0,{z},{z}],ls]//Timing > > is followed but an avalanche of error messages and the computation has to be > aborted. >