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
>
> 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: PS.
• 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