Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2001
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: Swiftest code to turn list of ordered pairs into Markov matrix
  • Next by Date: Re: Swiftest code to turn list of ordered pairs into Markov matrix
  • Previous by thread: Re: Swiftest code to turn list of ordered pairs into Markov matrix
  • Next by thread: Re: Swiftest code to turn list of ordered pairs into Markov matrix