Services & ResourcesWolfram ForumsMathGroup Archive

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

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

• To: mathgroup at smc.vnet.net
• Subject: [mg29738] Re: Swiftest code to turn list of ordered pairs into Markov matrix
• From: "Seth Chandler" <SChandler at Central.UH.Edu>
• Date: Fri, 6 Jul 2001 03:24:33 -0400 (EDT)
• Organization: University of Houston
• References: <200107030840.EAA12085@smc.vnet.net> <9i066o$guq$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

I want to thank the many individuals who contributed responses to my query.
One can learn a lot about Mathematica programming, I think, from reviewing
this thread. The quality of responses is also a credit to this outstanding
newsgroup.

When I used the various functions on my own test data, the two swiftest
programs were those submitted by Dan Lichtblau, which exploited the
Mathematica compiler, and Andrzej Kozlowski, who used a method depending on
Split[Sort[oplist]]. I was hoping to double the speed of my original
approach. Instead, both methods sped up my calculation by more than a factor
of 50.  Other submissions achieved similar results. I present the two
methods that provest fastest on my data here. Anyone wishing a notebook
showing the results in more detail is encouraged to e-mail me at
SChandler at uh.edu.

Short[smalldata,3]

{{1,100},{1,9},{2,13},{2,9},{3,3},{3,9},{4,103},{4,9},{5,5},{5,9},{6,39},{6,
    9},\[LeftSkeleton]218\[RightSkeleton],{116,116},{116,114},{117,29},{117,
    114},{118,30},{118,114},{119,31},{119,114},{120,98},{120,114},{121,
    99},{121,114}}

Short[bigdata,3]

{{1,551},{1,3},{2,27},{2,3},{3,578},{3,3},{4,4},{4,3},{5,5},{5,3},{6,81},{6,

3},\[LeftSkeleton]1226\[RightSkeleton],{620,620},{620,621},{621,596},{621,
    621},{622,547},{622,621},{623,23},{623,621},{624,574},{624,621},{625,
    75},{625,621}}

lichtblau= Compile[{{z,_Integer}, {edges,_Integer,2}},
 Module[{mat = Table[0,{z},{z}]},
 Map[(mat[[#[[1]],#[[2]]]] += 1)&, edges];
 mat
 ]]

Timing[lichtblau[121,smalldata];]

{0. Second,Null}

Timing[lichtblau[625,bigdata];]
Out[163]=
{0.11 Second,Null}

kozlowski[z_,oplist_]:=Module[{a=Array[0&,{z,z}],matrixSet},
    matrixSet[{i_,j_},k_]:=a[[i,j]]=k;
    matrixSet@@@({First[#],Length[#]}&/@Split[Sort[oplist]]);a]

Timing[kozlowski[121,smalldata];]
{0.02 Second,Null}

Timing[kozlowski[625,bigdata];]
{0.15 Second,Null}
> ----- Original Message -----
> From: Seth Chandler <SChandler at Central.UH.Edu>
To: mathgroup at smc.vnet.net
> Subject: [mg29738]  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>