Re: Swiftest code to turn list of ordered pairs into Markov matrix
- To: mathgroup at smc.vnet.net
- Subject: [mg29696] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Wed, 4 Jul 2001 03:08:22 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Unfortunately the code you sent is incorrect (which makes it rather easy or
difficult to beat). It works fine for short lists but something goes wrong
once they become long. Here is a case when your code works:
In[5]:=
ls=Table[{Random[Integer,{1,z}],Random[Integer,{1,z}]},{200}];
In[6]:=
Fold[ReplacePart[#,Extract[#,#2]+1,{#2}]&,Table[0,{z},{z}],ls]//Timing
Out[6]=
{0.05
Second,{{2,1,0,4,2,0,5,3,3,1},{0,3,3,6,0,2,1,2,0,1},{2,1,3,0,4,1,2,0,3,
2},{1,3,2,2,2,3,1,0,0,1},{2,0,4,3,0,1,5,6,6,3},{2,0,1,3,3,0,0,0,3,3},{4,
1,1,4,1,2,5,1,2,2},{3,1,1,1,2,3,2,2,3,4},{0,2,0,6,0,2,3,2,4,1},{1,3,1,3,
0,2,4,2,1,1}}}
Even so it seems to be beaten by the following one:
In[7]:=
Markov[ls_]:=
Block[{a=Array[0&,{z,z}]},
Plus@@(ReplacePart[a,Length[#],First[#]]&/@Split[Sort[ls]])]
In[8]:=
Markov[ls]//Timing
Out[8]=
{0.0166667
Second,{{2,1,0,4,2,0,5,3,3,1},{0,3,3,6,0,2,1,2,0,1},{2,1,3,0,4,1,2,
0,3,2},{1,3,2,2,2,3,1,0,0,1},{2,0,4,3,0,1,5,6,6,3},{2,0,1,3,3,0,0,0,3,
3},{4,1,1,4,1,2,5,1,2,2},{3,1,1,1,2,3,2,2,3,4},{0,2,0,6,0,2,3,2,4,1},{1,
3,1,3,0,2,4,2,1,1}}}
But now let's take a much longer list:
In[9]:=
ls=Table[{Random[Integer,{1,z}],Random[Integer,{1,z}]},{2000}];
the Markov function above works fine:
In[10]:=
Markov[ls]//Timing
Out[10]=
{0.0166667 Second,{{15,16,23,22,18,20,18,20,15,20},{21,14,20,29,22,23,12,23,
24,22},{21,11,18,28,15,19,24,19,19,8},{20,26,17,20,21,22,19,19,24,
20},{16,9,21,28,25,26,21,23,21,24},{28,20,24,24,21,20,13,17,16,25},{22,
24,23,33,23,16,17,22,18,12},{23,18,15,14,22,22,18,15,25,15},{23,20,19,
22,24,23,13,24,17,14},{20,20,14,22,20,13,14,25,21,26}}}
But yours does not:
In[11]:=
Fold[ReplacePart[#,Extract[#,#2]+1,{#2}]&,Table[0,{z},{z}],ls]//Timing
is followed but an avalanche of error messages and the computation has to be
aborted.
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
http://sigma.tuins.ac.jp/~andrzej/
on 7/3/01 5:40 PM, 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
>
>
>
>
>