Re: Swiftest code to turn list of ordered pairs into Markov matrix [using Sequence]

*To*: mathgroup at smc.vnet.net*Subject*: [mg29725] Re: Swiftest code to turn list of ordered pairs into Markov matrix [using Sequence]*From*: "Allan Hayes" <hay at haystack.demon.co.uk>*Date*: Wed, 4 Jul 2001 18:43:42 -0400 (EDT)*References*: <9hs1a0$bs9$1@smc.vnet.net> <9hugrb$f10$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Care with Sequence z= 100; oplist= Table[Random[Integer,{1,z}],{100000},{2}]; Here I use Sequence@@{x,y} to get Sequence[x,y] (b1=Table[0,{z},{z}]; MapThread[(b1[[Sequence@@#1]]=#2)&, {First/@#,Length/@# }]&[ Split[Sort[oplist]]]);//Timing {8.79 Second,Null} This is neat, but if I use {x,y}[[1]], {x,y}[[2]], I get a significant speed up. (b2=Table[0,{z},{z}]; MapThread[(b2[[#[[1]],#[[2]]]]=#2)&, {First/@#,Length/@# }]&[ Split[Sort[oplist]]]);//Timing {6.59 Second,Null} A speed up can similarly be obtained in David Park's code. Andrzej Kozlowski's helper function matrixSet[{i_, j_}, k_] := a[[i, j]] = k; in his Markov2 code performs a similar function Of course if we have to convert lists of different lenghts then Sequence must be used. The last form is still slower than Daavid Lichtblau's solution. convertToMarkovMatrix = Compile[{{n,_Integer}, {edges,_Integer,2}}, Module[{mat = Table[0,{n},{n}]}, Map[(mat[[#[[1]],#[[2]]]] += 1)&, edges]; mat ]]; convertToMarkovMatrix[n, oplist];//Timing {4.94 Second,Null} -- Allan --------------------- Allan Hayes Mathematica Training and Consulting Leicester UK www.haystack.demon.co.uk hay at haystack.demon.co.uk Voice: +44 (0)116 271 4198 Fax: +44 (0)870 164 0565 "Allan Hayes" <hay at haystack.demon.co.uk> wrote in message news:9hugrb$f10$1 at smc.vnet.net... > Seth, > > z= 50; > > oplist= Table[Random[Integer,{1,z}],{100000},{2}]; > > a=Fold[ReplacePart[#,Extract[#,#2]+1,#2]&,Table[0,{z},{z}],oplist];//Timing > > {44.6 Second,Null} > > (*I replaced {#2} with #2 -- the former gave trouble that I have not yet > tracked down*) > > (b=Table[0,{z},{z}]; > MapThread[(b[[Sequence@@#1]]=#2)&, > {First/@#,Length/@# > }]&[ > Split[Sort[oplist]]]);//Timing > > {4.84 Second,Null} > > a===b > > True > -- > Allan > --------------------- > Allan Hayes > Mathematica Training and Consulting > Leicester UK > www.haystack.demon.co.uk > hay at haystack.demon.co.uk > Voice: +44 (0)116 271 4198 > Fax: +44 (0)870 164 0565 > > "Seth Chandler" <SChandler at Central.UH.Edu> wrote in message > news:9hs1a0$bs9$1 at smc.vnet.net... > > 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 > > > > > > > > > > >