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

*To*: mathgroup at smc.vnet.net*Subject*: [mg29696] 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:22 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

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. -- Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ http://sigma.tuins.ac.jp/~andrzej/ on 7/3/01 5:40 PM, Seth Chandler at SChandler at Central.UH.Edu wrote: > Suppose one has a list of ordered pairs oplist such as > {{1,5},{1,6},{2,3},{2,3} ... }. All the values in the list are positive > integers. The highest value in oplist is known to be some value z. > > Now one wishes to form a matrix such that the value at element i,j is equal > to > Count[oplist,{i,j}]. One terribly slow way to do this is > > Table[Count[oplist,{i,j}],{i,1,z},{j,1,z}] > > A faster way to do this is as follows: > Fold[ReplacePart[#,Extract[#,#2]+1,{#2}]&,Table[0,{z},{z}],oplist] > > Does anyone have a considerably faster way? A speed up of 100% or more would > be very helpful. > > For what it's worth Count[oplist,{something_,_}] is the same for all values > of something. > > P.S. The problem arises in converting a representation of a directed graph > into a Markov transition matrix. > > Thanks, > > Seth J. Chandler > Associate Professor of Law > University of Houston Law Center > > > > >