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

• To: mathgroup at smc.vnet.net
• Subject: [mg29705] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Wed, 4 Jul 2001 03:08:29 -0400 (EDT)
• References: <200107030840.EAA12085@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Seth Chandler 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

A straightforward binning procedure will be about as fast as you can
get. Since everything is simple machine integer arithmetic, I use
Compile and that appears to make things 5-10 times faster than
otherwise.

n = 100;

edges = Table[{Random[Integer,{1,n}],Random[Integer,{1,n}]}, {n^3}];

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

In[39]:= Timing[mat1 = convertToMarkovMatrix[n,edges];]
Out[39]= {3.77 Second, Null}

To see how it is without Compile, try:

Timing[mat2 = Module[{mat = Table[0,{n},{n}]},
Map[(mat[[#[[1]],#[[2]]]] += 1)&, edges];
mat
];]

I am unable to compare this to your Fold[...] code because that gives
error messages such as

ReplacePart::psl:
Position specification {{6, 58}} in
ReplacePart[{{0, 0, 0, <<95>>, 0, 0}, <<99>>}, <<2>>]
is not an integer or a list of integers.

Extract::partw:
Part 56 of ReplacePart[{{0, 0, 0, <<95>>, 0, 0}, <<99>>}, <<2>>]
does not exist.

For this example,

Timing[mat3 = Table[Count[edges,{i,j}],{i,1,n},{j,1,n}]]

will take longer than I am willing to wait. So I'll use only n^2 edges
(1% of them).

In[42]:= e2 = Take[edges,n^2];

In[43]:= Timing[mat3 = Table[Count[e2,{i,j}],{i,1,n},{j,1,n}];]
Out[43]= {199.84 Second, Null}

We'll compare it to the bin count method to see just what improvement
factor we get in this case.

In[44]:= Timing[mat4 = convertToMarkovMatrix[n,e2];]
Out[44]= {0.04 Second, Null}

In[45]:= mat4===mat3
Out[45]= True

The bin count method is O(max(n^2,#edges)) for speed, which is what we
want for this problem. Though if the edge set is small one might do
better with a sparse representation of the matrix, as you could then get
rid of the n^2 term.

Daniel Lichtblau
Wolfram Research

```

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