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