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

• To: mathgroup at smc.vnet.net
• Subject: [mg29710] Re: Swiftest code to turn list of ordered pairs into Markov matrix
• From: tgayley at wolfram.com (Todd Gayley)
• Date: Wed, 4 Jul 2001 03:08:34 -0400 (EDT)
• Organization: Wolfram Research, Inc.
• References: <9hs1a0\$bs9\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```On Tue, 3 Jul 2001 08:55:28 +0000 (UTC), "Seth Chandler" <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.

Seth,

This is much faster for most z and lengths of oplist. The idea is to build and apply a set
of replacement rules that associate an {i,j} pair with its count. Note the use of
Dispatch, which makes an enormous difference.

Array[List, {z,z}] /. Dispatch[First[#]->Length[#]& /@ Split[Sort[oplist]]] /. {_, _} -> 0

--Todd Gayley
Wolfram Research

```

• Prev by Date: Re: Re: Equations
• Next by Date: newsgroup use
• 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