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

*To*: mathgroup at smc.vnet.net*Subject*: [mg29738] Re: Swiftest code to turn list of ordered pairs into Markov matrix*From*: "Seth Chandler" <SChandler at Central.UH.Edu>*Date*: Fri, 6 Jul 2001 03:24:33 -0400 (EDT)*Organization*: University of Houston*References*: <200107030840.EAA12085@smc.vnet.net> <9i066o$guq$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

I want to thank the many individuals who contributed responses to my query. One can learn a lot about Mathematica programming, I think, from reviewing this thread. The quality of responses is also a credit to this outstanding newsgroup. When I used the various functions on my own test data, the two swiftest programs were those submitted by Dan Lichtblau, which exploited the Mathematica compiler, and Andrzej Kozlowski, who used a method depending on Split[Sort[oplist]]. I was hoping to double the speed of my original approach. Instead, both methods sped up my calculation by more than a factor of 50. Other submissions achieved similar results. I present the two methods that provest fastest on my data here. Anyone wishing a notebook showing the results in more detail is encouraged to e-mail me at SChandler at uh.edu. Short[smalldata,3] {{1,100},{1,9},{2,13},{2,9},{3,3},{3,9},{4,103},{4,9},{5,5},{5,9},{6,39},{6, 9},\[LeftSkeleton]218\[RightSkeleton],{116,116},{116,114},{117,29},{117, 114},{118,30},{118,114},{119,31},{119,114},{120,98},{120,114},{121, 99},{121,114}} Short[bigdata,3] {{1,551},{1,3},{2,27},{2,3},{3,578},{3,3},{4,4},{4,3},{5,5},{5,3},{6,81},{6, 3},\[LeftSkeleton]1226\[RightSkeleton],{620,620},{620,621},{621,596},{621, 621},{622,547},{622,621},{623,23},{623,621},{624,574},{624,621},{625, 75},{625,621}} lichtblau= Compile[{{z,_Integer}, {edges,_Integer,2}}, Module[{mat = Table[0,{z},{z}]}, Map[(mat[[#[[1]],#[[2]]]] += 1)&, edges]; mat ]] Timing[lichtblau[121,smalldata];] {0. Second,Null} Timing[lichtblau[625,bigdata];] Out[163]= {0.11 Second,Null} kozlowski[z_,oplist_]:=Module[{a=Array[0&,{z,z}],matrixSet}, matrixSet[{i_,j_},k_]:=a[[i,j]]=k; matrixSet@@@({First[#],Length[#]}&/@Split[Sort[oplist]]);a] Timing[kozlowski[121,smalldata];] {0.02 Second,Null} Timing[kozlowski[625,bigdata];] {0.15 Second,Null} > ----- Original Message ----- > From: Seth Chandler <SChandler at Central.UH.Edu> To: mathgroup at smc.vnet.net > Subject: [mg29738] Swiftest code to turn list of ordered pairs into Markov > matrix > > > > 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 value > s > > 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 > > > > > > > >

**References**:**Swiftest code to turn list of ordered pairs into Markov matrix***From:*"Seth Chandler" <SChandler@Central.UH.Edu>