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

*To*: mathgroup at smc.vnet.net*Subject*: [mg29721] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix*From*: "Fred Simons" <f.h.simons at tue.nl>*Date*: Wed, 4 Jul 2001 18:43:40 -0400 (EDT)*References*: <200107030840.EAA12085@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

What will be the swiftest code seems to depend on the order of magnitude of your data. Your solution is, apart from a misprint in the second argument in Extract, pretty fast for small values of z. For some reason it tremendously slows down when z increases, much faster than I would expect. Below you find another solution for the problem with some comparisons. In[1]:= z = 10; n = 30000; oplist = Sort /@ Partition[ Table[Random[Integer, {1, z}], {2n}], 2]; In[2]:= Fold[ReplacePart[#1,Extract[#1,#2]+1,#2]&,Table[0,{z},{z}],oplist]; // Timing Out[2]= {1.49 Second,Null} In[3]:= mat = Array[0&, {z, z}]; Part[mat, Sequence @@ #]++ & /@ oplist;//Timing Out[3]= {3.95 Second,Null} In[4]:= z = 400; n = 30000; oplist = Sort /@ Partition[ Table[Random[Integer, {1, z}], {2n}], 2]; In[5]:= Fold[ReplacePart[#1,Extract[#1,#2]+1,#2]&,Table[0,{z},{z}],oplist]; // Timing Out[5]= {1333.1 Second,Null} In[6]:= mat = Array[0&, {z, z}]; Part[mat, Sequence @@ #]++ & /@ oplist;//Timing Out[6]= {4.07 Second,Null} Regards, Fred Simons Eindhoven University of Technology ----- Original Message ----- From: Seth Chandler <SChandler at Central.UH.Edu> To: mathgroup at smc.vnet.net Subject: [mg29721] [mg29683] 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>