Re: Swiftest code to turn list of ordered pairs into Markov matrix
- To: mathgroup at smc.vnet.net
- Subject: [mg29698] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix
- From: Richard Palmer <mapsinc at bellatlantic.net>
- Date: Wed, 4 Jul 2001 03:08:24 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
on 7/3/01 4:40 AM, Seth Chandler at SChandler at Central.UH.Edu 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
>
>
>
>
Hi Seth,
1. Build a matrix of zeros (the transition matrix). Call it TM.
2. For each ordered pair in oplist {I,j}:
A. Set TM[I,j]=TM[I,j]+1
Building the transition matrix is an overhead cost so the time complexity of
the algorithm depends on the length of oplist. Since you must read each
element of oplist to do this in any case, this should be about as fast as
you can do it. The program will speed up somewhat with how well you write
the code for step 2 above.
Regards,
Richard Palmer