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

*To*: mathgroup at smc.vnet.net*Subject*: [mg29704] RE: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix*From*: "David Park" <djmp at earthlink.net>*Date*: Wed, 4 Jul 2001 03:08:28 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Here's my entry Seth. (I had to make a change in your Fold routine to make it work with large arrays.) zmax = 10; oplist = Table[{Random[Integer, {1, zmax}], Random[Integer, {1, zmax}]}, {50000}]; Fold[ReplacePart[#1, Extract[#1, #2] + 1, #2] &, Table[0, {zmax}, {zmax}], oplist] // Timing {1.26 Second,{{461,479,513,507,481,484,521,476,565,490},{494,520,477,541,469, 491,467,549,485,493},{502,491,484,503,488,524,484,473,506,489},{499,475, 513,496,506,498,539,499,509,486},{516,516,481,494,483,501,492,506,485, 528},{473,536,506,495,495,506,483,507,502,505},{469,518,534,509,498,497, 510,461,506,502},{483,479,484,492,507,496,514,517,516,497},{534,530,519, 504,508,494,492,472,512,481},{498,506,493,541,526,462,481,507,489,525}}} My entry... Timing[markov = Table[0, {zmax}, {zmax}]; ({markov[[Sequence @@ First[#1]]] = Length[#1]} & ) /@ Split[Sort[oplist]]; markov] {0.16 Second,{{461,479,513,507,481,484,521,476,565,490},{494,520,477,541,469, 491,467,549,485,493},{502,491,484,503,488,524,484,473,506,489},{499,475, 513,496,506,498,539,499,509,486},{516,516,481,494,483,501,492,506,485, 528},{473,536,506,495,495,506,483,507,502,505},{469,518,534,509,498,497, 510,461,506,502},{483,479,484,492,507,496,514,517,516,497},{534,530,519, 504,508,494,492,472,512,481},{498,506,493,541,526,462,481,507,489,525}}} Plus @@ Flatten[markov] 50000 David Park djmp at earthlink.net http://home.earthlink.net/~djmp/ > From: Seth Chandler [mailto:SChandler at Central.UH.Edu] To: mathgroup 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 > > > >