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

*To*: mathgroup at smc.vnet.net*Subject*: [mg29705] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Wed, 4 Jul 2001 03:08:29 -0400 (EDT)*References*: <200107030840.EAA12085@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Seth Chandler 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 A straightforward binning procedure will be about as fast as you can get. Since everything is simple machine integer arithmetic, I use Compile and that appears to make things 5-10 times faster than otherwise. n = 100; edges = Table[{Random[Integer,{1,n}],Random[Integer,{1,n}]}, {n^3}]; convertToMarkovMatrix = Compile[{{n,_Integer}, {edges,_Integer,2}}, Module[{mat = Table[0,{n},{n}]}, Map[(mat[[#[[1]],#[[2]]]] += 1)&, edges]; mat ]]; In[39]:= Timing[mat1 = convertToMarkovMatrix[n,edges];] Out[39]= {3.77 Second, Null} To see how it is without Compile, try: Timing[mat2 = Module[{mat = Table[0,{n},{n}]}, Map[(mat[[#[[1]],#[[2]]]] += 1)&, edges]; mat ];] I am unable to compare this to your Fold[...] code because that gives error messages such as ReplacePart::psl: Position specification {{6, 58}} in ReplacePart[{{0, 0, 0, <<95>>, 0, 0}, <<99>>}, <<2>>] is not an integer or a list of integers. Extract::partw: Part 56 of ReplacePart[{{0, 0, 0, <<95>>, 0, 0}, <<99>>}, <<2>>] does not exist. For this example, Timing[mat3 = Table[Count[edges,{i,j}],{i,1,n},{j,1,n}]] will take longer than I am willing to wait. So I'll use only n^2 edges (1% of them). In[42]:= e2 = Take[edges,n^2]; In[43]:= Timing[mat3 = Table[Count[e2,{i,j}],{i,1,n},{j,1,n}];] Out[43]= {199.84 Second, Null} We'll compare it to the bin count method to see just what improvement factor we get in this case. In[44]:= Timing[mat4 = convertToMarkovMatrix[n,e2];] Out[44]= {0.04 Second, Null} In[45]:= mat4===mat3 Out[45]= True The bin count method is O(max(n^2,#edges)) for speed, which is what we want for this problem. Though if the edge set is small one might do better with a sparse representation of the matrix, as you could then get rid of the n^2 term. Daniel Lichtblau Wolfram Research

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