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
>
>
>
>